454 Baidu Mianjing 1

0、 project

project ：

• Code to github Up ！
• Don't describe the business of the project too much ！
• Describe the design of the project , Rewritten open source library , What are the benefits ！ High concurrency , cache , Decoupling network layer 、 The business layer 、db Strong coupling of layers ！ Using microservices 、 Message queue ,redis That is, the business layer and db The layers are decoupled ！

Introduce the project ：

• Project background ; Why do ！（ Chat server , According to a business scenario , Design a high concurrency business chat server ！） Write the server and test its performance , Support simultaneous online 10000 People's online chat ！ Further promotion , How do you do it? , Add cluster ！ There is another way to split its services into very small services , Build a distributed architecture , Microservice based model ！
• Architecture design of chat server project , The network layer 、 Service layer 、 Data transmission uses Json agreement , The Internet uses muduo library , be based on epoll+ High concurrency model of multithreading ！

Interviewer said ： The project you wrote is unnecessary ？

• Introduce why you wrote this project ！
• Every time I write a project, I get something ！ Put the front … Knowledge has been practiced in the project , Really understand multithreading development , Thread communication , Application in the project , And what I did after learning knowledge points before demo It's totally different ; Intelligent pointer … I really feel his benefits ！

---

What problems are encountered in the project ？

• Design problem , Analyze performance reasons , Introduced redis, It's also a problem ！
• Encounter deadlock ！
• Encounter paragraph errors , Hang up ！
• When testing the bottleneck of the server ,fd Setting the upper limit of , How? ？
• Project stability , Security ！

1、 How to ensure that the transmitted data is not lost or duplicated （ Project related ）

IT Every description point of skill , Where can it be introduced into the project ！

How to ensure that a project is completed ? Three situations ;

• The agreement itself helps you ;
• The third-party framework based on protocol implementation helps you do ;
• Write your own application , I made it on my own. ！

How to achieve high concurrency in the project ？

• muduo The library itself has achieved high concurrency , take muduo In the library be based on Rector Model IO Reuse + Thread pool The way

TCP Ensure that the transmitted data is not lost or duplicated ?

• The agreement itself guarantees ;
• Don't lose ： Timeout retransmission mechanism ;
• Not heavy ： Serial number and confirmation response mechanism ;

The application ensures that the transmitted data is not lost or duplicated ?

• Also similar to TCP The retransmission mechanism 、 Serial number and confirmation response mechanism ;
• take TCP A mechanism on the transport layer protocol , Do it again on the application layer ！

---

During the interview, I talked about TCP The protocol and UDP agreement , Interviewers often give you a scene to design ;

• TCP Connection based , It's a streaming protocol ;UDP It's disconnected , It's the user packet protocol , Both sides of the communication, whether they can receive it or not , The sender just sends , The receiving party shall try to receive ！
• TCP There is a security mechanism , Over time retransmission 、 Out of order rearrangement 、 The sliding window 、 flow control 、 Congestion control ！ Ensure reliable data transmission on the Protocol ！UDP unreliable ！
• TCP Of ACK The response will also occupy the network bandwidth ！（ Now the bandwidth is very good , Fiber into the home , Not to be considered ！ ）
• Now design the program of server class , Are all used TCP agreement ！
• TCP Although it costs a little extra traffic , But in exchange Very reliable transmission ！UDP no way ！
• The server must first ensure High availability and Highly reliable ！

TCP Three and four waves of ！

2、 Why should threads of thread pool be dynamically expanded ？ & The process of pool （nginx）/ Thread pool (muduo)/ Memory pool / Connection pool （ database ）

2.1、 The process of pool （nginx）/ Thread pool (muduo)/ Memory pool / Connection pool （ database ）

• It's too expensive to use a pool , Temporary generation and destruction are expensive ！ Using pools ;
• Need resources , Take it from the pool , It doesn't release when used up , Then return to the pool ;
• Processes and threads , stay Linux In the environment , When creating a process thread , The bottom layer is also used for cloning , Which is used in the kernel or fork！
• When a small amount of memory is frequently opened and released in the project ,malloc and free The efficiency of is relatively low ！ Use memory pool to improve the efficiency of small memory ！
• The same is true of connection pools , constantly TCP Three handshakes and four waves , Low efficiency , High resource consumption ！

2.2、 Why should threads of thread pool be dynamically expanded ？

Without dynamic capacity expansion , Thread pool is dead , How about a fixed number ？ Objective to see ！

No dynamic expansion ：

• muduo The thread pool of the library is not dynamically expanded ！ use Reactor Model + epoll + Thread pool , Number of threads in thread pool ：IO Number + Number of worker threads and CPU Same number of cores for , Only in this way can we make the most of CPU Parallel processing ！

Dynamic expansion ：

• All pools have an initial number ！
• If all threads are occupied , At this time, the time-consuming task , Need to expand the capacity to generate new threads ！
• The context switching of threads is very expensive ; So thread pool ; When the business concurrency cannot be estimated ; It can ensure that the system resource consumption is small , Performance guaranteed ;
• When within a certain period of time , If some threads are idle all the time , Release the redundant threads ！

Thread cost ：

• 32 position linux Next ,4G Virtual memory , 3G user , Each process can pthread_create Can create 380 Left and right threads ,3G / 8M = 380+（8M Is the size of the thread stack ）
• The creation cost of a thread is the same as that of a process , It's all big ;
• Too many threads , The memory occupied by the thread itself is relatively large , Less memory can be used by businesses ;
• Use ulimit -s see Size of thread stack ,1000-2000 Thread words , Memory will be taken up by half ！
• Context switch of thread ;
• Cause server jagged load ;（1000-2000 While the thread is blocking and waiting , When an event arrives , That moment , Systematic cpu And memory consumption is very large , It is easy to cause the server to crash ！ So we are not allowed to create many threads ！）

3、 Suppose there is a problem interacting with the database , Threads block when interacting with the database , The thread cannot continue execution , What problems will arise ？

• Chat server adopts Reactor Model , One IO The thread is complex and listens for new connections , The remaining threads belong to worker threads ！ A thread is in epoll Monitoring sockets of many clients on , After receiving a user's request , Will start doing business ！ The process of doing business will involve the database curd;
• If a worker thread is blocked , Cause to register on this worker thread epoll Read and write events that occur behind all sockets on , The current thread cannot process ！

4、3 How to solve the problem in ？

gdb debugging , King Daqin pit , There are special debugging articles ！

resolvent ：

• Use connection pool , After a certain time （ Set to 1-2s） No response , Will return an error ！ In this way, there will be no blocking when interacting with the database ！
• Worker threads do not block , Work on other threads clientfd You can handle the event ！

5、C++ The concept and difference of reference and pointer in ？

from swap Function introduced , The formal parameter wants to change the value of the argument , It is not possible to use value transfer ;

C Using pointers in languages ,C++ Use a reference in ！

stay windows Direct breakpoint debugging , It is found that the assembly code of pointer and reference is exactly the same ！

stay Linux Next , direct -g, Use gdb debugging ,disassemble Look at the disassembly code ！

When looking at assembly instructions , Define a reference , In fact, it should be on the stack ,
open up 4 Bytes of memory , Put the address of the variable memory it wants to reference into 4 In bytes ;

When referencing the variable it points to by referencing a variable , In fact, the compilation is also developed from the previous bottom 4 Address of bytes of memory , Automatically do a dereference operation ！
When dereferencing through a pointer , Actually from the pointer 4 Bytes to get the address of the memory pointed to , To access the memory pointed to ;

It can be seen that at the level of compilation 100% Similarity of ！ That is, the assembly level is the same , It is different at the language level ！

C++ Try to use references when developing in ：

• In fact, references are the same as pointers , However, the reference must be initialized , All references are safer than pointers ;
• But the pointer can't say bad ,C and C++ The biggest one , Through the pointer, you can roam the memory , Through a pointer ++ and – Can be offset in memory ; References cannot be offset , Just use references , It will automatically offset ！
• Pointers give us great scalability , No dereference pointer , The pointer can p+1,p+2 Offset ！
• There is no way to offset references in memory , Direct dereference ！

6、 The difference between address passing and reference passing ？

7、 In practical application, pass a large array , Don't want to change it , But I don't want him to copy , How do you do it? ？

Digging a hole ！

• Passing an array does not make a copy at all , Passing the array name always passes Array start address , It's a pointer ;
• Because only the address of the array is passed , When we use it , The length of the array needs to be passed in ！
• Directly pass in the address of the array , Just like when the pointer passes , Inside the function, you can modify the contents of the array ; If you don't want to change it , Add const！ You can read the contents of the array , You can't modify the contents of an array ！
• And then extend it , Array =》stl Containers ！stl The container is our prepared ！

vecto The difference between containers and arrays ：

• Containers don't have to manage their own memory , If it's not enough, you can expand …
• When passing a container , From argument to formal parameter is a process of copy construction ！ If a container is passed in a function , The performance will be greatly reduced , There is a process of copy construction ; At this time, it should be passed by reference ！ References can also modify containers , So it needs to pass const Frequently quoted ！

8、const A * p and A* const p The difference between ?

const Is it the pointer itself or the pointer pointing ;

const A * p：

• const modification p, Express p Cannot be assigned ,p Can be assigned ;

A* const p：

• const Modification is p, Express p Can't be assigned ,*p Can be assigned ;

Is it just such a simple answer ？

How to diverge ？

• from From the perspective of practice Diverge , It means that we have used ！

From the perspective of practice ：

• const A * p Mainly used when calling functions , Arguments are passed to formal parameters through pointers , In formal parameters , We just want to access the arguments , I don't want to modify the arguments ！ So the pointer of the formal parameter , Add... At the front const！ You can read * p. Cannot be modified * p;
• A* const p, Namely and this Pointer dependent ,p It can't be modified , You can't give this Pointer assignment ,this The pointer always points to the object that invokes the method ！ Can pass this The pointer can modify the value of the pointing object （*p You can assign ）, But it can't be modified this The direction of （p Cannot be modified ）！

const The amount of decoration is constant , Constants cannot be modified ？
const int a = 10

If direct a = 20, This is absolutely impossible ！

How to change ？

int *p = (int *) &a;
*p = 20;

Modify by assembly ：

This has been modified ！

Why can it be modified again ？

• const Modified variables cannot be modified just in the compilation phase , At the grammatical level ;
• actually , On the assembly , Is not to say that const Directly change the properties of memory , From the original readable and writable to read-only and not write , impossible ！
• const Just based on grammar , Compile phase , The compiler can detect a const The modified constant is assigned ！ But after compiling , It's on the assembly instructions , There is no such thing as const 了 , const It can't be modified at the grammatical level ！
• C In language ,const It's a constant variable ;C++ In language ,const Is a constant ！

9、 Add... After the member function const What does that mean? ？ What restrictions will there be ？

Answer from a practical point of view ：

• Define a const Often objects call ordinary methods , I found it impossible to call ！

Why can't you call ？

• C++ Call a method with an object , After the compilation , The actual calling process is still a C Function call ！ It's just Pass the address of the calling object as an argument to the function ; When compiling member methods , Will add a formal parameter this To receive the address of the object , however this Is a pointing non const Object's const The pointer , Can't receive const object ;

All when a constant object calls a member method , The member method needs to be followed by const, Affected this The pointer , Give Way this Fingers become points const Object's const The pointer , Such formal parameters this You can receive the object ！ A constant object can call a constant member method ！

Limit ：

• In the usual method , Only member variables of the object can be accessed , Can't change ！
• mutable Modified variables can still be modified ！

---

this The pointer

• Each object has a this The pointer , adopt this Pointer to access your address .
• this The pointer is not part of the object ,this The amount of memory occupied by the pointer is not reflected in sizeof On the operator .
• this Pointers can only be used in member functions , Global function 、 Static functions cannot be used this The pointer ;
• In ordinary member functions ,this Is a pointing non const Object's const The pointer （ For example, the class type is Student, that this Namely Student *const Pointer to type ）;
• stay const In member function ,this The pointer is a point const Object's const The pointer （ For example, the class type is Student, that this Namely const Student * const Pointer to type )
• this The pointer is constructed before the execution of the member function , Destroy after the execution of the member function .

const Object and the const Member functions

• Add const modification , Means in the function this A pointer is a constant pointer to a constant object , Member variables cannot be modified .
• One const If the member function returns as a reference *this, Then its return type is constant reference ;
• about const Object or const Object references and pointers , Member variables in objects cannot be modified , So you can only call const Member functions , Member variables will not be modified ;
• For non const object , You can call const Member functions , You can also call non const Member functions .

Constant member function features

• A constant member function cannot change the contents of the object that calls it .
• Constant object , And references or pointers to constant objects can only call constant member functions .
• You cannot call a normal member function on a constant object .
• If the constant member function is defined outside the class , You must also add const keyword .
• const Member functions can be modified and added mutable The value of the member variable of the keyword .
• Static member functions are object independent , Therefore, it cannot be declared const.

10、 Class const How to initialize members ？

Define the member variables that must be initialized , Must be placed in the initialization list （const Variable 、 Reference member variables ）

11、vector How to manage memory ？

• from vector Speaking of the bottom of , It is a dynamically expanded array ;

• The container depends on the space configurator allocator To manage memory , Space configurator has 4 This method is very important ！

• vector Only responsible for the construction of objects 、 destructor , Memory management depends on allocator Space configurator to manage .

• stay Linux Next is 0 - 1 - 2 - 4 - 8 2 Double capacity ！vs2017,2019 Next is 1.5 Double expansion ;( From a practical point of view , Write code , Constantly insert elements , Each time printing vector Capacity and actual size , Explore the capacity expansion mechanism .capacity return vector The capacity of ,sizeof Is to return vector The size of the actual element in )

• Under the summary , This is it. vector How to manage memory ;

• (turn ！ You can also introduce vector Other important methods ;（vector There are many other useful methods , for instance …）

• all C++ STL When the container manages the memory of the underlying object , It is impossible to use directly new and delete, Why can't you use , I said in class ！

• All containers must rely on allocator Space configurator , There are 4 A way ：construct、destory、allocate、deallocate;

• construct、destory Responsible for the construction and Deconstruction of objects ;allocate、deallocate Responsible for the development and release of memory , Is in the vector When managing memory , Be sure to put the object new The construction of objects and memory development are separated , take delete The destruction of objects and the release of memory are separated ！（ reason ： Initialize a vector When , If you use new Words , It will not only open up a memory , It will also construct some useless objects , It doesn't conform to our logic , All the underlying memory development depends on allocate To the ,allocate and deallocate Are used by default C Library malloc and free）

• If the application layer uses vector More frequently , Small pieces of memory are used more frequently , Memory pool can be used to replace allocate and deallocate Used in malloc and free;

• Re expansion , stay C++11 Copy construction and assignment overloading with right value references provided later ！ Greatly improved vector Copy and construct performance ！

12、vector When will iterator failure occur ？（ Consider how to avoid from programming habits ）

• In the process of their own practice , Have you ever touched the failure of iterators ？
• When we use vector When it comes to solving problems , It is possible to actually traverse vector, That is, when reading , Iterators do not fail ;
• It's going on insert and erase When , The iterator will fail ,insert and erase All received in are iterators , not only vector, Related container methods , Generally, we receive iterators , I'll talk later ！
• The bottom layer of the iterator is actually the encapsulation of a pointer , take vector Come on ,vector The bottom layer of the iterator of is a pointer ,vector The pointer to the iterator of is vector An array at the bottom ;
• Iterators are overloaded by this operator , In the same way Traverse different containers ！ Because the traversal methods of different containers are encapsulated in the iterator ++,- - In the operator ;
• insert It may return to the value vector Expansion of containers , Memory location has changed , At the bottom of the iterator is a pointer , Point to an address , After the expansion , The iterator must fail ！
• How to deal with ？insert and erase The return value will return the iterator of the new location , You need to update the loop variable of the iterator ;
• erase After deleting elements , All the elements behind move forward ,erase The iterator between the first element and the currently deleted element is still valid ！ But the current position to the end of the element iterator will change , You need to update ！

Now start expanding ：

• Iterators are very important for containers ！
• Every container has an iterator of bytes , Because the underlying data structure of each container is different ;
• But actually when writing code , It is found that the code of iterator traversing the container is the same , How does this work ？ Because iterators provide ++、- - Operator overload function , Although different containers , Different data structure elements have different iteration methods , But different iteration methods of different data structures are encapsulated in iterators ++、- - Operator overload function , So use iterators to manipulate different containers , The code is exactly the same ！
• Not only does the container method receive iterators for addition and deletion , Generic algorithms also use iterators ！

13、 Use copy construction to give a complex vector The assignment is not very good , How to solve ？

• It means vector Inside is a big object ,vector The copy construction of will cause the copy construction of many large objects ;
• The assignment will first temporarily construct the object on the right , According to the resources on the right , Open up memory for the object on the left , Then construct many objects on its memory , Then destruct the temporary object on the right , Destruct the memory ！ Efficiency is very low ！
• Depending on the situation std::move call vector R-value reference copy construction and assignment overloading （ Right value reference is also called mobile semantics , Will not open up memory for the left according to the size of the right , Construction object , Instead, take all the resources on the right ！）
• vector In addition to copy construction and assignment , Other methods also provide methods with right value references ！

14、map/multimap difference

take Associate container + Underlying data structure + Common methods Merge into one ！

map/multimap At the bottom of the are red and black trees , After that, we can say that the hash table and red black tree of data structure ！

Extend to hash table , It can be said that hash conflicts , Solution ！

When it comes to red and black trees , Can be BST and AVL Say it all , These belong to binary search tree , They just have their own characteristics ！

If you just say map Of key It can be repeated ,multimap Of key It can't be read repeatedly You can't ！

Try to answer questions From a practical point of view ！

Ideas ：

• When will it be used map, When doing something, you will use map; From the perspective of practice to map;
• And then cut to map/multimap On the difference between the two ！
• practice + theory ！

map and multimap Are called mapping tables , It mainly deals with the scenario of key value pairs with associated data ！ For example, a student's student number corresponds to a student's grade , Get student data by quickly searching student number ！

map and multimap The main difference is key Whether the value can be repeated ！value It can be repeated ！

Then introduce the underlying data structure Red and black trees ！ therefore map The time complexity of adding, deleting and checking is O（log2n）, Very efficient !

Red and black trees are generally used for key In scenarios with sequencing requirements ！

And then extend it , Just say , In fact, most scenes are right key There is no requirement for the order of , I usually look at some open source libraries ,muduo Network Library , It's all about unordered_map and unordered_set！ nudges ！

And then extend it ,Linux The virtual memory management of is red black tree , The efficiency is very high ！ In the early Linux Our memory management uses AVL, Last Linux3.6 The version has been changed to red black tree ！ Because red and black trees are relative to AVL Trees , It has the advantage of …

So we extend to AVL Trees , It's a balanced tree , It's a memory based ！

And then say , And based on IO Balanced tree of operations ,B Trees and B+ Trees … This is commonly used in database indexing , Its benefits are …

The core of the problem is detailed , The associated content is up to , Waiting for the interviewer to ask ！

---

Sequence containers vector、list、deque

• In especial vector and list, Array and linked list of mapping and basic data ;
• When it comes to containers , Iterate it 、 Talk about generic algorithms ！

15、 Intelligent pointer

When you really work , Bare pointers are rarely used ！

Speaking of it , Let's start from a practical point of view , What's the use of asking him ？

• Purpose ： Automatically release resources （ Object resources , File resources ）, I'm worried that some resources have been used up and have not been released , There will be resource leakage ！
• Smart pointers take advantage of the automatic deconstruction of the scope of objects on the stack , Write the release code of the resource to the destructor of the smart pointer ！

---

This is the introduction during the interview ：

• stay C In language , Dynamic allocation of heap memory uses malloc+free; stay C++ What we use new+delete;
• But manual development , May be free and delete Forget to write , Or other file resources forget to close ！
• In order to solve these problems automatically , Use smart pointer , Take advantage of the automatic destruct feature of the scope of the object on the stack ;

wisdom There are two kinds of energy pointers from the big direction , Without reference count and with reference count ！

• Without reference count ：C++ The standard library was previously provided auto_ptr, Introduce to you ;auto_ptr problem ： It will automatically hand over the ownership of the management object ！ therefore auto_ptr After copying construction and assignment , The original auto_ptr It can't be used anymore , This is a pit , He didn't take any precautions , Theoretically, it can be used , But once used, it will make mistakes ！auto_ptr Cannot be used in containers , The copy construction of the container will involve the copy construction and assignment of each element , Finally, it involves auto_ptr Copy construction and assignment of ！
• Without reference count unique_ptr, We recommend ,unique_ptr Remove the copy construction and assignment overload of lvalue , The copy construction and assignment overload of the right value are published , The advantage is …
• With reference count ： If you want multiple smart pointers to manage a resource , Use reference count ,shared_ptr, Bottom use CAS Operation to guarantee the atomic operation of adding and subtracting the reference count , It can be directly used in multithreaded environment ！

Classical problems ： With shared_ptr Why weak_ptr, Strong and weak smart pointer ？

• Starting from practice , If only shared_ptr Circular reference problems occur , Introduce examples of your own practice , How to solve ？

It also introduces shared_ptr and weak_ptr In solving multi-threaded access sharing C++ Thread safety of objects （ In class ）

also enable_shared_from_this and shared_from_this Get a smart pointer to the current object ;

• shared_from_this： How to get a of the current object in the member function of the current object shared_ptr The pointer ;
• Cannot pass the current object's this The pointer goes directly through one piece shared_ptr, It leads to two shared_ptr They all think that only they own this resource , Finally, when resources are released , Will release 2 Time , Problems arise ！（ King Daqin pit blog）

Continue to extend ：make_shared

effect ： by shared_ptr Filling pit ;

shared_ptr The operation of is divided into 2 Step ：

• structure shared_ptr Will send it a new Of memory ,shared_ptr The bottom layer will also new A control block that controls resources , It is also equivalent to a memory block , The address of the resource is recorded on it And reference count of resources ;
• Now suppose that the external resources managed new succeed , The underlying control block new failed , What do I do ？ save shared_ptr It was not created by itself , In the end, resources will not be automatically released for us , There is a problem with the creation of the smart pointer itself ;
• C++11 Later, it provided us make_shared, Get a point to the resource shared_ptr, It's very safe ！

C++14 After that make_unique, Complement with no reference count unique_ptr It's a pit ！

16、 Design ：10 Ten thousand positive integers , Value range 0 To 100w, Do not repeat each other , Given a number, judge whether it has appeared in these numbers ？

Interview reference questions ：

• 1、 Big data requires topK The problem of ;

---

• 2、 The problem of duplicate checking ;（ Really have no idea , Hashtable ！ The time complexity of adding, deleting and checking is O(1)）

The disadvantages of hash tables ：

• Space for time , Large memory consumption ！
• Common chain hash table , The elements with hash conflicts are placed in a bucket , A node represents an element , Linked lists , A node contains The node element + The address of the next node ！ Suppose you store int type ,10 Ten thousand elements are needed 40 Ten thousand bytes + The address of the next node 40 Ten thousand bytes , in total 80 Ten thousand sub sections ;

If you check and optimize ：
1、 Bitmap method ;

• One bit records one number ,1 Bytes 8 bits ,1 Bytes can be recorded 8 A digital ;
• Bitmap method is very memory saving , We can only judge whether the number has appeared ;
• It is recorded in an array , You have to know ,10 What is the largest bit of 10000 integers ; You need to define the size of the bitmap array according to the largest array ！

2、 The bloon filter ;

• There is a certain miscalculation ;
• Bloom filter said The number is not , that The number must not be ; Bloom filter said The number is , Numbers It doesn't have to be ;
• We need to explain in advance , This question allows a certain number of misjudgments ！
• Bloom filters are often used redis The cache , For example, in the cache , hit key Words , Allow some miscalculation , Improve the efficiency of body cache ！

17、 The intersection of two ordinal groups ？ Code level optimization ？n Take the intersection of two arrays ？

1、 Hashtable ;

• An array element builds a hash table first , The elements of another array are looked up in this hash table ;
• problem ： The ordered array in the title is not used , Not the best ！
• Time complexity ： O(m)xO(1)

2、 Two points search ;

• Traverse each element of the first array , Do a binary search in the second array ;
• Time complexity ： O(mlogn)
• problem ： Still not using both arrays in order , Only one array is used, which is ordered ！

3、 Double pointer ;

• Time complexity ： O(m) + O(n) = O(m + n)

Sum up the comparison ：

• The number of two arrays is similar （ Use double pointer ）; For example, all of them are 10000 individual , Two minute search time O(10000*13)= O(130000), Double pointer O(20000);
• The number of two arrays is quite different （ Use dichotomy ）; One 10 individual , One 20000 individual ; Double pointer O(10 + 20000), Two points search O(14*10);

---

n Take the intersection of two arrays ？

• 1、 Divide into two arrays , Keep doing it ！
• 2、n Pointer to process ！