# Data structures and algorithms

## Linked list

- Linked list , Common interview questions have to write a linked list to delete a node algorithm 、 Single chain list reverse 、 Two linked lists look for intersecting parts , This usually has to be written completely without error ;
- Give the head node of two linked lists , Find out the intersection of these two linked lists .
- java The difference between arrays and linked lists in , Respective advantages How to design a linked list with efficient random reading ability （ Jump watch ） Design jump table , Hop table insertion overhead , Jump table random reading process
- Here's a one-way list , Make this list K reverse , for example k=3 1 -> 2 -> 3 -> 4 -> 5 -> 6 Reverse to ： 3 -> 2 -> 1 -> 6 -> 5 -> 4 The length of the list is guaranteed to be K Multiple
- Given a linked list , Return to the first node of the link where the list begins to enter
- n A list in descending order is returned K A list of large nodes
- List merge ： give n An ordered list , Combine them into an ordered list .
- Yes k An ordered single chain list , How to merge into an ordered single linked list ？
- Reverse order of linked list , You can't change the pointer , How to implement with recursion .
- Reverse single chain table
- Do you know how to flip a double linked list
- There are two numbers that are so big that they are beyond long The range of the type , Now it is stored as a linked list, where the chain header represents the highest bit , for example 1->2->3->4 Express 1234, Please design an algorithm to find the sum of two numbers ;
- Reverse the number , You can't turn numbers into strings
- The entrance of the chain list to find the ring
- The reverse order of a single linked list
- Two linked lists merge , The longest common substring problem
- Single chain table reverse order , Quick line up , The sum of two numbers in the array is equal to the target value

## Array

- stay M In an array of sizes K Large number （ The biggest pile ）
- I now have an array [1,2,3,4], Please implement the algorithm , Get the full array of this array , Such as [2,1,3,4],•[2,1,4,3].... What is the time complexity of your algorithm
- Array A,2*n Elements ,n An odd number 、n An even number , Design an algorithm , Make the array odd subscript positions are all odd numbers , Even subscripts are placed in even numbers • Let's talk about your ideas first • Next odd number ？ How to find ？ • Do you have any ideas ？ • You have a little time complexity , If required O(N) What to do
- Handwriting algorithm , The combination of two ordered arrays .
- 100000 lines of two-dimensional array , The length of each line is 10, Each array is in descending order , Find the biggest 15 Number . First, I talked to the interviewer , And then I wrote it on white paper
- An algorithm for sorting the absolute values of an array ;
- Non descending array , Print the last occurrence of a value
- Find more than half the number in the array （ Moore voted ）
- An array inversion ,o(logn) What sort algorithm does the complexity use ;
- One 100 Length array , Inside is Fixed random numbers , The optimal algorithm that requires a list of repeated numbers .;
- Given two arrays , Each array has duplicate numbers . No class library functions , Sort these two arrays .
- Given an array , Find all from subarrays of the array Remove all spaces in a string
- Given an array , The size of the element 0~25, There are repeating elements . Output all the numbers according to the frequency
- Given an out of order array , Find the largest continuous number in an array ;
- Unordered array to find k Large number
- Give an array , and k, The sum of the two numbers in the array is k, Except for the double deck for How else can loops and dictionaries be implemented ;

## lookup

- Write binary search algorithm
- There's a main string A, Substring B, stay A Search for B
- A binary search algorithm for tearing up an ordered array
- Please tell us the realization idea and space-time complexity of binary search .
- Use dichotomy to find a length of 18 Of , A line-up table , When the search fails , How many times do you need to compare

## Sort

- How to achieve the fast scheduling , Quick sort （ Including algorithm steps 、 Average algorithm complexity 、 The best and the worst ）
- 5 A large file of 100 million , How to arrange ？
- Two 1G File in order , Merge in order
- Sort by hand . Merge two ordered arrays .
- What are the common sorting algorithms ？ The average time complexity of various sorting algorithms and the worst-case time complexity ？
- Write a sort algorithm that you're familiar with , And explain its advantages and disadvantages
- Given a length of N An array of repeating elements , The output of the 10 Large number .
- Write a quick sort by hand , I think you've been to ACM, So use non recursion to implement .
- Have you heard of it ？ How did he achieve ？
- If it's a quick sort of a single linked list , How do you do ？
- Fast scheduling time and space complexity , The best, the worst , Optimization plan ？
- Handwritten bubble sort
- Handwritten recursive sorting, etc
- Two sorted arrays , Conceive of an algorithm that inserts one array into another in order
- Manual implementation of a quick sort algorithm
- List several sorting algorithms for data
- Quick sort ？ Is quicksort stable ？ How to achieve the stability of a quick sort ？
- Given a non empty array , Returns the third largest number in this array . If it doesn't exist , Then return the maximum number in the array . The time complexity of the algorithm must be O(n).
- Do you have a quick rehearsal ？ Do you know the principle ？
- Sorting algorithm , Let's introduce quick sort , Time complexity of quick sorting , Is it a stable sort , Introduce several stable sorting algorithms you know
- 10 Choose the largest of them K individual , In what way , How complicated
- Let's talk about the principle of bubble sort
- Yes, please. 3 Order arrays to merge and sort

## Trees

- AVL Trees and B The concept of tree 、 details , Like asking mysql The implementation principle of database index , Basically, it's like asking you B Trees .
- Red and black trees , This is basically a data structure that has to be asked , Including the concept of red and black trees 、 Average algorithm complexity 、 The algorithm complexity in the best and worst case 、 Spin around 、 Color change .
- Find the lowest common root node of any two nodes in the binary tree , If the tree is BST Well . Depth-first search + Binary search tree properties
- B+ How trees split ？
- Traversing the binary tree before, in, after Level traversal of binary tree Depth first traversal of binary tree ( recursive 、 Non recursive ) Traversing a binary tree first ( recursive 、 Non recursive ) And for n The binary tree path of The depth of the binary tree Is the binary tree symmetrical List reversal
- What are the characteristics of red and black trees ?
- Binary tree sequence traversal output , Each layer outputs an array （ Handwriting algorithm ）.
- JDK1.8 The characteristics of red and black trees adopted , And the reasons for adopting red and black trees instead of AVL and B The reason for the tree ？
- A binary search tree , Find the common ancestor of two nodes .
- Given a binary search tree , Find the nearest common ancestor of the two specified nodes in the tree . for example , Input : root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output : 6 explain : node 2 And nodes 8 The most recent public ancestor of 6. Example 2: Input : root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 Output : 2 explain : node 2 And nodes 4 The most recent public ancestor of 2, Because by definition, the nearest common ancestor node can be the node itself .
- The basic concept of balanced binary trees A brief introduction b+ Trees
- The generation of multitree Given an array 【[a,b]、[c,b]、[e,a]、[h,a]、[k,h]】, The first one in the array represents the child node 、 The latter represents the parent node , Generate a multi tree , Return root node
- according to Z The glyph traverses the binary tree hierarchically , requirement bug free, And construct a binary tree to test
- Right side view of binary tree .
- Write a depth traversal of a binary tree
- Binary tree flip
- Binary tree s Type traversal , A variety of sequence traversal , Simple , But write test cases , It is equal to writing an array to binary tree function
- A nonequilibrium binary tree , How to find the farthest two leaf nodes in the fastest way .
- Give a binary tree and a target value , Find all paths that are equal to and equal to this value
- B and B+ Trees ,B+ Number of tree searches 、 Why not use a binary tree .
- The worst rotation of red and black trees
- Given a binary tree , Find the closest common parent of two nodes (LCA). The most recent common ancestor is the common ancestor of two nodes and has the maximum depth . Suppose that the given two nodes exist in the tree .
- Hierarchical ergodic binary tree , Returns a two-dimensional array , Each line represents a layer of
- The height of the tree is not calculated iteratively ;
- Suppose that the postorder traversal sequence of a binary tree is DFGGEBHICA, The middle order traversal sequence is ：DBFEGAHCI, Then the preorder traversal sequence is ？
- The first of a multi tree n layer Level traversal 2. What happens if recursion is too deep ？ Answer stack overflow . Why stack overflow ？python Where is the temporary variable in the function ？ When it's deep , What happens with loops ？ Why not stack overflow ？
- Given a binary tree , Print out each line in turn
- The former sequence traversal In the sequence traversal After the sequence traversal Know what can restore binary trees , Is it OK to know only the pre order and the post order ？
- Yes N The height of a full binary tree of nodes

## other

- Hashtable , The details of hash table are very demanding , For example, hash table conflict detection 、 Hash functions are commonly implemented 、 Algorithm complexity ; For example, baidu two sides let me write a hash table insert element algorithm , The element type is any type .
- Find duplicate items in two ordered arrays , Analyze the complexity of time and space , And then there's constant optimization .. What happens if the array length is very large ？
- Both threads continue to print odd and even numbers, respectively , Realize the alternate printing of two threads （ From small to large ）
- Given an encoded string , Returns the decoded string . The coding rule is : k[encoded_string], Represents the encoded_string Just repeat k Time . Be careful k Positive integer guaranteed . You can think that the input string is always valid ; There are no extra spaces in the input string , And the square brackets entered always meet the format requirements . Besides , You can assume that the raw data does not contain numbers , All numbers only indicate the number of repetitions k , For example, there is no such thing as 3a or 2[4] The input of . Example : s = "3[a]2[bc]", return "aaabcbc". s = "3[a2[c]]", return "accaccacc". s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
- leetcode213 You are a professional thief , Plan to steal houses along the street , There is a certain amount of cash in every room . All the houses in this place are in a circle , This means that the first house and the last house are next to each other . meanwhile , Adjacent houses are equipped with interconnected anti-theft system , If two adjacent houses are broken into by thieves on the same night , The system will automatically alarm . Given an array of non negative integers representing the storage amount of each house , Calculate if you don't touch the alarm , The maximum amount that can be stolen . Example 1: Input : [2,3,2] Output : 3 explain : You can't steal first 1 House No （ amount of money = 2）, And then steal 3 House No （ amount of money = 2）, Because they are next to each other . Example 2: Input : [1,2,3,1] Output : 4 explain : You can steal first 1 House No （ amount of money = 1）, And then steal 3 House No （ amount of money = 3）. Maximum amount stolen = 1 + 3 = 4 .
- Yes 15 A bottle , At most one of them is poisonous , Now there are four mice , After drinking poisonous water , You'll die the next day . How can you tell which bottle is toxic the next day
- Look, your resume mentioned raft Algorithm , Talk a raft The basic flow of the algorithm ？raft How to deal with brain crack in the algorithm ？ Have you ever understood paxos and zookeeper Of zab Algorithm , What's the difference between them ？
- Rebuild the queue according to height Let's say there's a group of people in a disordered order standing in a line . Each person is matched by an integer (h, k) Express , among h It's the height of this man ,k Is in front of this person and is taller or equal to h The number of people . Write an algorithm to rebuild the queue . Be careful ： Less than 1100 people . Example Input : [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] Output : [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
- A two-dimensional array , The number of each column increases from left to right , Each line grows from top to bottom , Find the position of a specified number in this array
- Given a binary search tree , Find the nearest common ancestor of the two specified nodes in the tree . In Baidu Encyclopedia, the most recent definition of public ancestor is ：“ For a tree T Two nodes of p、q, Recently, the common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible （ A node can also be its own ancestor ）.” for example , Input : root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output : 6 explain : node 2 And nodes 8 The most recent public ancestor of 6. Example 2: Input : root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 Output : 2 explain : node 2 And nodes 4 The most recent public ancestor of 2, Because by definition, the nearest common ancestor node can be the node itself .
- A problem in stock trading Given an array of integers , Among them the first i Elements represent the i Day's share price . Design an algorithm to calculate the maximum profit . Under the following constraints , You can do as many deals as you can （ Buy and sell a stock many times ）: You can't participate in multiple transactions at the same time （ You have to sell the stock before you buy it again ）. After sale of shares , You can't buy shares the next day ( That is, the freezing period is 1 God ). Example : Input : [1,2,3,0,2] Output : 3 explain : The corresponding transaction status is : [ purchase , sell , Freezing period , purchase , sell ]
- To give you one n * m A two-dimensional array of integers , Numbers are greater than or equal to 0, Now I want you to do an operation on the array , For all 0, take 0 All the rows and columns are changed to 0. Ask to use as little space and time as possible .
- Give you an array of integers , Elements in an array define a distance d[i] After sorting the array , The distance the element moves , Now I'll give you a K Array , That is, the distance between all elements in the array d <= k, For this K Array sorting , Hope to keep the time complexity as small as possible .
- Enter a set of integers that do not contain the same integers , Output all subsets Input ：[1,2,3] Output ：[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]] There are thirty bottles of water , Ten barrels , Each bucket can hold 0-10 A bottle of water , How many options are there
- Given a string and an integer k, You need to check every... From the beginning of a string 2k Before characters k Characters to reverse . If the remainder is less than k Characters , Then reverse all the rest . If there is less than 2k But greater than or equal to k Characters , Before reversal k Characters , And leave the rest of the characters as they are . Example : Input : s = "abcdefg", k = 2 Output : "bacdfeg" requirement : （1） The string contains only lowercase letters . （ 2） The length and k stay [1, 10000] Within the scope of .
- Flip strings , Reverse sentences, etc .
- Determine the maximum effective length of parentheses in a string . Realize with dynamic programming
- Give a string , Find consecutive identical characters , If there are more than two of the same , take ASCII Small .
- Give a string , Delete the largest consecutive identical string and return
- There is a set of unsorted integer arrays , You design an algorithm , Pair the elements of an array , Then output the maximum absolute value difference and the minimum absolute value difference " logarithm "
- m*n Two dimensional arrays are ordered as a whole , lookup value
- Returns the sort value of an array of numbers , Like data [6,2,5,0] The return is [4,2,3,1];
- An array of positive numbers , The length is N, And array elements <N, Count the number of times each positive number appears , Time complexity required O(n), Spatial complexity O(1);
- Achieve one fibonacci function , Input number n, Output fibonacci The number of the sequence n Item number , And add cache function to this function .
- 100G The text looks for the frequency of a word
- Is it connected to the red black tree •
- Do you know about the data structure “ Pile up ”
- The non recursive implementation of fibolacci sequence
- Algorithm n At the end of the factorial 0 The number of
- I have a file , Yes 45 Billion Arabic numbers , How to remove the weight ? How to find the largest number ?
- Write a fibnaccio Related examples of
- Enter two strings str1 str2 And integer n, Ask for two numbers n Base addition , Then output the string str3
- It's how binary arrays spiral out Then the second algorithm is how to get from 25 Find the fastest horse in the form of horse racing 3 horse , At most, you can only 5 Horses race , Ask at least how many times it takes ？ The answer is 7 Time , I have the right idea , But I got the number wrong , More 2 Unnecessary games .
- 6 Elements 1.2.3.4.5.6 In order to stack , Which of the following is not a valid stack sequence ？ a:345261 b:436521 c:245316 d:124653 e:543612
- The shortest path problem of graphs
- Algorithm problem （ climb stairs , Ask a man to climb the stairs , You can only climb one or two steps at a time , Yes N A stair , How many climbing methods can there be in total ）;
- Achieve one random(m,n) Method , return m To n The random number
- 64 Only teams find the best , Find the top two , front k Strong
- Namely m*n How many paths are there from the top left to the bottom right
- seek N All primes in
- Determine whether the string is a number
- When a text file contains 200 Ten thousand rows of data , How to append a character at the end of each line ;
- Find the length of the longest non repeating substring in a string
- Three signed integers （long） Count a, b, c, How to judge a+b > c? Implement and design test cases （ stay main Call in function , Print the results ） （ Consider the same sign crossing problem ）
- Give a string and a k, Ask to find no more than k The length of the longest substring of different characters
- 10 Turn into the system 16 Base number （ Nervous , It's a little time-consuming , Tut tut tut ）
- f(0)=0;f(1)=1; f(n)=f(n-1)+f(n-2) seek f（n）
- There's a main string A, Substring B, stay A Search for B

Welcome to search and pay attention to the wechat face-to-face program developed by me and friends 【 Interview assistant of big factory 】 And the official account 【 Micro view technology 】