# Preface

( Shh! Here are all algorithmic questions that have been interviewed! )

Algorithms are a topic that many factories like to produce, and everyone who has been corrected by the algorithm must be gnashing their teeth.

Well, this article is a welfare article. The purpose is to let the friends find confidence, no longer resist the algorithm, no longer feel hurt by the algorithm problem

The ultimate goal of this article is the last question, React Fiber. emmmm, just mention it, it's easy. Don't spray me

## Question 1: Stock question.

Implement a function to find a buying point and a selling point from the known daily price of a certain stock, and calculate the maximum return.

E.g:

enter:

[1, 2, 4, 8]
Output:
7

enter:

[8, 1, 2, 4]
Output:
3

//Obviously, this kind of topic must not write nested loops, for example:
for (){
for (){...}
}

//The time complexity of such an algorithm is O(n * n);

//Is there an O(n) solution?

//Yes, let's understand the next topic. Can we get the difference by subtracting the last number from the last number? A positive difference means you can make a profit, and a negative means you lose money. If you lose money, you have to do it again?

function  mf ( arr ) {
var str = "" ;
var m = 0 ;
var e = 0 ;
for ( var i = 1 ; i <arr.length; i++) {
var t = arr[i]-arr[m] ;
if (t> e) {
e = t;
str = "The first" +(m+ 1 )+ "The day to buy the first" +(i+ 1 )+ "The day to sell income" +e;
}
if (t < 0 )
m = i;
}
return str;
}

Copy code

## Question 2: leetcode 168. Excel table column name

Given a positive integer, return its corresponding column name in the Excel table.

1 => A;

2 => B;

3 => C

...

26 => Z;

27 => AA;

28 => AB;

29 => AC

...

52 => AZ;

53 => BA;

54 => BB

...

//Implement the function below

function convert(num) {//TODO}

//Test code:

const output1 = convert(1);

console.log(output1);//A

const output2 = convert(26);

console.log(output2);//Z

const output3 = convert(53);

console.log(output3);//BA

//Understand that, in fact, this question is obviously a question from decimal to 26. Mainly need to consider 2 factors.
//1. 1-26 correspond to AZ respectively, there is no 0;
//2. More than 26 enters A. (It is the same reason as the original full 10 into 1)

function  convert ( columnNumber ) {
const arr = [ 'A' , 'B' , 'C' , 'D' , 'E' , 'F' , 'G' , 'H' , 'I' , 'J' , 'K' , 'L' , 'M' , 'N' , 'O' , 'P' , 'Q' , 'R' , 'S' , 'T', 'U' , 'V' , 'W' ,'X', 'Y' , 'Z' ];
//Less than or equal to 26, directly return
let n = columnNumber;
if (n <= 26 ) return arr[n- 1 ];
let res = '' ;
while (n> 0 ) {
//n is subtracted by 1. Because the subscript of the array arr starts from 0. And the title is from 1
n--;
//Splicing from back to front
res = arr[n% 26 ] + res;
n = Math .floor(n/26 ); // Round off .
}
return res;
};
};
Copy code

## Question 3: Binary tree traversal

### Depth first traversal

First give a binary tree data

const tree = {
value : "-" ,
left : {
value : '+' ,
left : {
value : 'a' ,
},
right : {
value : '*' ,
left : {
value : 'b' ,
},
right : {
value : 'c' ,
}
}
},
right : {
value : '/' ,
left : {
value : 'd' ,
},
right : {
value : 'e' ,
}
}
}
Copy code

If you are interested, you should be able to see that this data is actually a formula:

$(a+b*c)-d/e$

Let s start with the code, let s take a look at the depth-first traversal (

Depth-First Search, DFS
) Bar. When you see the word dfs in the code, you should react to it in time. It is traversed in all likelihood.

//Deep traversal-first-order traversal
//Recursive implementation
let result = [];
let dfs = function ( node ) {
if (node) {
result.push(node.value);
dfs(node.left);
dfs(node.right);
}
}

dfs(tree);
console .log(result); //["-", "+", "a", "*", "b", "c", "/", "d", "e"]

/* Idea:
1. First traverse the root node and store the value in the array.
2. Then recursively traverse: first the left node, store the value into the array, and continue to traverse down; until (the binary tree is empty) the subtree is empty, the traversal ends;
3. Then backtrack and traverse the right node, store the value in the array, and loop recursively until the (binary tree is empty) subtree is empty, then the traversal ends.
*/

//Non-recursive implementation
let dfs = function ( nodes ) {
let result = [];
let stack = [];
stack.push(nodes);
while (stack.length) { //equivalent to while(stack.length !== 0) until the data in the stack is empty
let node = stack.pop(); //take the last j in the stack
result.push(node.value);
if (node.right) stack.push(node.right); //Push the right subtree first to ensure order
if (node.left) stack.push(node.left); //Push the left subtree later
}
return result;
}
dfs(tree);

/*Thinking
step 1. Initialize a stack and push the root node into the stack;
step 2. When the stack is not empty, execute steps 3 to 4 in a loop, otherwise the loop ends and the final result is obtained;
step 3. Get a node from the queue (in fact, it is the top element of the stack), and put the value into the result array;
step 4. If the right subtree of the node is not empty, push the right subtree of the node onto the stack. If the left subtree of the node is not empty, push the left subtree of the node into the stack;
(Ps: First push the right node into the stack, and then into the left node. When getting from the stack, the last node put on the stack is taken, and the first order traversal must first traverse the left subtree, and then traverse the right subtree. tree)

*/

//Deep traversal-middle-order traversal
//Recursive implementation
let result = [];
let dfs = function ( node ) {
if (node) {
dfs(node.left);
result.push(node.value); //Until the node has no left subtree, save the node into the result array and start traversing the right subtree
dfs(node.right);
}
}

dfs(tree);
console .log(result); //["a", "+", "b", "*", "c", "-", "d", "/", "e"]

/*You can understand the idea at a glance, just adjust the order  */

//
function dfs(node) {
let result = [];
let stack = [];
while(stack.length || node) { //  ||   &&
if(node) {
stack.push(node);
node = node.left;
} else {
node = stack.pop();
result.push(node.value);
node = node.right; //
}
}
return result;
}

dfs(tree);
/*
1.
2.
3.
4.
*/

//
//

let result = [];
let stack = [tree]; //First push the tree to be traversed onto the stack
let count = 0 ; //Used to record execution to the first level
let bfs = function () {
let node = stack[count];
if(node) {
result.push(node.value);
if (node.left) stack.push(node.left);
if(node.right) stack.push(node.right);
count++;
bfs();
}
}
dfc();
console .log(result); //["-", "+", "/", "a", "*", "d", "e", "b", "c"]

/*Thinking: Should the thought be clear at a glance? */

Copy code

## Question 4: React Fiber

This year, the interview was asked

React diff
What is the probability of the algorithm?

If we say that the previous diff algorithms are basically

Virtual DOM
->
DOM
, The current
diff
The algorithm is
Virtual DOM
->
Fiber
->
->
DOM
.

Do you think the interviewer will not consider time? So ask you

Fiber
diff
, And are you answering diff or fiber? Or are you talking about it all?

Here is a little trick. Knock on the blackboard and draw the focus! Please treat Fiber as an algorithm problem, and the first thing to be clear about algorithm problems is: the data structure corresponding to the algorithm.

step 1:
First introduce what properties the Fiber object has. In fact, this is an introduction to the data structure. Please pick the most core attributes to talk about.

step 2:
Make it clear how the Fiber object comes, that is, how to build the Fiber object.

step 3:
How to build a fiber list.

step 4:
How to render the real DOM

What exactly is Fiber?

Fiber is an execution unit

In React 15, the VirtualDOM tree as a whole is treated as a task for recursive processing. The overall execution of the task is huge and time-consuming and cannot be interrupted.

In React 16, the entire task is divided into small tasks for processing, and each small task refers to the construction of a Fiber node.

Tasks will be executed during the free time of the browser
, After the execution of each unit is completed, React will check whether there is free time, and if there is, it will return the control of the main thread.

//Oh hayo, let me help you list the attributes hanging on the Fiber object as much as possible. Isn't it horrible?   Does the scalp feel numb

type Fiber = {
/************************ DOM instance related********************** *******/

//Mark different component types, see WorkTag
tag for details : WorkTag,

//Component type div, span, component constructor
type : any,

//Instance objects, such as instances of class components, native dom instances, and function components have no instances, so this attribute is empty
stateNode : any,

/************************    Fiber    ***************************/

//  Fiber
return: Fiber | null,

//  Fiber
child: Fiber | null,

//  iber
sibling: Fiber | null,

//  Fiber   Fiber   Fiber
//  current <==> workInProgress
//
//alternate   Fiber   workInProgress   Fiber
alternate: Fiber | null,

/************************     ********************************/

//  props
pendingProps: any,
//  props
memoizedProps: any,
//  state
memoizedState: any,

/************************    ******************************/

//  Fiber
updateQueue: UpdateQueue<any> | null,

//  Fiber   DOM
effectTag: SideEffectTag,

//  DOM
firstEffect: Fiber | null,

//  side effect
nextEffect: Fiber | null,

//  DOM
lastEffect: Fiber | null,

//
expirationTime: ExpirationTime,

//    TypeOfMode
mode: TypeOfMode,
};