当前位置:网站首页>Interview series (7): data structure and algorithm, etc

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

2020-11-10 11:55:29 A loser

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 】

file
file

版权声明
本文为[A loser]所创,转载请带上原文链接,感谢