Huawei 2020 school recruitment written test programming questions read this article is enough (Part 2)

background

Continue with the background of the previous article , Keep looking. , First, send out another copy of the outline .

dried food （ Advanced part ）

1. Advanced data structure concept , Basic operation , And advantages and disadvantages, etc

1.1 Binary search tree

Simple questions

1. （ Symmetric binary tree ）
2. （ Balanced binary trees ）
3. （ Flip binary tree ）

Medium question

1. （ Middle order traversal of binary trees ）
2. （ Impassable binary search tree ）
3. （ Binary search book iterator ）
4. （ From binary search book to bigger and tree ）

---

1.2 Pile up

Simple questions

1. （ The... In the data stream K Big element ）
2. （ The weight of the last stone ）

Medium question

1. （ Sort the characters according to their frequency of occurrence ）
2. （ front K High frequency words ）
3. （ Refactoring strings ）

---

1.3 graph theory

Simple questions

1. （ Don't plant flowers next to each other ）
2. （ Find the judge in town ）

Medium question

1. （ Map analysis ）
2. （ The shortest path of color alternation ）

---

2. Common algorithms and ideas

2.1 Sorting algorithm （ Fast 、 Insert 、 Heap sort, etc ）

Simple questions

1. （ Relative sorting of arrays ）
2. （ Intersection of two arrays ）
3. （ Intersection of two arrays 2）

Medium question

1. （ Color classification ）
2. （ Merge range ）
3. （ Refactoring strings ）

---

2.2 iteration 、 The idea of recursion

Simple questions

1. （ The range of binary search tree and ）
2. （ The first N One tibonacci number ）

Medium question

1. （ The first K A grammatical symbol ）
2. （ Divided into k Equal subsets ）

---

2.3 The idea of partition （ Such as ： Two points search 、 Merge, sort, etc ）

Simple questions

1. （ Two points search ）
2. （x The square root of ）

Medium question

3. (Pow(x,y))
4. ( Search for a two-dimensional matrix )
5. （ Look for repetitions ）

---

2.4 search algorithm （ depth , Breadth ）

Simple questions

1. （ All paths of binary tree ）
2. （ Symmetric binary tree ）

Medium question

1. （ The sum of the paths II）
2. （ The level traversal of binary tree ）

---

2.5 Greedy Algorithm

Simple questions

1. （ The weight of the last stone ）
2. （ Play chips ）

Medium question

1. （ Rebuild the queue according to height ）
2. （ Task scheduler ）

---

2.5 Dynamic programming ( knapsack 0-1 difficulty )

Simple questions

1. （ climb stairs ）
2. （ The largest subsequence and ）

Medium question

1. （ Ugly number 2）
2. （ Different number of binary searches ）

---

appendix ： Blood spitting notes

Using data structures and algorithms

data structure ： character string 、 Array 、 Stack 、 queue （ Including priority queues 、 deque ）、 Linked list 、 Hashtable 、Set、 Binary tree . Priority queues can be used to solve the smallest and largest problems , I'm still a little dizzy about the adjustment of the heap .

Algorithm ： In front of the binary tree / in / In the following order / Level traversal ; Of Graphs BFS、DFS、 Shortest path algorithm 、 Minimum spanning tree ; to flash back 、 recursive 、 Dynamic planning, etc . The basic data structure of sorting algorithm has ready-made wheels , Just understand the principle .

The focus here is on the official examination scope .

about JAVA, Focus on the characteristics of several commonly used collection classes （ Is it orderly 、 What order 、 Is repetition allowed ）, In the process of solving problems, you can immediately think of which data structure a feature needs 、 Which class library .

Typical problem solving ideas summarized in the process of problem brushing （ Continuous brushing , If you have experience, please detour ）

1. Sliding window

Sliding window is a double pointer problem solving idea , use left、right Left and right hands , Represents the leftmost and rightmost ends of a sliding window （ initialization left = right = 0）. The left and right hands move in turn , Window size increases and decreases （ The window size can be fixed or dynamic , According to the title requirements ）, The window keeps sliding to the right , Finally, the best solution of the problem can be obtained in linear time . Sometimes topics need to be supplemented by HashMap、 Array to determine the existence 、 The feasibility of .

Recommended articles ： The sliding window

2. Linked list

The most basic operation of linked list ： establish 、 Insert 、 Deletion is a must .

The commonly used problem-solving method is mainly using the fast and slow pointer （ Only the lookup operation is involved ）、 Add auxiliary head node （ It involves adding, deleting and modifying ）, On this basis, how to judge whether the linked list has links and entry points 、 Intermediate nodes 、 Reciprocal K It is recommended to master the skills of solving problems . List questions must be drawn on white paper , Draw and write .

Recommended articles ： Linked list

3. Pictures

Recommend programmer Xiaohui 2019 Several posts about pictures in , It's very easy to understand

4. Binary tree

Binary tree feels no skill , It's good to have solid basic skills . The focus is on the front / in / In the following order / Sequence traversal ,LeetCode There will be some variants based on these , such as Z Font printing , Foreword and middle order , Recover binary tree from middle order and post order traversal , The finger of the sword offer And Xiaohui have typical explanations .

5. Retrospective method

Backtracking algorithm is a search attempt process similar to enumeration , According to the depth first search strategy , Starting from the root node, we explore the solution space tree , When a node is explored , We should first judge whether the node contains the solution of the problem , If you include , We will continue to explore from this node ; If the node does not contain the solution of the problem , Just “ to flash back ” return , That is, go back and choose again , Try another path .

If we use the backtracking method to find all the solutions of the problem , Go back to the root , And all feasible subtrees of the root node have to be searched all over before the end . And if we use the backtracking method to find any solution , As long as you find a solution to the problem, you can end it .

Adapt to the question type ： Complete permutation and combination

Templates ： I saw LeetCode There is a good template in , To be added .

6. Dynamic planning

Dynamic planning means that the next state can be based on the previous state , Or a reasoning process obtained from previous states . You can see the detailed dynamic planning —— Zou Bo talked about Dynamic Planning , It talks about the path 、 COINS 、 The longest subsequence .

Although I have been tested many times , I made seven or eight strokes , It is always dizzy to reason the state transition equation by yourself –#, Fortunately DP The problem that can be solved , There are other wheels that can be solved .

7. Bit operation

Bit operation is very basic , Typical bit operation skills and Applications , But they are seldom used in daily work , Wen guxia ： An operation