preface

This post was submitted by a fan who came to ByteDance on June 9, the day before yesterday. He shared some interview questions and I put them together in the hope that they will be helpful to you.

Let’s take a look at what he was asked

  • To introduce myself
  • Look, there’s a deadlock on your resume. Can you tell me a little bit about it? Change your code to deadlock free?
  • What about system calls?
  • Process thread difference?
  • How many ways can processes communicate? What’s the fastest way? Why is that?
  • How are processes allocated? What’s in the PCB? Why do process context switches consume a lot of resources?
  • Process scheduling algorithm?
  • So you said zero copy, what’s the process?
  • Talk about data structures you use
  • What tree structures do you know? What are their characteristics? (Search tree, balanced tree, red black tree, B tree, B+, Hoffman)
  • Let’s talk about red black trees
  • Greedy strategy proof for Huffman tree algorithm.
  • You said that stacks and queues can be converted to each other to write code.
  • Talk about common sorting algorithms
  • Quick fix? How to avoid it? Rip the top 3 algorithms?

There are two more rhetorical questions:

  • What else do I need to work on?
  • What new skills do I need to learn if I can participate in project development?

In addition to these, I have also compiled some real interview questions for other big companies

Can share to you, the need for friends can directly click on the first line of large factory interview questions collection portal can be claimed

Answer key

Ok, now let’s look at these questions one by one

1. Introduce yourself

Although everyone is prepared for the interview, it is not easy to make an impressive introduction. Some people even don’t pay attention to it and only want to impress the interviewer with their skills. Of course, if it is really a great skill, it should be no problem.

What is an interview?

It is an opportunity for the interviewer to further confirm that you are the person they are looking for, and for you to further demonstrate your communication skills.

So

Remember, you’re dealing with people, not answering questions to a machine!

First of all, why would an interviewer ask this question? Isn’t it clear and detailed in the resume?

Well, according to many interviewers, giving the interviewer a cushion of time to reacquaint himself with your resume is a good idea.

So, by introducing yourself, we remind the interviewer of your characteristics and why you are particularly suitable for the position. Of course, the language should be as concise as possible. After consulting with some experienced interviewers, I have summarized the three main points of the interview for your reference.

Keep it to one minute and it will be 120-160 words on paper:

  • Who am I
  • My three highlights, most relevant recent experience?
  • Why do I want this job?

These three points can be expressed in concise language and the introduction part is basically fine.

2. How to solve deadlock

Deadlock resolution generally has four stages, i.e

  • Deadlock prevention
  • Deadlock avoiding
  • Deadlock detection
  • Deadlock relieve

Deadlock prevention: Breaking any of the conditions necessary to cause deadlocks can prevent deadlocks.

Such as:

(1) Destruction of possession and waiting conditions: apply for all resources at one time, and then do not apply for resources again. If the resource conditions are not met, resources will not be allocated.

(2) Destruction of the inalienable condition: when a process obtains a certain inalienable resource, it puts forward a new resource application. If it fails to meet the requirement, all resources will be released.

(3) Break the cycle waiting condition: rank the resources and apply for the resources in ascending order. If a resource with a higher id wants to apply for a resource with a lower ID, the resource with a higher ID needs to be released first.

Deadlock avoidance: The process determines whether these operations are safe each time a resource is requested.

Such as:

Using the banker algorithm: it is necessary to check whether a resource allocation will cause a system deadlock before allocating it. If it is deadlocked, it is not allocated, otherwise it is allocated.

Deadlock detection: Determines whether the system is in a deadlock state. If yes, a deadlock release policy is executed.

Deadlock release: Forcibly reclaim resources occupied by a process and allocate them to other processes. (used in conjunction with deadlock detection)

3. System call

In the user programs that we run, all operations related to system-level resources (such as file management, process control, memory management, etc.) must be made to the OS through system calls and completed by the OS

Normally our processes are almost all user mode, read user data, when it comes to system operations, computer resources will use the system call

The functions of system call are roughly divided into

A system call does what it does — it involves operations on computer resources

  • Device management: Complete device request/release and device startup
  • File management: You can read, write, delete, and create files
  • Process control: Complete the process creation, cancellation, blocking and wake up functions
  • Memory management: Allocates and reclaims memory, and obtains the size and address of the memory occupied by a job

4, process thread difference

A process is an application that runs in memory. Each process has its own independent memory space. A process can have multiple threads. For example, in Windows, a running XX. exe is a process.

A thread is an execution task (control unit) in a process that is responsible for the execution of a program in the current process. A process has at least one thread. A process can run multiple threads, and multiple threads can share data.

Unlike the process heap of similar process are Shared by multiple threads and method of area resources, but each thread has its own program counter, the virtual machine and the local method stack, so the system in one thread, or switch between individual threads, burden is much smaller than the process, also because of this, thread, also known as a lightweight process.

5. Several ways of process communication

  • Pipe: A pipe is a half-duplex communication mode in which data flows only in one direction and can only be used between related processes. Process kinship usually refers to the parent-child process relationship.
  • Advanced piping (POPEN) : Start another program as a new process in the current program process, it is a child of the current program, this method is called advanced piping.
  • Named pipe: Named pipe is also a half-duplex communication mode, but it allows communication between unrelated processes.
  • Message queue: MESSAGE queues are linked lists of messages stored in the kernel and identified by message queue identifiers. The message queue overcomes the disadvantages of little signal transmission, pipe carrying only plain byte stream and limited buffer size.
  • Semophore: A semaphore is a counter that can be used to control access to a shared resource by multiple processes. It is often used as a locking mechanism to prevent other processes from accessing a shared resource while one process is accessing it. Therefore, it is mainly used as a means of synchronization between processes and between different threads within the same process.
  • Sinal: Signals are complex forms of communication used to inform the receiving process that an event has occurred.
  • Shared memory: A shared memory map maps a segment of memory that can be accessed by other processes. This shared memory is created by one process but can be accessed by multiple processes. Shared memory is the fastest IPC method and is specifically designed for the low efficiency of other interprocess communication methods. It is often used in conjunction with other communication mechanisms, such as signal two, to achieve synchronization and communication between processes.
  • Socket: A socket is also an interprocess communication mechanism. Unlike other communication mechanisms, it can be used to communicate between processes of different machines.

6. Process scheduling algorithm

Two scheduling algorithms based on process scheduling are as follows:

  • First come, first served (FCFS) scheduling algorithm
  • Short Job First (SJF) scheduling algorithm
  • Time slice rotation (RR) scheduling algorithm
  • Highest priority Priority scheduling algorithm
  • Multi-level feedback queue (MFQ) scheduling algorithm

Here space is limited, just talk about the first two kinds of bar, the rest if interested can find their own information

First come, first served (FCFS) scheduling algorithm

1. Introduction: First-come-first-served scheduling algorithm is one of the simplest scheduling algorithms, which can be used for job scheduling and process scheduling.

2. Principle: When the first-come-first-served algorithm is used in process scheduling, the first process to enter the queue is selected from the ready queue and the processor is assigned to it, that is, the one who queued first will be executed first.

3. Advantages:

Facilitate long operations (processes)

Favors CPU busy jobs (processes)

4. Disadvantages:

Not conducive to short work (process)

Bad for busy I/O jobs (processes)

Short Job First (SJF) scheduling algorithm

1. Brief Introduction: Short job (process) priority scheduling algorithm refers to the short job or short process priority scheduling algorithm, which respectively act on job scheduling and process scheduling. It is an optimized version of first-come-first-served scheduling algorithm.

2. Principle: The short process priority scheduling algorithm selects a process with the shortest estimated running time from the ready queue, and then allocates the processor to it until the execution is complete, while other processes generally do not beat the process that is being executed.

3. Advantages:

Algorithm is bad for long jobs (processes)

Failure to consider the urgency of the process

Due to the estimated running time, which is provided by the user, the algorithm may not be able to achieve short job first scheduling

Zero copy process

Here you see a picture should be understood, when the interview if encountered this question, use their own words can be

8. Common data structures

Just be honest about how you use them: arrays, linked lists, queues, stacks, trees, Hash tables, just name two or three.

Greedy strategy proof of Huffman tree algorithm

How to understand greedy algorithms?

Suppose we have a backpack that can hold 100kg items and can hold the following 5 kinds of beans. The total amount and total value of each bean are different. In order to maximize the total value of the items in the backpack, how do we choose which beans to carry in the backpack? How much of each type of bean?

Actually, we just need to figure out the unit price of each item first, and load it up in ascending order. Black beans, mung beans, red beans, green beans, yellow beans, so we can carry 20kg of black beans, 30kg of mung beans, 50kg of red beans in the backpack.

The solution to this problem is essentially a greedy algorithm. Combined with this example, summarized the steps of greedy algorithm to solve the problem:

The first step,

When we see this kind of problem, we should first associate with greedy algorithm: for a set of data, we define the limit value and the expected value, hoping to select a few data, in the case of satisfying the limit, the expected value is the largest. In the analogy of the previous example, the limit is that the total amount cannot exceed 100kg, and the expected value is the total value of the item. This set of numbers is 5 types of beans.

The second step,

Let’s try to see if we can solve this problem with a greedy algorithm: each time we select the data that contributes the most to the expected value, with the same amount of contribution to the limiting value. Just like the previous example, each time from the remaining beans, choose the highest unit price, that is, under the same weight, the most contribution to the value of the beans.

The third step,

In fact, greedy algorithms don’t always give you an optimal solution.

For example, in a weighted graph, we start from vertex S and find a shortest path to vertex T (the path has the lowest sum of weights for the edges). The greedy algorithm ends by selecting the smallest edge of the circle connected to the current vertex until it finds vertex T. In this way, find the shortest path: S->A->E->T, and the path length is 1 + 4 + 4 = 9. Obviously not the shortest, because the shortest is: S->B->D->T, and the total length is 2 + 2 + 2 = 6

The main reason why the greedy algorithm doesn’t work on this problem is that the first choice affects the second choice. So even if we choose the best way to go in the first step, it is possible that because of this step choice, every subsequent choice will be bad, and eventually the optimal solution will be eliminated.

Huffman code

Now let’s see how Hoffman coding uses greedy algorithms to achieve data compression coding, effectively saving data storage space

Suppose I have a file with 1000 characters and each character is 1 byte (1 byte = 8 bits). It takes 8000 bits to store 1000 characters. Is there a more space-efficient way to store them?

Suppose we find that the 1000 characters contain only six different characters. Let’s say they are a, B, C, D, E, and F. Three binary bits can represent eight different characters, so to minimize the storage space, each character is represented by three binary bits, for example: A (000), b (001), c (010), d (011), e (100), and f (101) require only 3000bits to store 1000 characters.

That’s where hoffmann code comes in. Huffman coding is a very effective coding method, widely used in data compression, its compression rate is usually between 20% ~ 90%.

Huffman coding looks not only at how many different characters there are in the text, but also at how often each character appears, choosing different lengths of code depending on the frequency. Huffman coding attempts to use this unequal length coding method to further increase the efficiency of compression.

How to choose different encoding lengths for characters with different frequencies? Based on greedy thinking, we can use slightly shorter encoding lengths for characters with more frequency; Use slightly longer codes for characters that occur less frequently.

For equal-length coding, compression is simple. For example, in that example, three bits represent one character. In the decompression process, three bits of binary are read from the text at a time, and then translated into the corresponding characters. However, the problem of whether Huffman codes are unequal in length, should be read one bit at a time, two bits at a time, three bits at a time, and so on, makes the decompression of Huffman codes more complicated. In order to avoid ambiguity in the decompression process, Hoffmann encoding requires that the encoding of each character is not prefixed by another encoding.

Assuming that the frequencies of the six characters from high to low was followed by a, b, c, d, e, f, we respectively coding them into this appearance, any a character encoding is not another prefix, at the time of decompression, each will be read as long as possible can extract the binary string, so there will be no ambiguity in the decompression. After this compression, only 2100bits are needed for 1000 characters.

Although the idea of Huffman coding is not hard to understand, how do you encode different characters at different lengths depending on how often they appear? It’s a little tricky here.

  • We treat each character as a node, with the accompanying frequency placed in the priority queue.
  • We take out the two nodes f (20) and E (30) with the lowest frequency from the queue.
  • Then create a new node x (50), set the frequency to the sum of the frequencies of the two nodes, and make this new node X (50) the parent of f (20) and E (30).
  • Finally, x (50) is placed in the priority queue. Repeat this process until there is no data in the queue.

  • Now let’s assign a weight to each edge, and we’ll mark all the edges to the left child as 0, and all the edges to the right child as 1, so the path from the root node to the leaf node is the Huffman code for the character corresponding to the leaf node.

Stack and queue conversion code

Implement queues with stacks

#pragma once #include "SqStack.h" class CQueue { public: CQueue(void); ~CQueue(void); CQueue(int size); void AppendTail(int e); int DeleteHead(); private: SqStack stack1; SqStack stack2; }; #include "StdAfx.h" #include "Queue.h" #include "SqStack.h" #include<iostream> using namespace std; CQueue::CQueue(void) { } CQueue::~CQueue(void) { } CQueue::CQueue(int size) { stack1.stacksize = stack2.stacksize = size; stack1.top = stack1.base = new int[size]; stack2.top = stack2.base = new int[size]; } void CQueue::AppendTail(int e) { stack1.Push(e); } int CQueue::DeleteHead() { int a, b; if(stack2.GetSize() == 0) { while(stack1.GetSize() ! = 0) { a = stack1.Pop(); stack2.Push(a); } } if(stack2.GetSize() == 0) { cout<<"queue is empty"<<endl; return -1; // Return -1} else {b = stack2.pop (); // Return -1} else {b = stack2.pop (); return b; } } #pragma once class SqStack { public: SqStack(void); ~SqStack(void); SqStack(int size); void Push(int e); int Pop(); int GetSize(); public: int stacksize; int* base; int* top; }; #include "StdAfx.h" #include "SqStack.h" #include<iostream> using namespace std; SqStack::SqStack(void) { } SqStack::~SqStack(void) { } SqStack::SqStack(int size) { stacksize = size; base = top = new int[size]; } void SqStack::Push(int e) { *top = e; top++; } int SqStack::Pop() { int e; If (top == base) {cout<<" empty "<<endl; } e = *--top; return e; } int SqStack::GetSize() { if(top == base) return 0; else return 1; } #include "stdafx.h" #include "Queue.h" #include "SqStack.h" #include<iostream> using namespace std; int main() { int a, b, n; CQueue c(10); Cout <<" Please enter the number of queue elements "<<endl; cin>>n; Cout <<" Please enter queue elements "<<endl; for(int i = 0; i < n; ++i) { cin>>a; c.AppendTail(a); } b = c.DeleteHead(); cin>>a; c.AppendTail(a); b = c.DeleteHead(); b = c.DeleteHead(); b = c.DeleteHead(); cout<<b<<endl; system("pause"); return 0; }Copy the code

Implement stacks with queues

#pragma once class CQueue { public: CQueue(void); ~CQueue(void); void InitCQueue(); int QueueLength(); void EnQueue(int e); int DeQueue(); public: int* base; int front; int rear; }; #include "StdAfx.h" #include "Queue.h" #include<iostream> using namespace std; #define MAXQSIZE 10 CQueue::CQueue(void) { } CQueue::~CQueue(void) { } void CQueue::InitCQueue() { base = new int[MAXQSIZE]; front = rear = 0; } int CQueue::QueueLength() { return (rear - front + MAXQSIZE) % MAXQSIZE; Void CQueue::EnQueue(int e) {if((rear + 1) % MAXQSIZE == front) {cout<<" queue full "<<endl; return; } base[rear] = e; rear = (rear + 1) % MAXQSIZE; return; } int CQueue::DeQueue() { int e; If (front == rear) {cout<<" queue empty "<<endl; //return; } e = base[front]; front = (front + 1) % MAXQSIZE; return e; } #pragma once #include "Queue.h" class SqStack { public: SqStack(void); ~SqStack(void); SqStack(int size); void Push(int e); int Pop(); private: CQueue cqueue1; CQueue cqueue2; }; #include "StdAfx.h" #include "SqStack.h" #include "Queue.h" #include<iostream> using namespace std; SqStack::SqStack(void) { } SqStack::~SqStack(void) { } SqStack::SqStack(int size) { cqueue1.InitCQueue(); cqueue2.InitCQueue(); } void SqStack::Push(int e) { cqueue1.EnQueue(e); } int SqStack::Pop() { int a; If (cqueue1.queuelength () == 0 && cqueue2.queuelength () == 0) {cout<<" stack empty "<<endl; //return ; } else if(cqueue1.QueueLength() ! = 0) { while(cqueue1.QueueLength() ! = 1) { a = cqueue1.DeQueue(); cqueue2.EnQueue(a); } a = cqueue1.DeQueue(); return a; } else if(cqueue1.QueueLength() == 0 && cqueue2.QueueLength() ! = 0) { while(cqueue2.QueueLength() ! = 1) { a = cqueue2.DeQueue(); cqueue1.EnQueue(a); } a = cqueue2.DeQueue(); return a; } } #include "stdafx.h" #include "SqStack.h" #include "Queue.h" #include<iostream> using namespace std; int main() { int r; SqStack s(10); s.Push(1); s.Push(2); r = s.Pop(); cout<<r<<endl; s.Push(3); r = s.Pop(); cout<<r<<endl; r = s.Pop(); cout<<r<<endl; system("pause"); return 0; }Copy the code

summary

Space is limited, I will only talk about these ten questions, after all, there are too many interview questions, in addition to these, I also sorted out some other big factory interview questions, if necessary, you can directly click the first line of big factory interview questions collection portal to get

You can also post your interview questions in the comments section, and we’ll see you in the next article