# 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:

enter:

```
//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 (

```
//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

If we say that the previous diff algorithms are basically

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

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.**

**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**

```
//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,
};
```

** **

~~ ~~