# 20 classic data structures and algorithms, more than 300 hand-drawn algorithm diagrams, show you the beauty of algorithms

Some classic data structure and algorithm books focus on theory, and readers may feel boring to learn. Some interesting data structure and algorithm books are easy to read, but the content is often not comprehensive. In addition, many data structure and algorithm books lack real development scenarios, and it is difficult for readers to combine theory and practice.

It just so happens that such a book has just been published, which solves the above-mentioned problems.

# The beauty of data structure and algorithm (full-color printing)

The beauty of data structure and algorithm (full-color printing)

This book comprehensively and systematically explains commonly used and frequently tested data structures and algorithms, and combines more than 300 pictures and hundreds of codes to make the content easier to understand. At the same time, for each knowledge point, the book combines real application scenarios to explain, using a question and answer explanation mode, so that readers can not only master theoretical knowledge, but also how to apply data structures and algorithms to actual development work. in.

Former Google engineer algorithm interview and practical experience summary

One-stop service for algorithm learning, problem-writing, and interview, verified by more than 100,000 readers, tailored for job interviewers and engineers.

# Contents of this book

The book is divided into 11 chapters. Chapter 1 introduces the complexity analysis method.

Chapter 2 introduces the basic linear table data structures of arrays, linked lists, stacks, and queues.

Chapter 3 introduces recursive programming techniques, 8 classic sorts, binary search and variants of binary search.

Chapter 4 introduces hash tables, bitmaps, hash algorithms, and Bloom filters.

Chapter 5 introduces various data structures related to trees, including binary trees, binary search trees, balanced binary search trees, recursive trees, and B+ trees.

Chapter 6 introduces the heap and various applications of the heap, including heap sorting, priority queues, finding Top  K , finding the median, and finding the percentile.

Chapter 7 introduces more advanced data structures such as skip table, union search set, line segment tree, and tree array.

Chapter 8 introduces string matching algorithms, including BF algorithm, RK algorithm, BM algorithm, KMP algorithm, Trie tree and AC automata.

Chapter 9 introduces graphs and related algorithms, including depth-first search, breadth-first search, topological sorting, Dijkstra algorithm, Floyd algorithm, A* algorithm, minimum spanning tree algorithm, maximum flow algorithm, and maximum binary matching.

Chapter 10 introduces 4 algorithm ideas, including greedy, divide and conquer, backtracking and dynamic programming.

Chapter 11 introduces the application of data structures and algorithms in 4 classic projects, including Redis, search engine, authentication flow and short URL service. In addition, Appendix A is the answer to the thinking questions in each chapter

# Professional recommendation

The study of algorithms and data structures is an exercise in the reader's logical thinking ability. For programmers, the most important ability is the ability to solve problems. Learning algorithms and mastering the application of data structures can give readers a scientific way of thinking. Through the learning of algorithms and data structures, readers can not only improve their competitiveness in interviews, but also become more calm and confident in dealing with marginal and performance issues at work. This book starts with commonly used data structures and algorithms, and uses an explanation format combined with practical engineering problems, which can lead readers to systematically study and interpret these classic computer science knowledge.
——Zhang Yunhao (Hercy)
The difficulty of LeetCode's CEO algorithm lies in the use of programming languages ​​to develop sophisticated logic through appropriate data structures. To a certain extent, data structures and algorithms can be said to be the underlying logic of computer applications, and this book is a must-read book for us to learn this underlying logic. Let us experience the beauty of algorithms and data structures together through the study of this book.
——Ru Bingsheng Tencent T4 Expert
I am a subscriber to the author’s column. The feature of this book is the multi-level explanation of the algorithm, from the explanation of the basic knowledge of the algorithm to the practical implementation. If you are a beginner in algorithm knowledge, you can use it to get started; if you are a job seeker, you can use it to prepare for an interview.
—— Liu Chao, author of "Interesting Network Protocol" and "Interesting Linux Operating System"

# Appreciation of detailed catalog and layout

Chapter 1 Complexity Analysis 1
1.1 Complexity Analysis ( Part 1 ): How to analyze code execution efficiency and resource consumption 2
1.1.1 The significance of complexity analysis 2
1.1.2 Big O complexity notation 2
1.1.3 Time complexity Degree analysis method 4
1.1.4 Several common time complexity measurement levels 5
1.1.5 Space complexity analysis method 7
1.1.6 Content summary 7
1.1.7 Questions 8
1.2 Complexity analysis (Part 2): The best and the most detailed 4 types of time complexity: bad, average, and amortized 8
1.2.1 Best time complexity and worst time complexity 8
1.2.2 Average time complexity 9
1.2.3 Amortized time complexity 10
1.2.4 Summary of content 11
1.2 .5 Questions 12
Chapter 2 Arrays, Linked Lists, Stacks and Queues 13
2.1 Arrays ( Part 1 ): Why do the subscripts of arrays generally start from 0 and number 14
2.1.1 Definition of arrays 14
2.1.2 Addressing formulas and random access characteristics 15
2.1.3 Inefficient insertion and deletion operations 15
2.1.4 Beware of array access out-of-bounds issues 16
2.1.5 Can containers completely replace arrays 17
2.1.6 Answer the questions at the beginning of this section 18
2.1.7 Content summary 18
2.1.8 Thinking Question 18
2.2 Arrays (below): The difference between arrays in data structures and arrays in programming languages ​​19
2.2.1 The implementation of arrays in C/C++ 19
2.2.2 The implementation of arrays in Java 20
2.2.3 The implementation of arrays in JavaScript Method 22
2.2.4 Content Summary 23
2.2.5 Questions 23
2.3 Linked List (Part 1): How to implement the LRU cache elimination algorithm based on the linked list 23
2.3.1 The underlying storage structure of the
linked list 24 2.3.2 The definition and operation of the linked list 24
2.3.3 Deformation structure of
linked list 26 2.3.4 Performance comparison between linked list and array 28
2.3.5 Answer the questions at the beginning of this section 29
2.3.6 Content summary 29
2.3.7 Questions 30
2.4 Linked lists (below): Which techniques can be used to easily write linked lists Related complex code 30
2.4.1 Tip 1: Understand the meaning of pointers or references 30
2.4.2 Tip 2: Beware of pointer loss and memory leaks 30
2.4.3 Tip 3: Use "sentinels" to simplify the code 31
2.4.4 Tip 4: Pay attention to boundary conditions and special situations 33
2.4.5 Technique 5: Draw a picture with examples to assist thinking 34
2.4.6 Technique 6: Write more and practice, no shortcuts 34
2.4.7 Summary of content 34
2.4.8 Questions 35
2.5 Stack: How to achieve Browser's forward and backward functions 35
2.5.1 Stack definition 35
2.5.2 Sequential stack and chain stack 35
2.5.3 Sequential stack supporting dynamic expansion 36
2.5.4 Application of stack in function call 37
2.5.5 Application of stack in expression evaluation 38
2.5.6 Stack in parenthesis Application in matching 38
2.5.7 Answer the questions at the beginning of this section 39
2.5.8 Content summary 40
2.5.9 Questions 40
2.6 Queue: How to realize the request queuing function of limited resource pools such as thread pool 40
2.6.1 Definition of queue 40
2.6 .2 Sequential Queue and Chained Queue 41
2.6.3 Circular Queue 42
2.6.4 Blocking Queue and Concurrent Queue 44
2.6.5 Answering the Opening Question of this Section 44
2.6.6 Content Summary 45
2.6.7 Questions 45
Chapter 3 Recursion, Sorting and binary search 46
3.1 Recursion: How to find the "final recommender" with 3 lines of code 47
3.1.1 What is recursion 47
3.1.2 Three conditions that recursion needs to meet 48
3.1.3 How to write recursive code 48
3.1.4 Writing Difficulties of recursive code 49
3.1.5 Beware of stack overflow in recursive code 49
3.1.6 Beware of recalculation of
recursive code 50 3.1.7 Rewrite recursive code into non-recursive code 51
3.1.8 Answer the questions at the beginning of this section 52
3.1.9 Content Summary 52
3.1.10 Questions 52
3.2 Tail recursion: How to use tail recursion to avoid stack overflow caused by deep recursion 53
3.2.1 Reasons for stack overflow caused
by recursion 53 3.2.2 What kind of recursive code can be rewritten into tail recursion 54
3.2.3 Can tail recursion really avoid stack overflow? 54
3.2.4 Questions 55
3.3 Sorting algorithm basis: From which aspects to analyze the sorting algorithm 55
3.3.1 The execution efficiency of the
sorting algorithm 55 3.3.2 The memory consumption of the sorting algorithm 56
3.3. 3 Stability of Sorting Algorithm 56
3.3.4 Content Summary 57
3.3.5 Questions 57
3.4 O(n2) Sorting: Why Insertion Sort is More Popular than Bubble Sort 58
3.4.1 Bubble Sort 58
3.4.2 Insert Sort 60
3.4.3 Selection and sorting 62
3.4.4 Answering the opening questions of this section 63
3.4.5 Content summary 64
3.4.6 Questions 64
3.5 O(nlogn) sorting: how to quickly find the K-th largest element with the help of quick sorting 64
3.5.1 Merge The principle and realization of
sorting 64 3.5.2 The performance analysis of merge sorting 66
3.5.3 The principle and realization of
quick sorting 68 3.5.4 The performance analysis of quick sorting 70
3.5.5 Answer the questions at the beginning of this section 71
3.5.6 Content summary 72
3.5.7 Questions 72
3.6 Linear sort: How to sort 1 million users according to age 72
3.6.1 Bucket sort 73
3.6.2 Count sort 74
3.6.3 Cardinal sort 76
3.6.4 Answer the opening question 77
3.6.5 Content Summary 77
3.6.6 Questions 77
3.7 Sorting optimization: how to implement a high-performance general sorting function 78
3.7.1 How to choose a suitable sorting algorithm 78
3.7.2 How to optimize quick sort 79
3.7.3 Example analysis of sorting function 79
3.7.4 Summary of content 80
3.7.5 Questions 80
3.8 Binary search: how to use the most memory-
saving way to realize the fast search function 80 3.8.1 The ubiquitous binary idea 81
3.8.2 O(logn) amazing search speed 82
3.8.3 Recursive and non-recursive implementations of
binary search 82 3.8.4 Limitations of binary search application scenarios 83
3.8.5 Answer the questions at the beginning of this section 84
3.8.6 Content summary 85
3.8.7 Questions 85
3.9 Variations of binary search : How to quickly locate the attribution of the IP address 85
3.9.1 What is the binary search for variant problem 86
3.9.2 Variant question 1: Find the element whose first value is equal to the given value 86
3.9.3 Variant question 2: Find the element whose last value is equal to the given value 88
3.9.4 Variant question 3: Find the element whose first value is greater than or equal to the given value 88
3.9.5 Variant question 4: Find the element whose last value is less than or equal to the given value 89
3.9.6 Answer the beginning of this section Question 89
3.9.7 Content Summary 90
3.9.8 Questions 90
Chapter 4 Hash Table, Bitmap and Hash Algorithm 91
4.1 Hash Table ( Part 1 ): How to implement the word spell check function of Word software 92
4.1. 1 Hash Idea 92
4.1.2 Hash Function 93
4.1.3 Hash Conflict 93
4.1.4 Answer the opening question of this section 95
4.1.5 Content summary 95
4.1.6 Questions 96
4.2 Hash table (in): How to build An industrial-grade hash table 96
4.2.1 Design a hash function 96
4.2.3 Avoid inefficient expansion 98
4.2.4 Choose an appropriate conflict resolution method 99
4.2.5 Industrial Hash table example analysis 100
4.2.6 Answer the opening question of this section 100
4.2.7 Content summary 101
4.2.8 Questions 101
4.3 Hash table (below): How to use hash table to optimize LRU cache elimination algorithm 101
4.3. 1 LRU cache elimination algorithm 102
4.3.3 Content Summary 105
4.3.4 Questions 105
4.4 Bitmap: How to implement the URL link deduplication function in webpage "crawlers" 106
4.4.1 Hash table-based solutions 106
4.4.2 Bitmap-based solutions 106
4.4.3 Solution based on Bloom filter 108
4.4.4 Answer to the opening question of this section 110
4.4.5 Content summary 110
4.4.6 Questions 111
4.5 Hash algorithm: How to prevent the leakage of user information after the database is disconnected 111
4.5 .1 Introduction to Hash Algorithm 111
4.5.2 Application 1: Security Encryption 112
4.5.3 Application 2: Unique Identification 113
4.5.4 Application 3: Data Verification 113
4.5.5 Application 4: Hash Function 113
4.5.6 Application 5 : Load balancing 114
4.5.7 Application 6: Data slicing 114
4.5.8 Application 7: Distributed storage 115
4.5.9 Answer the opening question of this section 116
4.5.10 Content summary 116
4.5.11 Questions 116
Chapter 5 Tree 117
5.1 Trees and Binary Trees: What kind of binary trees are suitable for array storage 118
5.1.1 Tree definition 118
5.1.2 Binary tree definition 118
5.1.3 Binary tree storage 119
5.1.4 Binary tree traversal 120
5.1.5 Answer the questions at the beginning of this section 122
5.1.6 Content summary 122
5.1.7 Questions 122
5.2 Binary search tree: What are the advantages of binary search tree compared to hash table 122
5.2.1 Definition of binary search tree And operation 123
5.2.2 Binary search tree that supports repeated data 126
5.2.3 Performance analysis of binary search tree 126
5.2.4 Answer the question at the beginning of this section 127
5.2.5 Content summary 128
5.2.6 Questions 128
5.3 Balance two Fork search tree: why red-black tree is so popular 128
5.3.1 Definition of balanced binary search tree 128
5.3.2 Definition of red-black tree 129
5.3.3 Performance analysis of red-black tree 129
5.3.4 Answer the question at the beginning of this section 130
5.3.5 Content Summary 130
5.3.6 Questions 131
5.4 Recursion tree: how to find the time complexity of a recursive algorithm with the help of a tree 131
5.4.1 Recursive tree time complexity analysis method 131
5.4.2 Actual combat 1: The time complexity of quick sort Degree analysis 132
5.4.3 Actual combat 2: Fibonacci sequence time complexity analysis 133
5.4.4 Actual combat 3: Full array time complexity analysis 133
5.4.5 Content summary 135
5.4.6 Questions 135
5.5 B+ tree: How the MySQL database index is implemented 135
5.5.1 Typical requirements: Query by value and query by interval 135
5.5.2 Solution based on hash table and binary search tree 136
5.5.3 Solution based on B+ tree 136
5.5.4 Content summary 139
5.5.5 Thinking Question 140
Chapter 6 Heap 141
6.1 Heap: How to maintain the maximum value of dynamic collection 142
6.1.1 Definition of
heap 142 6.1.2 Heap storage 142
6.1.3 Insert elements into the heap 143
6.1.4 Delete top elements of the heap 144
6.1 .5 Delete any element 145
6.1.6 Heap performance analysis 145
6.1.7 Answer the opening question of this section 145
6.1.8 Content summary 146
6.1.9 Questions 146
6.2 Heap sort: Why is heap sort not faster than quick sort 147
6.2. 1 Building a Heap Sorting 147
6.2.2 Sorting Heap Sorting 149
6.2.3 Performance Analysis of Heap Sorting 149
6.2.4 Answering the Questions at the Start of this Section 150
6.2.5 Content Summary 150
6.2.6 Questions 151
6.3 Heap Application: How to quickly get Top 10 popular search keywords 151
6.3.1 Heap application 1: Priority queue 151
6.3.2 Heap application 2: Find Top K 152
6.3.3 Application of Heap 3: Finding the median and percentile 153
6.3.4 Answer the opening question of this section 155
6.3.5 Content summary 155
6.3.6 Questions 156
Chapter 7 Jump table, merge search, line segment Trees and tree arrays 157
7.1 Jump table: How the ordered collection type in Redis is implemented 158
7.1.1 The origin of the jump table 158
7.1.2 How fast is the jump table query 159
7.1.3 Is the jump table very fast? Waste of memory 160
7.1.4 Efficient insertion and deletion 161
7.1.5 Jump table index dynamic update 162
7.1.6 Answer the opening question of this section 162
7.1.7 Content summary 163
7.1.8 Questions 163
7.2 Consolidation : path compression and pressing Whether the two optimizations of rank merge conflict 163
7.2.1 The origin of the union search 163
7.2.2 The realization idea based on linked list 164
7.2.3 The realization idea based on tree 166
7.2.4 Content summary 168
7.2.5 Questions 168
7.3 Line segment Tree: How to find the K-ranked headhunter in Liepin.com 168
7.3.1 Interval statistical problem 169
7.3.2 Other applications of the line segment tree 172
7.3.3 Answer the opening question of this section 174
7.3.4 Content summary 174
7.3. 5 Questions 174
7.4 Tree array: How to implement a high-performance, low-latency real-time leaderboard 174
7.4.1 "Prefix sum" question 175
7.4.2 Comparison of tree array and line segment tree 177
7.4.3 Answer the question at the beginning of this section 177
7.4. 4 Summary of content 178
7.4.5 Questions 178
Chapter 8 String matching algorithm 179
8.1 BF algorithm: how to realize the search and replace function in programming language 180
8.1.1 Principle and realization of
BF algorithm 180 8.1.2 BF algorithm Performance analysis of 181
8.1.3 Answer the question at the beginning of this section 181
8.1.4 Content summary 182
8.1.5 Questions 182
8.2 RK algorithm: How to use hash algorithm to achieve efficient string matching 182
8.2.1 Principle and implementation of RK algorithm 182
8.2.2 Performance analysis of RK algorithm 183
8.2.3 Content summary 184
8.2.4 Questions 184
8.3 BM algorithm: How to realize the search and replace function in the text editor 185
8.3.1 The core idea of ​​BM algorithm 185
8.3.2 Principle analysis of
BM algorithm 186 8.3.3 Code implementation of
BM algorithm 188 8.3.4 Performance analysis of BM algorithm 192
8.3.5 Answer the questions at the beginning of this section 193
8.3.6 Content summary 193
8.3.7 Questions 193
8.4 KMP algorithm: How to understand KMP algorithm with the help of BM algorithm 194
8.4.1 Basic principles of KMP algorithm 194
8.4.2 Calculation method of failure function 196
8.4.3 Performance analysis of KMP algorithm 197
8.4.4 Summary of content 198
8.4.5 Questions 198
8.5 Trie Tree: How to Realize the Search Keyword Prompt Function of Search Engines 198
8.5.1 Definition of
Trie Tree 199 8.5.2 Code Implementation of
Trie Tree 200 8.5.3 Performance Analysis of
Trie Tree 201 8.5.4 Trie Tree and Hash Table and red-black tree comparison 202
8.5.5 Answer the questions at the beginning of this section 202
8.5.6 Content summary 203
8.5.7 Questions 204
8.6 AC automata: How to use multi-pattern string matching to achieve sensitive word filtering 204
8.6.1 Single-based Sensitive word filtering of pattern strings 204
8.6.2 Sensitive word filtering based on Trie tree 205
8.6.3 Sensitive word filtering based on AC automata 205
8.6.4 Performance analysis of AC automata 208
8.6.5 Content summary 209
8.6.6 Thinking Question 209
Chapter 9 Figure 210
9.1 Representation of a graph: how to store friend relationships in social networks such as Weibo and WeChat 211
9.1.1 Definition of graph 211
9.1.2 Storage method of adjacency matrix 212
9.1.3 The storage method of the adjacency list 213
9.1.4 Answer the opening questions of this section 214
9.1.5 Content summary 215
9.1.6 Questions 215
9.2 Depth-first search and breadth-first search: How to find out the third-degree friend relationship in social networks 216
9.2.1 What is a search algorithm 216
9.2.3 Depth-first search 219
9.2.4 Answer the opening question of this section 220
9.2.5 Content summary 220
9.2.6 Questions 220
9.3 Topological sort: how to determine Compilation dependencies of code source files 221
9.3.1 What is topological sorting 221
9.3.2 Using Kahn algorithm to realize topological sorting 222
9.3.3 Using depth-first search to realize topological sorting 222
9.3.4 Using topological sorting to detect loops 223
9.3.5 Answer Questions at the beginning of this section 224
9.3.6 Content summary 224
9.3.7 Questions 224
9.4 Single-source shortest path: How does the map software "calculate" the optimal travel route 225
9.4.1 Introduction to the shortest path algorithm 225
9.4.2 Principles and principles of Dijkstra's algorithm Realize 225
9.4.3 Performance analysis of
Dijkstra algorithm 228 9.4.4 Application of Dijkstra algorithm idea 228
9.4.5 Answer the question at the beginning of this section 229
9.4.6 Content Summary 230
9.4.7 Questions 230
9.5 Multi-source shortest path: how to use Floyd algorithm to solve the transitive closure problem 231
9.5.1 Principle and implementation of
Floyd algorithm 231 9.5.2 Performance analysis of Floyd algorithm 232
9.5.3 Using Floyd Algorithm to Solve Transitive Closure 232
9.5.4 Content Summary 233
9.5.5 Questions 233
9.6 Heuristic Search: How to Use A* Algorithm to Realize the
Wayfinding Function in the Game 233 9.6.1 What is the Suboptimal Route 234
9.6.2 Principle and implementation of
A* algorithm 234 9.6.3 Comparison between A* algorithm and Dijkstra algorithm 236
9.6.4 Answer the opening question of this section 237
9.6.5 Content summary 237
9.6.6 Questions 238
9.7 Minimal spanning tree: How to randomly generate games The maze map in 238
9.7.1 What is the minimum spanning tree 238
9.7.2 The principle and implementation of Kruskal's algorithm 239
9.7.3 The principle and implementation of Prim's algorithm 240
9.7.4 Answer the questions at the beginning of this section 242
9.7.5 Content summary 244
9.7 .6 Questions 245
9.8 Maximum Flow: How to Solve the Problem of Maximum Matching in Singles’ Dating Friendship 245
9.8.1 What is the Maximum Flow 245
9.8.2 Ford-Fulkerson Method 246
9.8.3 Edmonds-Karp Algorithm 247
9.8.4 Maximum Binary Matching 249
9.8.5 Solving the Opening Questions of this Section
249
9.8.6 Content Summary 249 9.8.7 Questions 250
Chapter 10 Greedy, Divide and Conquer , Backtracking, and Dynamic Programming 251
10.1 Greedy algorithm: How to use greedy algorithm to implement Huffman coding 252
10.1.1 How to understand greedy algorithm 252
10.1.2 Application examples of greedy algorithm 253
10.1.3 Answer the opening question of this section 255
10.1.4 Content summary 256
10.1.5 Questions 256
10.2 Divide and conquer algorithm: talk about the divide and conquer idea in the large-scale computing framework MapReduce 256
10.2.1 How to understand the divide and conquer algorithm 257
10.2.2 Application examples of the
divide and conquer algorithm 257 10.2.3 Divide and conquer algorithm in big data processing Application of 259
10.2.4 Answer the opening question of this section 259
10.2.5 Content summary 260
10.2.6 Questions 260
10.3 Backtracking algorithm: learn the core idea of ​​backtracking algorithm from the movie "Butterfly Effect" 260
10.3.1 How to understand backtracking algorithm 261
10.3.2 The Eight Queens Problem 261
10.3.3 The 0-1 Knapsack Problem 262
10.3.4 The Regular Expression Matching Problem 263
10.3.5 Summary of Content 264
10.3.6 Questions 264
10.4 First acquaintance with dynamic programming: How to cleverly solve the problem of collecting orders during the "Double 11" shopping 264
10.4.1 The learning route
of dynamic programming 265 10.4.2 Using dynamic programming to solve the 0-1 backpack problem 265
10.4. 3 The upgraded version of the 0-1 knapsack problem 269
10.4.4 Answer the opening question of this section 270
10.4.5 Content summary 271
10.4.6 Questions 272
10.5 Dynamic programming theory: a thorough understanding of the optimal substructure, no aftereffects and repeated substructures Question 272
10.5.1 "One Model and Three Features" Theory Introduction 272
10.5.2 "One Model and Three Features" Application Examples 273
10.5.3 Two Problem Solving Methods of Dynamic Programming 274
10.5.4 Four Algorithm Ideas Comparative analysis of 277
10.5.5 Summary of content 277
10.5.6 Questions 278
10.6 Dynamic programming: How to implement the spelling error correction function in the search engine 278
10.6.1 How to quantify the similarity of two strings 278
10.6.2 How to pass Calculate the Levinstein distance
by programming 279 10.6.3 How to calculate the longest common substring length by programming 281
10.6.4 Answer the opening question of this section 282
10.6.5 Content summary 283
10.6.6 Questions 283
Chapter 11 Data structure and algorithm combat 284
11.1 Actual Combat 1: Analyze the data structure corresponding to the common data types of
Redis 285 11.1.1 Introduction to Redis database 285
11.1.2 List 285
11.1.3 Hash 286
11.1.4 Set 286
11.1.5 Sorted set 287
11.1.6 Persistence of data structure 287
11.1.7 Summary and extension 288
11.1.8 Questions 288
11.2 Actual combat 2: Analysis of the classic data structure and algorithm behind search engines 288
11.2.1 Search The overall introduction of the engine system 288
11.2.2 Collection 289
11.2.3 Analysis 290
11.2.4 Index 292
11.2.5 Query 292
11.2.6 Summary and extension 293
11.2.7 Questions 293
11.3 Actual combat 3: Analysis of microservice authentication and limitations The data structure and algorithm behind the flow 293
11.3.1 Background of authentication 294
11.3.2 How to achieve fast authentication 294
11.3.3 Background of current limiting 297
11.3.4 How to achieve precise current limiting 297
11.3.5 Summary and extension 298
11.3 .6 Questions 299
11.4 Actual Combat 4: Use the learned data structures and algorithms to implement short URL services 299
11.4.1 The overall introduction of short URL service 299
11.4.2 Short URL generated by hash algorithm 299
11.4.3 Short URL generated by ID generator 302
11.4.4 Summary and extension 303
11.4.5 Questions 303
Appendix A Answers to Questions 304