A, takeaway

As far as I know, a lot of front-end programmers don’t have a clear understanding of the basic concepts of “data structures” and “algorithms,” which leads to a lot of people being put off by this section.

In fact, once you get a sense of what “data structures” and “algorithms” really mean, and some of the actual scenarios in which they can be used, you may become very interested in them. Of course, it will bring you considerable income.

Many front-end students will have some resistance after seeing “data structure” and “algorithm”, or they try to practice, but they are baffled and give up.

A big part of this is because you don’t know what it means to learn them, or you haven’t mastered proper practice.

In fact, when you have a certain purpose, and a reasonable method of practice, then learning this part of the content will be easy.

In this article, I’m going to share some of my experiences and methods for learning “data structures” and “algorithms.”

Later, I will also conduct a comprehensive review of all the common data structures and algorithm classifications.

1.1 Category Description

There are many kinds of data structures and algorithms. Taking trees as an example, the types of trees include: binary tree, B tree, B+ tree, Trie tree, red-black tree and so on. In this paper, only binary tree is selected.

For the front end, there is no need to know more about some of the more partial types and solutions, one is a waste of precious time, two is not much application.

The categories of data structures and algorithms selected in this paper are the most frequent and widely used categories.

1.2 Topic Description

In addition, it is very important to find the right typical questions when you do the problems, so that you can learn the knowledge more quickly and efficiently. The typical questions of each type are given later in this article for your reference.

Topic:

  • awesome-coding-js: my front-end algorithm open source project, including I have done the topic and detailed analysis
  • leetcode
  • The sword refers to offer

In addition, stay tuned for a long-term update of a column on front-end algorithms that will cover each type of data structure and algorithm in detail.

2. Why study data structures and algorithms

Before learning a piece of content, we must first know why we want to learn, rather than blindly follow the trend.

This will make it easier for you to benefit from the learning process and will give you motivation to study.

To be clear, learning data structures and algorithms doesn’t have to be about memorizing binary trees, heaps, stacks, queues, etc., and it doesn’t have to be about memorizing questions by rote. If you’re just scratching the surface, it’s going to be a pain in the ass.

2.1 Idea of problem solving

A computer is just a very cold machine, which can respond to whatever instructions you give it.

And the development engineer to do is how to translate the actual problem into computer instructions, how to convert, to look at the “data structure” classic statement:

Design the data structure and apply the algorithm.

So, it’s very important that data structures and algorithms are very important for building ideas about how to solve problems.

If Java is an automatic car, C is a manual jeep. What about data structures? It’s how the gearbox works. You can drive an automatic from A to B without knowing how the gearbox works, and not necessarily slower than someone who does. When it comes to programming, like driving a car, experience goes a long way, but if you don’t know how the bottom line works, you’ll never be able to drive a car. You won’t be able to fix a car, and you won’t be able to build one. If you’re not interested in either of those things, that’s fine, as long as you know how to use data structures. But if you want anything more than programming in this lifetime, data structures are a topic you can’t get around.

2.2 the interview

This is a very realistic point, and is why many front-end learning data structures and algorithms.

The general attitude towards algorithms falls into the following categories:

Google, Microsoft and other well-known foreign companies in the interview engineer, the algorithm is the decisive factor, front-end engineers are the same, the basic is every round will be examined, even if you have a very strong background, may also be because of one or two algorithm answer is not good and missed with such enterprises.

The second type, the algorithm is an important factor, some large domestic factories in the interview, will also take the data structure and algorithm as an important reference factor, the basic interview is a must, if you do not meet certain requirements, will directly fail.

The third category, bonus points, many companies will not put the data structure and algorithm as a hard requirement, but also symbolic out of some questions, when you put an algorithm question is very beautiful, this is definitely a bonus point.

So learning data structures and algorithms is very important if you want to move to a better company or get a higher salary.

How to prepare

Knowing the importance of data structures and algorithms, what’s the best way to prepare?

3.1 Comprehensive Understanding

Before learning and practicing, you must to do a comprehensive data structure and algorithm of the understanding and definition of data structures and algorithms, classification, a thorough understanding of, if this part is not good, what are you doing a problem will completely don’t know what you’re doing, and in the process of blind search for the answer, the process is very painful, and often little income.

In the later chapters of this article, I will do a comprehensive review of common data structures and algorithms.

3.2 Classification Exercises

Once you have an overall understanding of the data structure and algorithm, it’s time to practice.

Pay attention, it must be a classification exercise! Classification exercise! Classification exercise! It’s so important that it should be repeated for three times.

I have seen a lot of students with a warm heart to start to brush the problem, from the first problem of Leetcode, often very motivated at the beginning, may also send a circle of friends or boiling point 😅, and then nothing.

The first few questions are very easy, and may give you a certain amount of confidence. However, if you follow the serial number, you will soon encounter hard. Or some people, simply brush simple, first brush all the simple.

However, such blind brush, the effect is very poor, it is possible that you stick to it, brush hundreds of, also can have a little effect, but the whole process may be very slow, and the effect is far better than the classification exercise.

The so-called classification exercises, that is, practice by each category, for example: this time only practice binary tree problems, then start to practice backtracking algorithm problems.

Before you begin the exercise, you often need to have a detailed understanding of the specific category, including its specific definition, related concepts and applications, and possible topic types, before you begin.

3.3 Regular review and summary

After practicing a few problems for each type, you can see a pattern, some problems work this way, others work that way… This is a very normal phenomenon, there must be a certain pattern of each type of topic.

At this time you can begin to summarize this kind of problem, in view of this kind of problem, and its typical problem, the method of solving the problem, to summarize. The next time you run into this type of problem, you’ll be able to figure out how to solve it quickly.

So, when you see a problem, first you have to think about what kind of data structure or algorithm it belongs to, then you have to think about what kind of problem it is, and then you have to think about the solution to that problem.

If you can’t do this with a new problem, it means you don’t know enough about the problem, and you need to spend more time practicing.

Of course, I will share my summary in this part later, to help you less detours.

3.4 Choice of questions

As for the source of the topic, HERE I recommend to first read “Sword Point Offer”, then leetcode, “Sword Point Offer” can find a lot of typical topics, it is very important for you to find and summarize the rules. Check leetCode after reading it and you’ll find it easier.

As for the choice of difficulty, I suggest that leetCode should be simple and medium difficulty, because what we need to do is to look for patterns, that is, to master the typical problems. When you master these patterns, it is also possible to solve some hard problems, but it is just a matter of taking more time. Don’t spend too much time on tricky questions at first.

After the above method, after a period of practice, I can AC basic LeetCode medium difficulty problems within 20min. In addition, during the recent job-hopping process, I can write out almost all algorithm problems quickly, or think of the solution ideas quickly. I hope you can see my experience and approach to achieve the same effect, or do better than ME.

Time complexity and space complexity

Before we start, we need to understand the concepts of temporal and spatial complexity, which together determine the quality of a piece of code:

4.1 Time Complexity

The time complexity of an algorithm reflects the time it takes to run the program from start to finish. The time complexity of the algorithm is the number of times (frequency) that the basic operation is repeated.

There are no looping statements, called O(1), also called constant order. If there is only one cycle, the frequency of the basic operation of the algorithm increases linearly with the problem size n, which is denoted as O (n), also called linear order.

Common time complexities are:

  • O(1): Constant Complexity: Constant Complexity
  • O(log n)Logarithmic Complexity: Logarithmic Complexity
  • O(n): Linear Complexity: Linear time Complexity
  • O(n^2): N square Complexity Square
  • O(n^3): N square status
  • O(2^n): Exponential Growth
  • O(n!): Factorial Factorial

4.2 Space Complexity

The spatial complexity of a program is the amount of memory required to complete the program. Using the spatial complexity of a program, it is possible to predict how much memory is required to run the program.

In addition to the storage space and the instructions, constants, variables and input data used by a program, it also needs some units of work to operate on the data and some auxiliary space to store the information needed for real calculation.

5. Data structure

The term “data structure” is familiar to most of us, and may have heard it in many scenarios. But have you ever considered what a “data structure” is?

Data structure is a set of one or more specific relationships between data elements.

Generally you can think about it in two dimensions, the logical structure and the storage structure.

5.1 Logical Structure

To put it simply, logical structure is the relationship between data. Logical structure can be roughly divided into two kinds: linear structure and nonlinear structure.

Linear structure: is an ordered collection of data elements. The relationship between data elements is one to one, that is, except for the first and last data elements, all other data elements are end to end.

Common linear structures are: stack, queue, linked list, linear table.

– Non-linear structure: Data elements are no longer kept in a linear sequence. Each data element may be associated with zero or more other data elements.

Common nonlinear structures include two-dimensional arrays, trees and so on.

5.2 Storage Structure

Logical structure refers to the relationship between data, while storage structure is the realization of logical structure in computer language. Common storage structures include sequential storage, chain storage, index storage and hash storage.

For example, if an array is contiguous in memory, it belongs to sequential storage. The linked list is to establish the association between the data actively, but in memory is not necessarily continuous, it belongs to the chain storage; And the order and the logic doesn’t have an order, but you can put it in a hash table, a hash store of data in some way.

5.3 Data structure – Binary tree

A tree is used to simulate a collection of data with a tree-like structure. According to its characteristics, it can be divided into many kinds. For us, it is enough to master the structure of binary tree. It is also the simplest and most widely used kind of tree.

Binary tree is a typical tree – like structure. As its name suggests, a binary tree is a tree structure with up to two subtrees per node, usually referred to as “left subtree” and “right subtree”.

5.3.1 Binary tree traversal

Best of all, it’s best to master both the recursive and non-recursive versions. The recursive version is easy to write, but the non-recursive version that really examines the basics.

  • Binary tree in order traversal
  • Preorder traversal of a binary tree
  • Binary tree back order traversal

Reconstruct binary tree according to the characteristics of preorder traversal and in order traversal, reverse thinking, very interesting topic

  • Reconstruct the binary tree
  • Find the traversal of the binary tree

5.3.2 Symmetry of binary trees

  • Symmetric binary trees
  • Mirror image of a binary tree

5.3.3 Binary search tree

Binomial search tree is a special binomial tree, the topic of investigating binomial search tree is generally investigating the characteristics of binomial search tree, so it is very important to master its characteristics.

  1. If the left subtree of any node is not empty, then the value of all nodes in the left subtree is smaller than the value of its root node;
  2. If the right subtree of any node is not empty, then the value of all nodes in the right subtree is greater than the value of its root node;
  3. The left and right subtrees of any node are also binary search trees.
  • The KTH node of the binary search tree
  • A sequential traversal of a binary search tree

5.3.4 Binary tree depth

The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node.

Balanced binary tree: the difference between the left and right subtree depths is greater than 1

  • The maximum depth of a binary tree
  • The minimum depth of a binary tree
  • Balanced binary tree

5.4 Data structure – Linked list

Use an arbitrary set of storage cells to store the data elements of a linear table. An object stores its own value and the address of the next element.

  • Need to traverse to query elements, query slow.
  • Insert element simply disconnect and re-assign, insert fast.

Linked list is also a data structure often used in development. Fiber Tree formed by connecting Fiber nodes of React16 is a single linked list structure.

5.4.1 Basic Applications

It is mainly the application of the basic concepts and characteristics of the list. If the basic concepts are grasped firmly, this kind of problem can be easily solved

  • Print the list from end to end
  • Delete a node from the linked list
  • Reverse a linked list
  • Replication of complex linked lists

5.4.2 Ring questions

The problem of loop class is the problem of extending and deriving from judging whether there is loop in a single linked list

  • Circular linked list
  • The entry node of a linked list loop
  • Joseph ring

5.4.3 double pointer

The idea of double Pointers is often used in linked lists and arrays. It uses two or more Pointers in different positions to solve the problem by changing the speed and direction.

  • Two Pointers start at different positions: one at the beginning, the other at the end;
  • The two Pointers move at different speeds: one is faster and the other is slower.

For singly linked lists, since we can only traverse the list in one direction, the first scenario may not work. However, the second scenario, also known as the slow pointer and fast pointer techniques, is very useful.

  • A common node for two linked lists
  • The KTH node from the bottom of the list
  • Cross linked list

5.4.4 Bidirectional Linked List

Double-chained also has a reference field, called the PREv field. With this extra field, you know the node before the current node.

  • Flatten multilevel two-way linked list

5.5 Data structures – Arrays

An array is one of the most common data structures we see in development, a collection of elements that are stored sequentially. But elements can be randomly accessed, because each element in an array can be identified by the array index. Insert and delete to move the subsequent elements, but also to consider the expansion problem, the insertion is slow.

Arrays are very closely related to everyday business development, and how to use arrays wisely is the key to developing high-quality code.

5.5.1 double pointer

The above list mentioned a type of problems, mainly using two or more different positions of the pointer, through the change of speed and direction to solve the problem. Note that this technique is often used with sorted arrays.

  • Reorder the array so that an odd number precedes an even number
  • The sum is the two numbers of S
  • A sequence of consecutive positive integers whose sum is S

5.5.2 Sum of N numbers

Very common question, basically is a routine, the main consideration is how to reduce the time complexity than the violent profit method, but also will use the above double pointer technique

  • The sum of two Numbers
  • The sum of three number
  • The sum of four number

5.5.3 Two-dimensional arrays

Establish a certain abstract modeling ability, will be in the actual many problems abstract

  • Building a product array
  • Print the matrix clockwise

5.5.4 Data statistics

Arrays are all about statistics and computation, and this kind of problem examines how to do statistics on arrays in a more efficient way.

  • A number that appears in an array more than half its length
  • The largest sum of contiguous subarrays
  • Poker run
  • The first character that appears only once

5.6 Data structures – Stacks and queues

In the above array, we can access the elements randomly by indexing, but in some cases, we may want to restrict the order in which the data is accessed, so there are two data structures that restrict the order in which the data is accessed: stack (last in, first out) and queue (first in, first out).

  • Queue and stack implementation
  • The stack containing the min function
  • Stack push popup sequence
  • Maximum sliding window
  • After the rain

5.7 Data structure – Hash table

The basic principle of hashing is to retrieve records by converting a given key value to an offset address.

The conversion of keys to addresses is done by a relation (formula) called the hash function.

While hash tables are an effective search technique, they have some drawbacks. Two different keywords, with the same hash function value, are mapped to the same table location. This phenomenon is called conflict. The two conflicting keywords are called synonyms of the hash function.

How to design hash functions and how to avoid collisions is a common problem with hash tables. There are two criteria for choosing a good hash function:

  • 1. Simple and fast to calculate
  • 2. A uniform human distribution of keys in the address space

For example, the following topic:

  • Random elements are inserted, deleted, and retrieved in constant time

When we use a hash table, we usually need to create an extra space to record some calculated values, and we need to retrieve them quickly in the next calculation, such as the sum of two numbers, the sum of three numbers, and so on.

  • The sum of two Numbers
  • The sum of three number
  • The first non-repeating character in a character stream
  • Gems and Stones

5.8 Data structure-heap

The bottom of the heap is actually a full binary tree, which can be implemented as an array

  • Each node element value is not less than the child node – maximum heap
  • Each node element has a value no greater than its child node – the minimum heap

Heap can greatly reduce the time complexity of code when dealing with some special scenarios, such as finding the largest number or the smallest number in a large amount of data, you can use heap to complete this process.

  • Basic operations of the heap
  • The median in a data stream
  • The smallest k number

Six, algorithm

6.1 the sorting

Sorting is probably the front end of the most contact algorithm, a lot of people’s algorithm path from a bubble sort, there are a lot of sorting methods, they have their own application scenarios and advantages and disadvantages, here I recommend the following 6 most used sorting methods, if you are interested in can also study the other several.

  • Quick sort

Select a target value, smaller than the target value to the left, larger than the target value to the right, the position of the target value has been lined up, the left and right sides of the fast row.

  • Merge sort

Divide large sequence into small sequence, sort the small sequence and merge the sorted small sequence into large sequence.

  • Selection sort

Each sort takes the largest or smallest number and places it in the first ordered sequence.

  • Insertion sort

View the left-hand sequence as an ordered sequence and insert numbers one at a time into the ordered sequence. When inserting, start the comparison from the rightmost part of the ordered sequence, and move back one bit if the number is larger.

  • Bubble sort

Loop through the array, comparing the current element to the next, bubbling up if the current element is larger than the next. The next loop continues, not through the sorted numbers.

  • Heap sort

Create a big top heap, where the top of the heap must be the largest element. Swap the first and last elements so that the remaining elements continue to adjust to the large top heap. You go back and forth and swap this with the first element and rebuild, and you’re done.

6.2 Binary search

Search is one of the most basic and useful algorithms in a computer. It describes the process of searching for a particular value in an ordered collection.

Binary search maintains the left, right, and middle indicators of the search space and compares the search targets or applies search criteria to the intermediate values of the set; If the conditions are not met or the values are not equal, the impossible half of the target is cleared and the search continues on the remaining half until success is achieved. If the search ends with half empty, the condition cannot be met and the target cannot be found.

  • Two-dimensional array lookup
  • Rotates the smallest number in the array
  • Look up the number in the sort array
  • Square root of x
  • Guess the number size

6.3 the recursive

Recursion is an efficient way to solve a problem in which a function calls itself as a subroutine.

You might be wondering how to implement functions that call themselves. The trick is that every time a recursive function calls itself, it breaks down a given problem into subproblems. The recursive call continues until the point where the subproblem can be solved without further recursion.

To ensure that a recursive function does not result in an infinite loop, it should have the following properties:

  • A simple base case – a termination scheme that can generate an answer without recursion.
  • A set of rules, also known as a recursive relationship, breaks down all other cases into base cases.

6.3.1 Double Calculation

Some problems are considered recursively, the idea is clear, but recursion is not recommended, such as the following:

  • Fibonacci series
  • Dance steps
  • The rectangle cover

The common disadvantage of using recursion for these problems is that it involves a lot of double computation. If the recursion level is too deep, it will directly cause the JS process to crash.

You can avoid double counting by using memorization, which creates an extra space to store the values that have already been computed, but this will waste some memory space. Therefore, the above problems will generally be solved using dynamic programming.

Therefore, before using recursion, be sure to check if the code contains double counting, and if so, recursion is not recommended.

Recursion is an idea, not a type, and many classical algorithms are based on recursion, so I won’t give you any more questions here.

6.4 Breadth first search

Breadth-first search (BFS) is an algorithm that traverses or searches data structures, such as trees or graphs, and can also be used in more abstract scenarios.

The characteristic is that nodes that are closer to the root will be traversed earlier.

For example, we can use BFS to find the path from the start node to the target node, especially the shortest path.

In BFS, nodes are processed in exactly the same order as they were added to the queue, first-in, first-out, so breadth-first searches are generally implemented using queues.

  • Print binary trees from top to bottom
  • randomly
  • The Importance of employees
  • The number of islands

6.5 Depth-first search

Like breadth-first search, depth-first search (DFS) is an important algorithm for traversing/searching in trees/graphs.

Unlike BFS, nodes accessed earlier may not be nodes closer to the root. Therefore, the first path you find in DFS may not be the shortest path.

In DFS, nodes are processed in reverse order, just as they are added to the stack; it is last in, first out. So depth-first search is generally implemented using a stack.

  • Binary tree in order traversal
  • The maximum depth of a binary tree
  • Path to the combined
  • The curriculum
  • The number of islands

6.6 Backtracking Algorithm

The system selects a viable solution from all possible options at each step of the solution.

After selecting an option in one step, you go to the next step and are faced with new options. Repeat the selection until the final state is reached.

All options for the problem solved by backtracking can be represented in a tree structure.

  • There are n possible options in a step, which can be thought of as a node in the tree.
  • Each node option is viewed as a node line, reaching its n children.
  • Leaf nodes correspond to terminal states.
  • If leaf nodes satisfy the constraints, it is a feasible solution.
  • The leaf node does not satisfy the constraint, goes back to the previous node and tries other leaf nodes.
  • All the child nodes of the node do not meet the condition, and then go back to the previous node.
  • All the states do not satisfy the condition, the problem is unsolved.

Backtracking algorithms are suitable for problems that consist of multiple steps, and each step has multiple options.

  • The path to a value in a binary tree
  • Permutation of strings
  • Sum is n numbers of sum
  • Path in matrix
  • The range of motion of the robot
  • N Queen problem

6.7 Dynamic Planning

Dynamic programming is often the most effective problem type to investigate the algorithm and design ability, facing this kind of problems, the most important thing is to grasp the stage of the problem, understand the state of each stage, so as to analyze the relationship between the stages.

The problem applicable to dynamic programming needs to satisfy the optimal substructure and no after-effect. The solution process of dynamic programming is to find the state transition equation and solve it from the bottom up.

The bottom-up solution saves you a lot of complexity, such as the Fibonacci sequence above, which increases exponentially in time with recursion, whereas dynamic programming keeps the time of the algorithm at O(n).

6.7.1 Path Faults

  • Minimum path sum
  • Different paths
  • Different Paths II
  • The shortest path to form a string

6.7.2 Stock trading problems

  • The best time to buy and sell stocks
  • The best time to buy and sell stocks III
  • Al shabaab
  • Robbery II

Subsequence problem

  • Different subsequences
  • Maximum subsequence of product
  • Longest ascending subsequence
  • Longest echo subsequence

6.8 Greedy Algorithm

Greedy algorithm: when solving a problem, always do what seems to be the best approach at the moment.

The greedy algorithm applies to scenarios where the problem can be decomposed into subproblems and the optimal solution of the subproblems can be recurred to the optimal solution of the final problem. The optimal solution of the seed problem becomes the optimal substructure

6.8.1 Stock trading problems

  • The best time to buy and sell stocks II
  • The best time to buy and sell stocks includes fees

6.8.2 Currency selection

  • Change change
  • Change exchange II

6.9 Differences between greedy algorithm, dynamic programming, and backtracking

The difference between greedy algorithm and dynamic programming lies in that it selects the solution of each subproblem and cannot go back. Dynamic programming saves the previous operation results and selects the current one according to the previous results, which has the function of going back, while backtracking algorithm is a large number of repeated calculations to obtain the optimal solution.

There are many algorithmic problems that can be solved using these three ideas at the same time, but there is always a most suitable solution, which requires constant practice and summary to in-depth understanding in order to better choose a solution.

Vii. Front-end coding ability

This is the part that is most closely related to front-end development; while writing business code, we should also be concerned with the internal implementation of some class library or framework.

Most of the time, we don’t need to implement these wheels manually when writing business, but they are very important to a front-end programmer’s coding skills, and if you have a certain foundation in algorithms and data structures, a lot of source code looks very simple.

I have chosen some questions below:

  • Manually implement call, apply, bind
  • EventEmitter
  • Image stabilization
  • The throttle
  • Shallow copy and deep copy
  • Arrays are de-duplicated, flattened, and maximized
  • Array out-of-order – shuffle algorithm
  • The function is curialized
  • Implement JSONP manually
  • Simulate promise
  • Manually implement ES5 inheritance
  • Implement Instanceof manually

Eight, summary

Some of the pictures in this article are from the Internet, if there is infringement, please contact me to delete, thank you.

This article is not an in-depth analysis of each point, but a comprehensive analysis of the data structure and algorithm from the perspective of why, how and what to do (for the front end perspective). I hope that after reading this article, you can have the following help:

  • To establish a comprehensive cognitive system of data structure and algorithm
  • Grasp the method of fast learning data structure and algorithm
  • Understand the important classifications and classical question types of data structures and algorithms

If you want to learn more about data structures and algorithms, stay tuned for my next article.

Awesome coding-js: github.com/ConardLi/aw…

Feel free to correct any mistakes in the comments section, and if this post has helped you, feel free to like or follow.

For more great articles, you can follow me on github blog, and your star✨, like and follow is what keeps me creating!

I recommend you to follow my wechat public account [Code Secret Garden] and push high-quality articles every day. We communicate and grow together.

We are the r&d team of Bytedance Interactive Entertainment, including Douyin short video, Douyin Volcano version, TikTok, Faceu, Xiaoyan, cut and so on. As of January 2020, Douyin daily active users (DAUs) have exceeded 400 million, and continue to maintain high growth. You will support product development and related architecture, and each line of code will affect millions of users.

Class of 2021: DRZUM5Z

Website delivery: job.toutiao.com/s/JR8SthH