Interview series (7): data structure and algorithm, etc

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 】