preface

Hello, everyone, I am your old friend Qingge. Recently, a fan wrote me a message about his miserable experience in the interview, saying that he will soon graduate. Many of his classmates have found satisfactory offers, but he was very miserable in the interview.

IT turned out that he majored in automation, but IT was really difficult to find a job in his major, so he turned his eyes to the hot industry: computer. On the one hand, the salary was high, on the other hand, he felt IT was very respectable (I don’t know where to start with this, we are helpless and miserable code farmers).

I asked him if he had prepared well for the interview. (I guess he wasn’t prepared)

Sure enough, he said that he only read a little basic Knowledge of Java (very weak), did a real project to imitate Tmall, hurried to the interview, in the process of the interview was asked about algorithms, data structures, completely confused, the last few rounds of defeat, returned to school in disgrace.

Seeing that the students got satisfactory offers one after another and began to go out to dinner to celebrate, he did not dare to follow them for fear of losing face.

Based on this fan’s embarrassing situation, I decided to draft a popular science article on the basis of computer science. Don’t look down upon these foundations, in the process of the interview, the computer foundation is the focus of the investigation of the goal, the more big factory, the more important is that your foundation is solid, can say that the foundation determines how far you can go in the way of coding. I don’t know if you were asked about algorithms during the interview. The interviewer will give you a logical algorithm question and ask you to write by hand, or ask you some questions about data structure and ask you to give a reasonable data storage solution. So how can you prepare enough knowledge to make yourself comfortable in an interview?

Today we are going to talk about algorithms and data structures. Of course, due to my limited personal level, there may be some unreasonable or careless mistakes in the article. I hope you can point them out when you see them, so that we can make progress together.

Program = algorithm + data structure

There is a formula in Teacher Zou Xin’s “Method of Construction” :

Program = algorithm + data structure

Program is based on some or some data structure, using some algorithm or some algorithms to solve the problem process.

To go grocery shopping to go grocery shopping

  1. Choose dishes
  2. weighing
  3. pay
  4. The deal

In the above example, dishes and money are data, and “how to finish buying vegetables” is the algorithm of this program. There are countless examples in our daily lives that can be explained by programs like this, but we rarely think about it consciously, but it shows how algorithms and data structures can profoundly affect our lives.

So let’s break it down. What is an algorithm? What is a data structure?

algorithm

The English word of algorithm is: algorithm, which is a very old concept. In ancient China, there was a collection of algorithm “Nine Chapters suanshu”. In the field of mathematics, algorithm is the formula and idea to solve a certain kind of problem.

There are efficient algorithms and there are bad ones. For example, we calculate 1+2+3+4+… Plus 10,000, if we go through each of these, how much time does it take? Maybe from dawn till dark. But another way to think about it is to break it down into the following formula:

1 + 10000 = 10001

2 + 9999 = 10001 3 + 9998 = 10001… 5000 + 5001 = 10001

1+2+3+4+… +10000 has 5000 items 10001, and the extraction formula is:

(1+10000) × 10000 ÷ 2 = 5005000

Now many people know this classical algorithm. It actually takes advantage of the law of arithmetic sequence. It saves time and effort to get the result easily.

The quality of an algorithm is usually measured in the following two aspects:

  • Time complexity: Indicates the time spent executing the current algorithm
  • Space complexity: How much memory is required to perform the current algorithm

Time complexity

To calculate the time complexity, we usually estimate the number of operational units of the algorithm, and each unit runs for the same amount of time. Therefore, the total running time and the number of operation units of the algorithm differ by at most a constant coefficient.

Different input values of the same size may still cause different running time of the algorithm, so we usually use the worst-case complexity of the algorithm, denoted by T(n), defined as the maximum running time required for input N of any size.

Big O: big O plus () is a function f(), O(f()), which shows the relationship between the time/space consumed by an algorithm and the growth of the data.

Common calculation types of several algorithms are as follows:

  • Time complexity O(1) :

The most common HashMap we use to query data is the typical O(1) algorithm, which can find the target after one calculation regardless of the size of the data (without considering hash conflicts).

  • Time complexity O(n) The multiple of the increase of data is the same as the multiple of the increase of time. Generally, the commonly used traversal calculation method is O(n).

  • O(n ^ 2) for example, bubble sort requires n times n times, so it’s O(n).

  • Time complexity O(logn) When the amount of data increases by n times, the time required increases by logn times. Binary search is a typical O(logn) algorithm, eliminating half the possibilities each time.

Spatial complexity

The spatial complexity of the algorithm refers to the amount of computer resources such as memory and CPU.

  • Space complexity O(1)

If the temporary space required for algorithm execution does not change with the size of a variable N, that is, the space complexity of this algorithm is a constant, which can be expressed as O(1).

int i = 1;
int j = 2;
int m = i + j;
Copy the code

The space allocated by the variables in the above code is already defined at the beginning, so its space complexity is O(1).

  • Space complexity O(n)

In a program structure such as a loop, if each loop initializes a new variable, the space complexity is O(n).

for(int i = 1; i < n; i++) {
   int j = i;
}
Copy the code

The above is the basic analysis of the time complexity and space complexity of the algorithm.

The data structure

After analyzing the algorithm, let’s look at the data structure.

Data structure is the cornerstone of algorithms. Without the support of data structure, the best algorithms are useless.

Common data structures are summarized as follows:

An array of

An array is a structure in which multiple elements can be stored consecutively in memory and allocated consecutively in memory. The elements in an array are accessed by array subscripts, which start from 0. It is a linear data structure.

Advantages:

  1. Querying elements by index is fast
  2. It is convenient to traverse a number group by index

Disadvantages:

  1. Once the array is fixed in size, it cannot be expanded
  2. An array can store only one type of data
  3. Add and delete operations are slow because other elements need to be moved.

Application scenario: Frequent query but little data is added or deleted, requiring little storage space.

The list

A linked list is a discontinuous, non-sequential storage structure on a physical storage unit. The logical order of data elements is realized by the pointer address of the linked list. Each element contains two nodes, one is the data domain (memory space) where the element is stored, and the other is the pointer domain pointing to the address of the next node.

According to the point of the pointer, linked lists can form different structures, such as single linked lists, bidirectional linked lists, circular linked lists, etc.

Advantages:

  1. Linked list is a very common data structure, no need to initialize the capacity, can arbitrarily add and subtract elements;
  2. When adding or deleting an element, you only need to change the pointer field of the node before and after the element to point to the address, so it is quick to add and delete.

Disadvantages:

  1. Because it contains a large number of pointer fields, it occupies a large space.
  2. Finding elements requires traversing the linked list to find them, which is time-consuming.

Application scenario: A small amount of data needs to be added frequently and deleted.

The tree

Tree is a relatively complex data structure, of which the more representative is binary tree, binary tree derived from binary heap data structure.

Tree is a kind of data structure, which is composed of N (N >=1) finite nodes to form a set with hierarchical relationship. It’s called a tree because it looks like an upside-down tree, meaning it has roots up and leaves down.

Tree characteristics:

  • Each node has zero or more child nodes;
  • A node without a parent is called the root node.
  • Each non-root node has one and only one parent;
  • In addition to the root node, each child node can be divided into multiple disjoint subtrees.

Binary tree is a special kind of tree, which has the following characteristics:

  • Each node has at most two subtrees, and the degree of each node is at most two.
  • The left and right subtrees are ordered and cannot be reversed.
  • Even if a node has only one subtree, you have to distinguish between the left and right subtrees.

Binary trees add and delete elements quickly, and there are a lot of algorithm optimization in the search aspect, so, binary trees have both the benefits of linked list, but also have the benefits of array, is the optimization scheme of both, in the processing of large quantities of dynamic data is very useful.

Binary tree has a lot of extended data structure, including balanced binary tree, red black tree, B+ tree, etc., these data structure binary tree derived on the basis of a lot of functions, widely used in practical applications, such as mysql database index structure is B+ tree, and HashMap of the underlying source code used in the red black tree. If we want to thoroughly understand binary trees and their derived data structures, we need to continue to study in depth.

Hash table

A hash table, also known as a hash table, is a data structure that is accessed directly by key and value. The key and value are mapped to a location in the set, so that the corresponding elements in the set can be found quickly.

Some set classes in Java are constructed based on hash principles, such as HashMap and HashTable, etc. It is very convenient to find elements of the set by using the advantages of hash table. However, because hash table is a data structure derived from array, it is relatively slow in adding and deleting elements.

The heap

A heap is a special data structure that can be viewed as an array object of a tree with the following properties:

  • The value of a node in the heap is always no greater than or less than its parent;
  • The heap is always a complete binary tree.

The heap with the largest root node is called the maximum heap or large root heap, and the heap with the smallest root node is called the minimum heap or small root heap.

figure

Graph is a very complex data structure, which is generally used to represent the association of multiple pairs.

At the end

Above is this period to bring you a simple introduction to the algorithm + data structure, here is mainly to throw a brick to introduce a piece of advice, I hope students through this article to realize their own weaknesses in knowledge, targeted to learn and summarize the algorithm, data structure related knowledge points. If you can speak well in an interview, I’m sure the interviewer will respect you.

As for the algorithm, I recommend you to go to leetcode website, where many of the original algorithm questions of big factories come from. If you finish the questions here, you will have no problem in the interview. The website is leetcode-cn.com/

As for data structures, I also recommend a website for you to learn: visualgo.net/zh

The algorithm can be visualized here, which can help us intuitively understand the operation process of the algorithm and deepen the understanding of the algorithm and data structure.

I am programmer Qingge, a programmer who loves life and sharing 😜

Thank you for your reading, creation is not easy, I hope you can give me a three-punch support I a wave 🤩 at the same time you are welcome to pay attention to my original public number Java learning guide, we can blow boast force, talk about the ideal 😆