当前位置:网站首页>I have been working for six years with a college degree. Do you still have a chance to enter a large factory?

I have been working for six years with a college degree. Do you still have a chance to enter a large factory?

2020-11-10 00:31:27 QT programmer

Input [www.baidu.com] The whole process in the browser , The more detailed, the better .

The browser gets the input domain name [www.baidu.com]
Browser to domain name system  DNS  Request parsing [www.baidu.com] Of  IP  Address
DNS Analysis of Baidu server IP Address
Browser and server setup TCP Connect ( Default port 80)
The browser sends out HTTP request , Request Baidu home page
Server pass HTTP Request to send the home page file to the browser
TCP Connection release
The browser parses the home page file , Exhibition web Interface

Please describe C/C++ The memory partition of the program ?

Actually C and C++ There is still a certain difference in the memory partition of , But there is no distinction here :

1) The stack area (stack)— Release is automatically allocated by the compiler , Stores the parameter values of the function , The value of a local variable, etc , It operates like a stack in a data structure .
2) Heap area (heap) — Release is usually assigned by the programmer , If programmers don't release , At the end of the program, the OS Recycling , Notice that it's not the same as the heap in the data structure , The distribution method is similar to the linked list
3) Global area ( Static zone )(static)—, Global and static variables are stored in one block , Initialized global and static variables in one area , Uninitialized global variables and uninitialized static variables are in another adjacent area . - Released by the system at the end of the program .
4)、 Text constant area — That's where constant strings are put . Released by the system at the end of the program .
5)、 Program code area — Store the binary code of the function body .

The difference between stack and heap :

1) Heap and stack storage : The stack stores local variables 、 Function parameters, etc . Heap storage uses new、malloc Application variables, etc ;
2) Application method : Stack memory is allocated by the system , Heap memory is requested by yourself ;
3) System response after application : Stack —— As long as the remaining space of the stack is larger than the requested space , The system will provide memory for the program , Otherwise, an exception will be reported indicating that the stack overflows . Pile up —— First of all, you should know that the operating system has a list of free memory addresses , When the system receives an application for a program , Will traverse the list , Find the first heap node whose space is larger than the applied space , Then delete the node from the free node list , And allocate the space of the node to the program ;
4) Request size limit :Windows The size of the lower stack is usually 2M, The heap has a large capacity ;
5) Comparison of application efficiency : Stacks are allocated automatically by the system , Faster . Heap usage new、malloc Wait for distribution , slower ;

summary : The advantage of stack area is processing efficiency , The advantage of the reactor area is flexibility ;

Memory model : Free zone 、 Static zone 、 Dynamic area ; according to c/c++ Object lifecycles are different ,c/c++ There are three different memory regions in the memory model of , namely : Free existence
according to c/c++ Object lifecycles are different ,c/c++ There are three different memory regions in the memory model of , namely : Free storage area , Dynamic area 、 Static zone .
Free storage area : The non static storage area of a variable , That is to say, the stack ;
Dynamic area : use new ,malloc Allocated memory , That is to say, pile ;
Static zone : Global variables , Static variables , Where string constants exist ;
notes : Although the code takes up memory , But that does not belong to c/c++ Part of the memory model ;

The idea of quick sequencing 、 Time complexity 、 Implementation and optimization methods ?

Three steps to quick sort :

(1) Choose the benchmark : In the waiting sequence , Pick out an element in some way , As " The benchmark "(pivot);
(2) Split operation : The actual position of the datum in the sequence , Divide the sequence into two subsequences . here , The elements to the left of the datum are smaller than the datum , The elements to the right of the datum are all larger than the datum ;
(3) Fast sort two sequences recursively , Until the sequence is empty or there is only one element .

Choice of benchmark :
For divide and conquer algorithm , When each partition , If the algorithm can be divided into two subsequences of equal length , Then divide and conquer algorithm will achieve maximum efficiency . namely : The same array , The least time complexity is that each selected benchmark can divide the sequence into two equal length ; The biggest time complexity is that the benchmark of each selection is the largest or smallest element of the current sequence ;
Quick code implementation :
We usually choose the first of a sequence as the cardinal number , So the quick code is as follows :
`void quicksort(vector<int> &v,int left, int right)
{
if(left < right)//false Then the recursion ends
{
int key=v[left];// Base assignment
int low = left;
int high = right;
while(low < high) // When low=high when , Indicates the end of a split
{
while(low < high && v[high] >= key)//v[low] Cardinal number , From back to front with cardinal number
Than a
{
high--;
}
swap(v[low],v[high]);
while(low < high && v[low] <= key)//v[high] Cardinal number , From front to back and cardinal number
Than a
{
low++;
}
swap(v[low],v[high]);
}
// After split , Repeat for each segment
quicksort(v,left,low-1);
quicksort(v,low+1,right);
} }
`
notes : Such an array or sequence v Must be a formal parameter of the reference type , Because the follow-up results need to be directly reflected in the original
In sequence ;
Optimize :
The cardinality of the above quick sort is the first element of the sequence , So for an ordered sequence , Fast scheduling time complexity will reach
Worst o(n^2). therefore , The optimization direction is the reasonable choice base .
Common practice “ Take the three Numbers ” Law ( The sequence is too short to combine with other sorting methods , Such as insertion sort 、 Selection sort
etc. ), as follows :
① When the sequence interval length is less than 7 when , Use insert sort ;
② When the sequence interval length is less than 40 when , Divide the interval into 2 paragraph , Get the left endpoint 、 Right endpoint and midpoint , We
Take the median of these three points as the cardinal number ;
③ When the sequence interval is greater than or equal to 40 when , Divide the interval into 8 paragraph , Get three points to the left 、 Middle three and right three , branch
Don't get the middle of the three points on the left 、 The median in the middle three points and the median in the right three points , We're going to get three more median numbers
Take the median , Then take the value as the cardinality .
The specific code is only in the previous code will “ Base assignment ” Change it to ①②③ The corresponding code can be :
`int key=v[left];// Base assignment
if (right-left+1<=7) {
insertion_sort(v,left,right);// Insertion sort
return;
}else if(right-left+1<=8){
key=SelectPivotOfThree(v,left,right);// Three out of three
}else{
// Three groups, three choices , Three more ( Use 4 Time SelectPivotOfThree, It's not shown here )
}
Function to call :
void insertion_sort(vector<int> &unsorted,int left, int right) // Insertion sort algorithm
{
for (int i = left+1; i <= right; i++)
{
if (unsorted[i - 1] > unsorted[i])
{
int temp = unsorted[i];
int j = i;
while (j > left && unsorted[j - 1] > temp)
{
unsorted[j] = unsorted[j - 1];
j--;
}
unsorted[j] = temp;
}
}
}
int SelectPivotOfThree(vector<int> &arr,int low,int high)
// Take the three Numbers , At the same time, move the median to the first place in the sequence
{
int mid = low + (high - low)/2;// Calculate the subscript of the element in the middle of the array
// Select the pivot using the middle of three
if (arr[mid] > arr[high])// The goal is : arr[mid] <= arr[high]
{
swap(arr[mid],arr[high]);
}
if (arr[low] > arr[high])// The goal is : arr[low] <= arr[high]
{
swap(arr[low],arr[high]);
}
if (arr[mid] > arr[low]) // The goal is : arr[low] >= arr[mid]
{
swap(arr[mid],arr[low]);
}
// here ,arr[mid] <= arr[low] <= arr[high]
return arr[low];
//low Save the value in the middle of the three positions in the position of
// You can directly use low The elements of position act as pivots , Instead of changing the partition function
}
`
There are two points to note here :
① Insert sort algorithm implementation code ;② The trinomial median function is not only to achieve the middle , And moving the median to the lowest level , So that the original partition function is still available .

How to optimize MySQL?

In terms of effect, the first one has the greatest impact , It's getting smaller and smaller in the back .

① SQL Statement and index optimization
② Database table structure optimization
③ Optimization of system configuration
④ Hardware optimization

Two intersecting one-way lists , How to find their first public node ?

① If two linked lists intersect , Then start at the intersection , The following nodes are the same , That is to say, the last node must be
Same as ;
② Traversing two linked lists from beginning to end , And record the chain length , When their tail nodes are different , Then the two are definitely different
hand over ;
③ Same tail node , If A Long for LA,B by LB, If LA>LB, be A front LA-LB Skip first ;
—— More classic questions like linked lists : Find the input of one-way local circular list 、 Combine two ordered lists to form
An ordered list 、 Reverse order of linked list 、 Find the penultimate K Nodes , Judge whether there is a ring, etc .

new/delete and malloc/free The underlying implementation of ?

malloc and new The difference between :

1)malloc And free yes C++/C Standard library functions for languages ,new/delete yes C++ Operator . They can be used to request dynamic memory and free memory ;
2)new Returns a pointer of the specified type , And it can automatically calculate the required size . and malloc The number of bytes must be calculated by the programmer , And after returning, it is forcibly converted to a pointer of the actual type ;
3)new/delete The constructor initialization can be performed automatically while the object is created , Destructors are automatically executed before the object dies . and malloc Just allocate memory , The resulting memory cannot be initialized , So we get a piece of new memory , Its value will be random ; since new/delete The function of the malloc/free, Why? C++ And keep it malloc/free? because C++ Programs often call C function , and C The program can only use malloc/free Managing dynamic memory .

new/delete、malloc/free Underlying implementation principle :
summary :new/delete The underlying implementation of is to call malloc/free Functionally implemented , and malloc/free The bottom of
Layer implementation does not operate memory directly, but calls the system API Realized .
new/delete The schematic diagram of the two distribution modes is as follows :
Be careful , For the example at the end of the figure above “new[]/delete[] When it comes to opening up 4 Bytes are used to store objects
Count ”, Explain as follows :

① For built-in types :

new [] Not before the first address 4 Bytes define the length of the array .delete and delete[] It's the same execution effect , Will delete the entire array , The length to be deleted from new You can know when .

② For custom types :

new [] Will be in front of the first address 4 Bytes define the length of the array . When delete[] when , According to the previous 4 The length defined by bytes to execute the destructor to delete the entire array . If it's just delete Array first address , Only the value of the first object will be deleted .

image

I don't know if there are so many interview questions , Those who need interview questions can Share Oh

版权声明
本文为[QT programmer]所创,转载请带上原文链接,感谢