# [AIdrifter CS 浮生筆錄](https://hackmd.io/s/rypeUnYSb) <br> Cracking The Coding interview
# 前言準備
- google注重system design和可擴展性
- C++
- Professional
- 精通
- 用過

- OPL , TA stack-usage
- Challenge
- mistake / fault
- 收穫
- 領導
- Conflict
- 現在想想是否有不同的做法


- 盡量不要說"我們"，人家會搞不楚這東西到底是不是你做的
- SAR
- Situation
- Action
- 拆順序，分散步驟，最重要的部分。
- Result
:::info
之前P&P Language上課的Job Interveiw
:::
# Big-O
## Asymptopic Notation
業界Big-O <=> 學術Big-Theta

課本
- Big O
- Big Theta
- Big Omega

## Time Complexity
O(n) : constant time
O(logn) : logarithmic : 通常是binary Search，元素折半。
O(n) : linear
O(nlogn) : linearithmic
O(n^2) : square
O(n^3) : cubic
O(2^n) : exponetial ： fib(n) = fib(n-1) +fib(n-2), O(branch^depth)，看不懂可以畫tree圖。
O(n!) : factorial


quick sort
- Best O(n)
- Worst O(n^2)
- Average (nlogn)
- 這些說的都是big-thetas
https://en.wikipedia.org/wiki/Time_complexity

## Sapce Complexity
- Recursive stack

## Amortized Time 平攤時間
- Vector insert()時的copy元素成本

1 + 2 + 4 + 8 + ....x
= x + x/2 + x/4 + ... 1
= x(1 + 1/2 + 1/4 + .... 1/2^n)
= x( 1/( 1- 1/2))
= 2x


## f(n) = f(n-1) + f(n-2)
Time Complexity : O(2^n) : O(branch^depth)
Sapce Complexity: O(n) : Tree height
1+2+3+...n = n(n+1)/2


O(branch^depth)
=> O (2^logn) = O(n) // 換底公式

2^p = Q
=> lnQ = P

:::info
延伸題目
1.用binary Search找平方根
2.Permutation的recursive寫法
:::

# Technicla Questions
## 必會章節
## 解題步驟
## BUD

## BCR
Best Conceivable Runtime
https://hackmd.io/CSJhi7AaTkmoT4pLOUR2RA

## What Good Coding Looks Like

- 用資料結構去存資料:Coeficcient
- Appropriate Code Reuse
- 

- Modular
- function化 : 多寫幾個function
- Flexible and Robust

# Array & String
:::info
Review Previous STL all time Complexity

:::

## Hash Table


## Array List
Java: ArrayList <=> C++: vector

## String Builder
Java:StringBuilder
https://stackoverflow.com/questions/2462951/c-equivalent-of-stringbuffer-stringbuilder

:::info
C++的stringBuilder???
:::

# LinkedList
- Insert()
- Delete()
- If the list is doubly linked, we must also update n. next to set n. next. prey equal to n. prev.

- runner(): 龜兔賽跑 找迴圈
- Recursive Problem

# Stack
LIFO
- push()
- peak() <=> top()
- pop()
- IsEmpty()

- Application
- DFS
- recursive

# Queue
- add()
- remove()
- peak
- IsEmpty()

:::info
- Priority queue + heap
:::

- Application
- BFS
- 實做cache

# Tree
Binary Tree
Full Binary Tree: 每個node都有兩個child

Complete Binary Tree: 從左到奏照順序擺: heap

Ternay Tree
Binary Search Tree
Balanced Tree
Perfect Tree： every level has full nodes
## Tree Traversal
:::info
要有全部Traversal的實做
DLR
LDR
LRD
:::

- in-order traversal
- Typically, for binary search tree, we can retrieve all the data in sorted order using in-order traversal. We will mention that again in another card(Introduction to Data Structure - Binary Search Tree).
- post-order traversal
- is widely use in mathematical expression. It is easier to write a program to parse a post-order expression. Here is an example:
- 

vector<int> inorderTraversal(TreeNode* root) 
{
    vector<int> result;
    TreeNode* visit = root;
    stack<TreeNode*> stree;
    
    while (visit != NULL || !stree.empty())
    {
        if (visit != NULL)
        {            
            stree.push(visit);
            visit = visit->left;
        }
        else
        {
            visit = stree.top();
            stree.pop();
            result.push_back(visit->val);
            visit = visit->right;
        }
    }
    
    return result;
}

lass Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> res;
        
        stack<TreeNode*> stk;
        
        TreeNode* temp = root;
        
        while(temp != NULL || stk.empty() == false)
        {
            while(temp != NULL)
            {
                stk.push(temp);
                temp = temp->left;
            }
            
            temp = stk.top();
            stk.pop();
            res.push_back(temp->val);
            temp = temp->right;
        }
        
        return res;
        
    }
};

  for (std::stack<TreeNode*> dump = st; !dump.empty(); dump.pop())
                std::cout << dump.top()->val << " ";
            cout<<endl;

 vector<int> postorderTraversal(TreeNode* root) {
        if(!root) return {};
        stack<TreeNode*> st;
        TreeNode* visit = root;
        vector<int> path;
        st.push(visit);
        while(!st.empty()){
            visit = st.top();
            st.pop();
            path.push_back(visit->val);
            if(visit->left)  st.push(visit->left);
            if(visit->right) st.push(visit->right);
        }
        reverse(path.begin(), path.end());
        return path;
    }

https://leetcode.com/explore/learn/card/data-structure-tree/134/traverse-a-tree/930/discuss/45551/Preorder-Inorder-and-Postorder-Iteratively-Summarization

## Binary Heaps
:::info
要有Priority Queue的實做
:::
### Insert() + adjust()

### extract_min() + adjust()

## Tries (Prefix Tree)
- N-ary Tree的變形

## Red-Black Tree

# Graph
## adjancey List
## adjancey matrix
## BFS
BFS + queue
- width/breadth
- horizontal
- visit every nodes


## DFS
DFS + stack
- vertical
- 兩點間的最短距離

## Bidirectional Search

## Algo
### Floyd-Warshall
求全部的點到點最短距離O(n^3)
### Topological Sort
### Dijkstra
### AVL Tree

# Bit Operation
## 技巧
## Arthimeticvs vs. Logical right Shift

## Common Bits Tasks
### Get
### Set(set 1)
### Clear(set 0 from 0 to i)

### Update(set 0 or 1)

# Mathematics
## Prime
### sqrt(n)
a*b = n ,必存在b任一數使得 b<sqrt(n)
### The Sieve of Eratosthenes
:::info
code...
:::
## gcd
greatest common divisor

## lcm
least common mutiple

xy = gcd(x,y) * lcm(x,y)

## Probability

### Probability of A and B
### Probability of A or B
### Independence
### Mutual Exclusivity

:::info
找時間補一下條件機率
:::

# Logical Puzzles
## Develop Rules and Patterns
兩條線可以燒1hr 如何算出15min
## Worst Case Shifting
九球一球輕 最多稱兩次天平 如何找出最輕球？

# Design
## Singleton

## Factory

# Recursive + DP
## Approach
Top-Down : Recursive
Bottom-up : DP(Dynamic Programming)
Half-and-Half : Binary Search

## fib
### Recursive

### Cache

### DP

# Sort
## Bubble Sort
## Selection Sort
## Merge Sort
## Quick Sort
## Radix Sort(Bucket Sort)
- counting sort為弱化版 並沒有處理digits

# Search
## Binary Search