Xiaomi's one-sided interview questions (self sorting answers)

Xiaomi interview question

Of course I haven't had an interview yet , This is the true question of Niuke .

1.HashMap

• 1.7 It used to be arrays + Linked list ,1.8 It's an array + Linked list + Red and black trees
• 1.7 An array is Entry, It's head insertion , During the expansion, the original order of elements in the list will be changed , In the case of concurrency, the problem of chaining is caused .
• 1.8 yes Node, Use tail insertion , The original order of the list elements will be maintained during the expansion , There will be no link problem .
• hashmap Expansion mechanism ： The default is 16, When it exceeds the total capacity 0.75f, That is to say >12 It will be expanded when it is used , Why 0.75 Well ？ Because it satisfies the statistical Poisson distribution , When the expansion factor is 0.75 The probability of reaching the highest . The capacity of each expansion is doubled .
• 1.8 Later, due to the addition of red and black trees , So when the node of the linked list at a certain position in the array >8 when , And the length of the array >=64 when , The list is transformed into a red black tree , If the array length <64, Then only the array capacity is expanded . If the linked list is reduced to <5, Red and black trees will degenerate into linked lists .
• If concurrent hashmap have access to currentHashMap

2. State of thread

• New state NEW： Thread state not yet started
• Ready state RUNNABLE： Ready state , Waiting in line CPU Allocate resources
• Block waiting BLOCKED ： Blocked waiting for monitor lock , Such as waiting for synchronized Code block
• Wait state WAITING ： A thread called Object.wait(), Wait for another thread to call Object.notify()
• Time wait for TIMED_WAITING： More timings than waiting state , If the waiting time is exceeded, it will enter this state
• Termination status TERMINATED： Indicates that the thread has completed execution

3. The difference between stack and queue

Common ground ：

• It's all linear
• They can only be inserted and deleted at the end of a linear table
• Can be achieved through the sequence structure and linked list structure
• The time complexity of insertion and deletion is O（1）, So is the spatial complexity

Difference ：

• First in first out queue , Stack back in and back out

4. Transaction and isolation levels

Business :

• Atomicity ： Not all transactions are executed , Or they don't do it
• Uniformity ： When the transaction is complete , The data must be in a consistent state
• Isolation, ： All concurrent transactions that modify data are isolated from each other
• persistence ： After the transaction completes , Changes to the database are permanently saved

Four problems brought about by transactions ：

• Missing changes ： Business A Read a data , Simultaneous transaction B Also read this data , Business A Modify submit ,B Also modify the submission , hold A The modified data covers .
• Dirty reading ： Business A Modify a data but haven't submitted it yet , Business B Read this data , Then transaction A Operation error reporting , Rolled back . Business B What you read is dirty data
• It can't be read repeatedly ： Business A Read a data , It's not over yet , Business B Modified this data , Cause transaction A Read this data again （ That is, between two readings ） It may not be the same .
• Fantasy reading ： Business A Read a few lines of data , Then business B Inserted data , In the subsequent query , Business A Query some data that does not exist .

Isolation level ：

• Read-Uncommitted（ Read uncommitted ）： Allow reading of uncommitted data , Dirty reading will occur 、 It can't be read repeatedly 、 Fantasy reading .
• Read-Committed（ Read submitted ）： Allow reading committed data in concurrent transactions , There will be non repeatable reading 、 Fantasy reading .
• Repeatable-Read（ Repeatable ）：Mysql Of InnoDb Default isolation level , Multiple reads of the same data are the same , There will be unreal reading .
• Serializable（ Serialization ）： The highest isolation level , It's completely in line ACID

5. Optimistic lock pessimistic lock

Pessimistic locking ：

• Every time I get the data, I think others will modify it , So every time I get the data, I lock it ,Java Medium synchronized and ReentrantLock Such exclusive locks are pessimistic locks .

Optimism lock ：

• Every time I go to get the data, I think other people won't modify it , So it won't lock , But in the process of updating, we will judge whether other people have updated this data during this period , You can use the version number mechanism and CAS Algorithm implementation .

6. The difference between threads and processes

• A process is the smallest unit of resource allocation , A thread is the smallest unit of program execution
• Process has its own independent address space , Every time a process is started , The system will allocate address space to it , Create data tables to maintain code snippets 、 Stack and data segments , Threads have no independent address space , It uses the same address space to share data .
• CPU Switching a thread costs less than a process
• Creating a thread costs less than a process
• Easier communication between threads , In the same process , Threads share global variables , Data such as static variables , Communication between processes needs to be in the form of communication （IPC） Conduct
• More secure multithreaded programs , The death of one process does not affect another process （ Because there's a separate address space ）, Multithreaded programs are harder to maintain , A thread dies , The whole process is dead （ Because shared address space ）
• The process requires a lot of resource protection , Spending big , Relatively inefficient , Thread resource protection requirements are not high , Low overhead , Efficient , It can switch frequently

7. Process of communication （ Five kinds ）

Interprocess communication （IPC）

a. The Conduit

It's usually an anonymous pipe , yes UNIX System IPC Oldest form
characteristic

• It's half duplex , It has fixed read end and write end
• It can only be used for communication between related processes （ It is also between parent-child processes or brother processes ）
• It can be seen as a special file , For its reading and writing, you can also use ordinary read、write Such as function . Only in memory .

b.FIFO

FIFO, Also known as named pipes , Is a file type
characteristic

• FIFO Data can be exchanged between unrelated processes , Different from the nameless channel
• FIFO There is a pathname associated with it , It exists in the file system as a special device file

c. Message queue

Message queue , It's a linked list of messages , Stored in the kernel . A message queue consists of an identifier （ That's the queue ID） To mark .
characteristic

• Message queuing is record oriented , The message has a specific format and a specific priority .
• Message queuing is independent of the occurrence and reception processes . When the process terminates , Message queues and their contents are not deleted .
• Message queue can realize random query of messages , Messages are not necessarily read in first in first out order , It can also be read by the type of message .

d. Semaphore

Semaphore （semaphore） With what has been introduced IPC Different structure , It's a counter . Semaphores are used to achieve mutual exclusion and synchronization between processes , Instead of storing interprocess communication data .
characteristic

• Semaphores are used for inter process synchronization , To transfer data between processes, you need to combine shared memory
• Semaphores are based on the PV operation , The operation of the program on semaphores is atomic operation .
• Every time the semaphore is PV The operation is not limited to adding... To the semaphore value 1 Or minus 1, And you can add and subtract any positive integer .
• Support semaphore group .

e. Shared memory

Shared memory （Shared Memory） , Refers to two or more processes sharing a given store .
characteristic

• Shared memory is the fastest IPC, Because processes access memory directly .
• Because multiple processes can operate at the same time , Therefore, process synchronization is required .
• Semaphore + Shared memory is usually used in combination , Semaphores are used to synchronize access to memory

8. How to start a thread

• Inherit Thread class ,implements Runnable Interface
• Realization Callable Interface by FutureTask Wrapper to create Thread Threads 、 Use ExecutorService、Callable、Future Implement a thread that returns a result

9.gc Algorithm , Heap memory model

gc There are four algorithms ： Copy algorithm , Mark clear , Tag to sort out , Generational collection .

Heap memory model ： private （ Program counter 、 Virtual machine stack 、 Native Method Stack ）, public （ Pile up 、 Method area 、 Runtime constant pool ）、 Direct memory

10. There are several ways to traverse binary tree , Oral sequence traversal

Four kinds of ： Before the order 、 Middle preface 、 follow-up 、 sequence , If recursive traversal is used, it will consume computer resources , You can use iteration

Sequence traversal generally uses queues 、 Or array assisted traversal

11. Quick line up , And its time complexity

Sort address

Time complexity ：O(n log n)

computer network

1.tcp Three handshakes

Answer address

2. Status code

1 Status code at the beginning ：（ Temporary response ） A status code that indicates a temporary response and needs to continue .

• 100（ continue ） The requester shall continue to make the request . The server returns this code to indicate that the first part of the request has been received , Waiting for the rest .
• 101（ Handover protocol ） Requestor has requested server to switch protocol , The server has confirmed and is ready to switch

2 Status code at the beginning ：（ success ） A status code that indicates that the request was successfully processed

• 200（ success ） The server has successfully processed the request , Usually , This means that the server provides the requested web page
• 201（ Created ） The request succeeded and the server created a new resource

3 Status code at the beginning ：（ Redirect ） Indicates that the request is to be completed , Need further operation . Usually , These status codes are used to redirect .

• 300 ( Multiple choice ) Request for , The server can perform many operations . The server can (user agent) Select an action , Or provide a list of actions for the requester to select .
• 304 ( not changed ) Since last request , The requested page has not been modified . When the server returns this response , Page content will not be returned .

4 Status code at the beginning ：（ Request error ） Indicates that the request may be in error , Hinders server processing

• 403（ prohibit ） Server rejects request
• 404（ Not found ） The server could not find the requested page

5 Start status code ：（ Server error ） Indicates that the server encountered an internal error while trying to process the request .

• 500（ Server internal error ） Server encountered an error , Unable to process request
• 504 ( gateway timeout ) Server as gateway or proxy , But the request was not received from the upstream server in time .

3.TCP,UDP The difference between

• TCP Connection oriented （ Contact before transferring data ）,UDP It's disconnected , There is no need to establish a connection when sending data
• TCP Provide reliable service , Data transmission is error free , No loss , And arrive in order ,UDP Do your best to deliver , That is, there is no guarantee of reliable delivery .
• UDP It has better real-time performance , Work efficiency ratio TCP high , Suitable for broadcast communication
• TCP Can only 1 Yes 1,UDP Sure 1 Yes 1、1 For more than
• TCP There are many requirements for system resources ,UDP There are few requirements for system resources

Algorithm problem

1. Merge two arrays NC22

Reference force deduction question

	void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    
        int last=m+n-1;
        while(n){
    
            if(m==0||nums1[m-1]<nums2[n-1]){
    
                nums1[last--]=nums2[--n];
            }else{
    
                nums1[last--]=nums1[--m];
            }
        }

    }