Interviewed a dozen advanced front-end, even (flat data structure to Tree) can not write out

“This article has participated in the good article call order activity, click to see: back end, big front end double track submission, 20,000 yuan prize pool for you to challenge!”

preface

Recruitment season is usually golden three silver four, or gold nine silver ten. Recently in this May and June, after interviewing a dozen senior front end. There’s a set of little problems to look at the algorithm. The background returns a flat data structure, turned into a tree.

Let’s look at the title: The data for tying is as follows:

Let arr = [{id: 1, name: '1', pid: 0}, {id: 2, name: '2', pid: 1}, {id: 3, name: '3', pid: 1}, {id: 4, name: {id: 5, name: 'department 5', pid: 4},]Copy the code

The output

[{" id ": 1," name ":" unit 1 ", "pid" : 0, "children" : [{" id ": 2," name ":" department 2 ", "pid" : 1, "children" : []}, {" id ": Department of 3, "name" : "3", "pid" : 1, "children" : / / / as a result,,,}}]]Copy the code

Our requirements are simple, and we can forget about performance. I went back and analyzed the interview, and the results surprised me.

10% of you have no idea, you don’t have this structure

60% said they used recursion, had ideas, gave them a notebook, but couldn’t write it out

Twenty percent stumbled through it with guidance

The other 10% can write it, but not at their best

It feels like it’s hard to meet the right person when it’s not hiring season.

Next, we implement this little algorithm in several ways

What is a good algorithm and what is a bad algorithm

To judge the quality of an algorithm, generally from the execution time and space, the shorter the execution time, the smaller the memory space, then it is a good algorithm. Accordingly, we often use time complexity to represent execution time and space complexity to represent memory footprint.

Time complexity

The time complexity is calculated not by the time the program runs, but by the number of times the algorithm executes the statement.

As n increases, the time complexity increases, and the algorithm takes more time. Common time complexities are

• Constant of the orderO(1)
• The logarithmic orderO(log2 n)
• Linear orderO(n)
• Linear logarithmic orderO(n log2 n)
• Square orderO(n^2)
• Cubic orderO(n^3)
• K to the power stageO(n^K)
• The index orderO(2^n)

Calculation method

1. Pick the term with the highest relative growth
2. The highest coefficients are all 1’s
3. If it’s a constant, it’s O(1)

For example, if f(n)=3*n^4+3n+300, then O(n)=n^4

Usually we calculate the time complexity for the worst case. A few points to note when calculating time complexity

• If the execution time of the algorithmDon't over ntheincreasewhilegrowth, if the algorithm hasThousands ofStatement, the execution time is just oneLarger constant. The time complexity of such an algorithm isO(1). For example: Code executed 100 times is a constant, so is its complexityO(1).

    let x = 1;
    while (x <100) {
     x++;
    }
Copy the code

• There areMultiple loopThe time complexity of the algorithm is determined byMaximum number of nesting layersIn the loop statementThe innermostThe method of the statement. Here’s an example: In the following for loop,The outer loopEach timeAt a time.The inner loopTo performnTimes, the number of executions is determined by n, and the time complexity isO(n^2).

for (i = 0; i < n; i++){ for (j = 0; j < n; j++) { // ... code } }Copy the code

• Cycles are not only related tonIs related to, but also to execution loopsJudge conditionsThe relevant. For example: In the code, ifarr[i]Is not equal to1So the time complexity is order n. ifarr[i]Is equal to the1If the loop does not execute, the time complexity is zeroO(0).

for(var i = 0; i<n && arr[i] ! = 1; i++) { // ... code }Copy the code

Spatial complexity

Space complexity is the amount of storage space temporarily occupied by an algorithm while it is running.

Calculation method:

1. Ignore the constant and write it in order one
2. The space complexity of the recursive algorithm =(the depth of recursion n)*(the auxiliary space required for each recursion)

Simple points to calculate space complexity

• Only single variables are copied, and the space complexity is O(1). For example: The space complexity is O(n) = O(1).

let a = 1; let b = 2; let c = 3; Console. log(' output a,b,c', a,b,c);Copy the code

• Recursive implementation, calling fun, each time creating 1 variable k. Call n times, the space complexity O(n*1) = O(n).

    function fun(n) {
       let k = 10;
       if (n == k) {
           return n;
       } else {
           return fun(++n)
       }
    }
Copy the code

Recursive traversal lookup regardless of performance implementation

The main idea is to provide a recursive getChildren method that recurses to find subsets. So, no performance concerns, no brain to look up, most people only know recursion, just can’t write it…

/** * GetChildren */ const getChildren = (data, result, pid) => { for (const item of data) { if (item.pid === pid) { const newItem = {... item, children: []}; result.push(newItem); getChildren(data, newItem.children, item.id); Const arrayToTree = (data, pid) => {const result = []; getChildren(data, result, pid) return result; }Copy the code

From the above code we analyze that the time complexity of the implementation is O(2^n).

I can do it without recursion

The main idea is to first convert the data into a Map for storage, and then find the corresponding data directly from the Map for storage with the help of the object reference during traversal

function arrayToTree(items) { const result = []; // Store the result set const itemMap = {}; For (const item of items) {itemMap[item.id] = {... item, children: []} } for (const item of items) { const id = item.id; const pid = item.pid; const treeItem = itemMap[id]; if (pid === 0) { result.push(treeItem); } else { if (! itemMap[pid]) { itemMap[pid] = { children: [], } } itemMap[pid].children.push(treeItem) } } return result; }Copy the code

From the above code, we analyze that there are two loops, the time complexity of the implementation is O(2n), a Map is needed to store the data, and the space complexity is O(n).

Optimal performance

The main idea is to first convert the data into a Map for storage, and then find the corresponding data directly from the Map for storage with the help of the object reference during traversal. Differences in traversal that is, do Map storage, there is a correspondence. Performance will be better.

function arrayToTree(items) { const result = []; // Store the result set const itemMap = {}; // for (const item of items) { const id = item.id; const pid = item.pid; if (! itemMap[id]) { itemMap[id] = { children: [], } } itemMap[id] = { ... item, children: itemMap[id]['children'] } const treeItem = itemMap[id]; if (pid === 0) { result.push(treeItem); } else { if (! itemMap[pid]) { itemMap[pid] = { children: [], } } itemMap[pid].children.push(treeItem) } } return result; }Copy the code

From the above code we analyze, it is done in one loop, the time complexity of the implementation is O(n), it requires a Map to store the data, and the space complexity is O(n).

A profound

From our test results, as the number increases, the recursion implementation becomes slower and slower, basically increasing exponentially.

conclusion

Do you think the advanced front end, should be very smooth to write this out. Leave your thoughts in the comments section. There are better implementations than that, so leave your answers in the comments section and let’s all learn.