Interview algorithm questions

A algorithm

I often encounter a flat tree structure passed to me from the back end. Converting such a structure into a tree structure can be used in cases like Cascader:

Const data = [{parent: 3, ID: 4, value: 4,}, {parent: null, ID: 1, value: 1,}, {parent: 1, id: 2, value: 2, }, { parent: 1, id: 3, value: 3, } ]; Output: [{id: 1, value: 1, children: [{id: 2, value: 2,}, {id: 3, value:3, children: [{id: 4, value: 4,}]}];Copy the code

Implementation idea:

  • Find the root node first
  • I recurse from the root to find the child

Two surface algorithm

In a one-dimensional coordinate, give a target line segment, e.g. (3, 8). A set of source line segments, e.g. (1, 2),(3, 4), (5, 8), (3, 6). Checks whether the collection of source segments completely covers the target segment, returning true or false

Const data = [3, 8]; const source = [[1, 2], [3, 4], [5, 8], [3, 6]]; Output: true,Copy the code

Implementation idea: mainly how to merge the source line segment

  • First sort the source line segment according to the starting point
  • The source line segment is traversed again, and the starting point of the next line segment is compared with the current end point each time to judge whether it overlapped again. If so, it is merged; if not, it indicates that it is a separate line segment
  • Traverse the merged source line segment to determine whether the target line segment is completely included

Three algorithms

Merges two ordered arrays in reverse order. Answer: Refer to Leet Code question 88

conclusion

One side of the algorithm, and three side of the algorithm quickly write out, the second side of the algorithm, also let the interviewer to give some hints to write out. Don’t panic when you encounter algorithmic questions during the interview. The following steps will help you figure out the algorithm:

  1. First make clear the meaning of the topic, determine the input and output. Check with the interviewer that you understand the questions correctly
  2. Sort out your ideas and explain to the interviewer that there is no problem with your ideas before you start coding
  3. Even if you don’t have ideas, don’t panic, or just don’t do it, smile and ask the interviewer to give you a hint
  4. Follow the prompts and repeat Step 2
  5. Encoding and running, summarizing and analyzing time complexity and space complexity