Tree Traversals

Pre Order

1
2
3
4
5
6

const PreOrder = (node) => {
  if (node === null) return;
  console.log(node.value); // visit the node before traverse
  PreOrder(node.left);
  PreOrder(node.right);
};

In Order

1
2
3
4
5
6

const InOrder = (node) => {
  if (node === null) return;
  InOrder(node.left);
  console.log(node.value); // visit the node in traverse
  InOrder(node.right);
};

Post Order

1
2
3
4
5
6

const PostOrder = (node) => {
  if (node === null) return;
  PostOrder(node.left);
  PostOrder(node.right);
  console.log(node.value); // visit the node after traverse
};

Level Orider

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

function levelOrder(root: TreeNode | null): number[][] {
  let queue: (TreeNode | null)[] = [root];
  const result: number[][] = [];

  while (queue.length > 0) {
    const ans: number[] = [];
    const q: (TreeNode | null)[] = [];

    while (queue.length > 0) {
      const node = queue.shift();
      if (node) {
        ans.push(node.val);
        q.push(node.left, node.right);
      }
    }

    result.push(ans);
    queue = q;
  }

  result.pop();
  return result;
}

Complete Binary Tree

Give an array and return a tree construction.

1

Maximum Depth of Binary Tree

We go deep inside it’s left and it’s right, compare both of them. The one has greatest value will be add to one.

1
2
3
4
5
6
7
8

function maxDepth(root: TreeNode | null): number {
  if (root === null) return 0;

  const leftLen = maxDepth(root.left);
  const rightLen = maxDepth(root.right);

  return Math.max(leftLen, rightLen) + 1;
}

Minimum Depth of Binary Tree

1
2
3
4
5
6
7
8
9
10

function minDepth(root: TreeNode | null): number {
  if (root === null) return 0;

  const l = minDepth(root?.left);
  const r = minDepth(root?.right);

  // Add This Line
  if (r === 0 || l === 0) return Math.max(l, r) + 1;
  return Math.min(l, r) + 1;
}

Balanced Binary Tree

A balanced binary tree, also referred to as a height-balanced binary tree, is defined as a binary tree in which the height of the left and right subtree of any node differ by not more than 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function isBalanced(root: TreeNode | null): boolean {
  let resp = true;
  const Depth = (node: TreeNode | null): number => {
    if (node === null || resp === false) return 0;

    const l = Depth(node.left);
    const r = Depth(node.right);

    if (Math.abs(l - r) > 1) resp = false;
    return 1 + Math.max(l, r);
  };

  Depth(root);
  return resp;
}

Check If Two Binary Trees Are Equal

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

We can traverse both of them at same time and find if they are equal in the same node.

1
2
3
4
5
6
7
8

const isSameNode = (p: TreeNode | null, q: TreeNode | null) => {
  if (p === null && q === null) return true;
  if (p === null || q === null) return false;

  if (p.val !== q.val) return false;

  return isSameNode(p.left, q.left) && isSameNode(p.right, q.right);
};

Intuition

DFS is a recursive algorithm that use backtracking principle for graph traversal.

The main intuition for DFS is:

1. Find the beginning vertex of the graph, marked as visited and output, and try to get into its next options.
2. If this option has child vertex then try to get into next option.
3. Until arrive at the bottom vertex which don’t have visited child vertex.
4. Then Track back to the last vertex, if it has unvisited options, get into the option and do this four steps again;
5. Until all vertexes have been visited.

Here is an example.

1
2
3
4
5

  1 - 4     8 - 9
 /| \      /|
0 |   3 - 5 |
 \|      / \|
  2     6   7

the order of next graph visited is:
0 -> 1 -> 4 -> 1 -> 3 -> 5 -> 8 -> 9 -> 8 -> 7 -> 8 -> 5 -> 6 -> 5 -> 3 -> 1 -> 2 -> 1 -> 0

the order of the out put is: 0 -> 1 -> 4 -> 3 -> 5 -> 8 -> 9 -> 7 -> 6 -> 2

Implementation

1
2
3
4
5

  1
 / \
0 - 3 - 4
 \ /
  2

Recursion

The intuition inspire us that for each vertex we can ignore the last one and do same about the next one. So we can use Dfs(G, v) means (graph, vertex), recursive to each vertex.

In the function, we do visit(), marked() to current vertex and recurse its all next unvisited vertex.

1
2
3
4
5
6
7

function Dfs(G, v) {
  visit(v); // at the begin
  v.marked = true;
  for (let w in v.neighbors) {
    if (w.marked === false) Dfs(G, w);
  }
}

This is a preorder method. There is also a different order for Dfs called postoder that print out the vertex after all its sub vertex have been visited.

1
2
3
4
5
6
7

function Dfs(G, v) {
  v.marked = true;
  for (let w in v.neighbors) {
    if (w.marked === false) Dfs(G, w);
  }
  visit(v); // at the end
}

Stack

We also can use a stack data structure to implement it.

We pop the vertex in the stack one by one to visit it. And if it has unvisited vertex, we push all the unvisited child into stack waiting to visit. And continue popping in loop.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function Dfs(G, v) {
  const stack = [v];
  while (stack.length > 0) {
    const v = stack.pop();
    if (v.marked === false) {
      visit(v);
      v.marked === true;
    }
    for (let w in v) {
      if (w.marked === false) {
        stack.push(w);
      }
    }
  }
}

What is big O notation

big o notation is used to analyze the efficiency of an algorithm: as the size of the input growth, how drastically do the space or time requirements grow with it.

So when evaluating an algorithm efficiency we must taking to consideration the efficiency of each step within the algorithm. Then find the step that has the worst performance and prioritize it over all of the better performing steps.

$O(1)$

A constant is any step that doesn’t scale with the input to the function.

$O(n^2)$ / $O(n^3)$

1
2
3
4
5
6
7
8
9

function Square(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        console.log(i, j, k);
      }
    }
  }
}

$O(log n)$

1
2
3
4
5
6
7
8
9
10
11

function logFunc(n) {
  if (n === 0) return 'Done';
  n = Math.floor(n / 2);
  return logFunc(n);
}

function logn(n) {
  while (n < 1) {
    n = Math.floor(n / 2);
  }
}

The input n is always divided by 2, so the complexity is $O(log_{2}n)$. So if n is always divided a constant number x, it will be $O(log_{x}n)$

Binary Search

Searching must be an ordered array Thinking we need to find a certain number in this array.

1. find the midpoint of our array
2. figure out if the number we’re searching for is grater than or less than midpoint
3. if it’s greater than our number, the left array is the right side of the midpoint. Otherwise the right array
4. recur the step 1 to 3 in the left array.

1
2
3
4
5
6
7
8
9

function BinarySearch(arr, target, start, end) {
  if (start > end) return `Can't get it`;

  const mid = Math.floor(start + end / 2);
  if (target === arr[mid]) return `Get index ${mid}`;

  if (target > arr[mid]) return BinarySearch(arr, target, mid + 1, end);
  else return BinarySearch(arr, target, 0, mid - 1);
}

$O(nlog n)$

1
2
3
4
5
6
7
8
9

function nLogNFunc(n) {
  let y = n;
  while (n > 1) {
    n = Math.floor(n / 2);
    for (let i = 2; i <= y; i++) {
      console.log(i);
    }
  }
}

top loop $O(log2n)$. Inner loop keep the origin value of n so it’s $O(n)$. Totally, it’s $O(nlog_{2}n)$

Merge Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

function MergeSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  const mid = Math.floor(arr.length / 2);

  return Merge(MergeSort(arr.slice(0, mid)), MergeSort(arr.slice(mid, arr.length)));
}

function Merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }
  return [...result, ...left.slice(leftIndex), ...right.slice(rightIndex)];
}

Consider we have 4 length array, MergeSort() have two level $O(logn)$ . For EVERY LEVEL, Merge() touch each number in the array n times $O(n)$. So it’s $O(nlogn)$ totally

$O(2^n)$

Fibonacci

1
2
3
4
5
6

function fib(n) {
  if (n == 0) return 0;
  if (n == 1) return 1;

  return fib(n - 1) + fib(n - 2);
}

$O(n!)$

1
2
3
4
5
6
7
8
9

function fn(n) {
  if (n == 0) {
    return;
  }

  for (let i = 0; i < n; i++) {
    fn(n - 1);
  }
}

Reference: swyx blog, robin blog

STEP 1 OS Settings

1. Dock

   1. Remove most application from the dock
   2. Middle size magnification and Smaller dock
   3. OFF “show recent applications in dock”
   4. ON “show indicators for open applications”
   5. OFF menu bar “Automatic hide desktop and full screen”

2. Battery

   1. ON “Show percentage”

3. Display

   1. Nightshift

4. Siri

   1. Disable

5. Trackpad

   1. Tap to click
   2. Tracking speed 9/10

6. Keyboard-Text

   1. disable “Capitalize word automatically”
   2. disable “Add full stop with double-space”
   3. disable “Use smart quotes and dashes”
   4. use “ for double quotes
   5. use ‘ for single quotes

7. Spotlight

   1. Disable Spotlight except for Applications and System Preferences

8. Finder

   1. Sidebar on locations
   2. Hide all Tags
   3. Show all Filename Extensions
   4. Search the current folder
   5. view show tab/path/status bar

9. Dictionary

   1. Add chinese simplified dictionary
   2. Delete wiki and apple dictionary

10. Sharing

    1. Change computer name

11. Terminal

    1. Change terminal user name

       1 2 3

       sudo scutil --set ComputerName "newname" sudo scutil --set LocalHostName "newname" sudo scutil --set HostName "newname"

    2. Default show hidden files

       1	defaults write com.apple.finder AppleShowAllFiles YES

12. Security & Privacy -> General

    1. immediately after sleep or screen saver begin

13. Screen saver

    1. Flip Clock Screen Saver
    2. Set Right Hot Corner to screen saver and cancel other corner

STEP 2 Homebrew

Install homebrew as package manager for macOS, paste that command line in the terminal. Remember to set $PATH in .zprofile

Refer: Install Homebrew

Install GUI applications:

1
2
3
4
5
6
7
8
9
10
11

brew install --cask \
iterm2 \
visual-studio-code \
sublime-text \
docker  \
discord \
figma \
imageoptim \
eul \
alfred \
google-drive

Install terminal applications :

1
2
3
4
5
6
7
8
9
10

brew install \
node \
wget \
exa \
git \
autojump \
nvm \
pnpm \
commitizen \
graphicsmagick

Install other apple apps: xnip, google drive

Install node app:

1
2

npm install -g typescript \
ts-node

STEP 3 Set Iterm2 Terminal

1. Make iterm2 Default Term

2. Preference

   1. General ->
      1. Window
         1. unselect “Native full screen windows”
      2. Startup
         1. Use System Window Restoration Setting
         2. select “close windows when closing an app”
   2. Appearance
      1. Windows: select “Hide scrollbar”
      2. Tabs:
         1. unselect “Show tab bar in fullscreen”
         2. Select “flash tab bar when switching tabs in fullscreen”
         3. Dimming: Unselect all dimming
   3. Profiles -> window
      1. Transparency: 30
      2. Style: full screen
      3. Screen: main screen
   4. Profiles -> Advanced
      1. Semantic History -> Open with editor … -> VS Code
   5. Open new split pane with current directory
   6. Natural Text Editing

3. Install Oh-my-zsh

   1. Homebrew Install Starship as new terminal theme.

      1 2	brew install starship echo 'eval "$(starship init zsh)"' >> ~/.zshrc

   2. Install and use the new font in iTerm2: Preferences -> Profile -> Text -> Font: monoid-nerd-font.

      1 2	brew tap homebrew/cask-fonts brew install --cask font-monoid-nerd-font

   3. Download oh-my-zsh plugins, clone that git repo to default zsh directory, and set plugin in .zshrc

      • zsh-completions
      • zsh-autosuggestions
      • Zsh-syntax-highlighting

STEP 4 Set VS Code

Download Extensions:

• Gitlens
• Auto Import
• Auto Close Tag
• Auto Close Tag
• EditorConfig
• eslint
• prettier
• Better Comments
• import cost
• Highlight Matching Tag
• color highlight
• ES7+ React/Redux/React-Native/JS snippets, react refactor
• vscode-styled-components
• color picker
• leetcode
• The Doki Theme
• background
• prettier-eslint
• Markdown Preview Enhanced
• markdownlint
• markdown all in one
• Code Spell Checker

JSON settings:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

{
  "security.workspace.trust.untrustedFiles": "open",
  "files.autoSave": "afterDelay",
  "files.trimTrailingWhitespace": true,
  "explorer.confirmDelete": false,
  "explorer.compactFolders": false,
  "workbench.startupEditor": "none",
  "workbench.statusBar.visible": true,
  "workbench.editor.enablePreview": false,
  "workbench.editor.restoreViewState": true,
  "terminal.integrated.fontFamily": "Monoid Nerd Font",
  "editor.fontFamily": "Monoid Nerd Font",
  "editor.fontSize": 14,
  "editor.tabSize": 2,
  "editor.insertSpaces": true,
  "editor.detectIndentation": false,
  "editor.renderWhitespace": "none",
  "editor.scrollBeyondLastLine": true,
  "editor.minimap.enabled": false,
  "editor.find.seedSearchStringFromSelection": "selection",
  // syntax highlighting
  "files.associations": {
    ".env*": "makefile"
  },
  // prettier
  "prettier.singleQuote": true,
  "prettier.printWidth": 120,
  "editor.formatOnSave": true,
  "[javascript]": {
    "editor.formatOnSave": true,
    "editor.defaultFormatter": "esbenp.prettier-vscode"
  },
  "[javascriptreact]": {
    "editor.formatOnSave": true,
    "editor.defaultFormatter": "esbenp.prettier-vscode"
  },
  "[typescript]": {
    "editor.formatOnSave": true,
    "editor.defaultFormatter": "esbenp.prettier-vscode"
  },
  "[typescriptreact]": {
    "editor.formatOnSave": true,
    "editor.defaultFormatter": "esbenp.prettier-vscode"
  },
  // eslint
  "editor.codeActionsOnSave": {
    "source.fixAll.eslint": true
  },
  "eslint.validate": ["javascript"],
  "javascript.validate.enable": false,
  "javascript.updateImportsOnFileMove.enabled": "never",
  "typescript.updateImportsOnFileMove.enabled": "never",
  // auto generated
  "explorer.confirmDragAndDrop": false,
  "js/ts.implicitProjectConfig.checkJs": true,
  "editor.formatOnPaste": true,
  "editor.formatOnType": true,
  "extensions.ignoreRecommendations": true,
  "[jsonc]": {
    "editor.defaultFormatter": "esbenp.prettier-vscode"
  },
  "workbench.colorTheme": "Bearded Theme Coffee Reversed",
  "[markdown]": {
    "editor.defaultFormatter": "esbenp.prettier-vscode"
  },
  "window.zoomLevel": -1
}

STEP 5 Set Github

For terminals, set global name and email

1
2

git config --global user.name Kristine
git config --global user.email kristine.7q@gmail.com

Set SSH Keys for github

1. create a new SSH key in the ~/.ssh folder:

   1 2 3 4 5

   mkdir ~/.ssh cd ~/.ssh ssh-keygen -t ed25519 -C "github" # use file name: github # use passphrase

2. In your ~/.ssh/config file, add the new SSH key, so that it can get picked up for every terminal session automatically:

   1 2 3 4

   Host * AddKeysToAgent yes UseKeychain yes IdentityFile ~/.ssh/github

3. Add SSH key to MacOS’ keychain:

   1	ssh-add --apple-use-keychain ~/.ssh/github

4. Add the public key to your GitHub settings via the website or via the GitHub CLI via

   1 2 3

   # use GitHub's CLI brew install gh gh auth login

那么我们从render()开始。

早版本 React 的 render 函数，首先把 react element 解析成真正的 dom，然后用document.appendChild(dom)的方式，挂载到父节点上，也是 React 之前被诟病的低性能的设计：渲染一旦开始就无法停止，直到渲染了完整的 dom 树，可能会阻塞主线程很久，如果浏览器需要做高优先级的事情，比如处理用户输入或保持动画流畅，它必须等到渲染完成。