# Mock Interview 1

## Question 1

class Stack {
private:
    vector<int> container;
public:
    void pop();
    void push(int val);
    int top();
}

void Stack::pop(){
    if(container.empty()){
        throw();
    }
    container.pop_back();
}
void Stack::push(int val){
    container.push_back(val);
}
int Stack::top(){
    container.back();
}

## Question 2

int fibnocci(int num){
    // 1 1 2 3 5 8
    // 1 1
    //   1 2
    //     2 3
    // if(num < 3) return 1;
    // int dp1 = 1;
    // int dp2 = 1;
    // for(int i = 3; i <= num; ++i){
    //     int temp = dp2;
    //     dp2 = temp+dp1;
    //     dp1 = temp;
    // }
    // return dp2;
    if(num == 1) return 1;
    if(num == 2) return 1;
    
    return fibnocci(num-1) + fibocci(num-2);
}

T(n)=O(2^n)
S(n)=O(n)

## Question 3
- 給你一個 stair，踩到每一階有它需要花的 cost，你可以跨一到二階。計算花最少的 cost 走出。
- e.g. \[1,2,6,3,4,3,4,9,4\]

int minCost(vector<int> stairs){

    int n = stairs.size();    
    // vector<int> costStairs(n, 0);
    // costStairs[0] = 0;
    // costStairs[1] = 0;
    // 1, 2, 6, 3, 4, 3, 4, 9, 4
    // 1, 2, 3, 4, 5, 6, 7, 8, 9
    // 0, 0, 1, 2, 5, 5, 8, 8, 12, ans: 16
    int onefloorbefore = 0;
    int twofloorbefore = 0;
    
    for(int i = 2; i < stairs.size(); ++i){
        costStairs = min(onefloorbefore + stairs[i-1], \
                        twofloorbefore + stairs[i-2]);
    }
    return min(costStairs[n-2] + stairs[n-2], \
              costStairs[n-1] + stairs[n-1]);
}

## Question 4

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

void dfs(vector<vector<char>> map, int x, int y){
    int m = map.size();
    int n = map[0].size();
    if(x < 0 || x >= m || y < 0 || y >= n) return;
    if(map[i][j] == '0') return;
    map[i][j] = '0';
    // mxn
    dfs(map, x+1, y);
    dfs(map, x-1, y);
    dfs(map, x, y-1);
    dfs(map, x, y+1);
}
int landCounter(vector<vector<char>> map){
    int m = map.size();
    int n = map[0].size();
    int counter = 0;
    // mxn
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(map[i][j] == '1'){
                counter++;
                dfs(map, i, j);
            }
        }
    }
    return counter;
}

https://hackmd.io/@chiashengchen/B1cB1ztDt
https://hackmd.io/@chiashengchen/B1YUxEdcF
https://hackmd.io/@chiashengchen/r1iS3jKcK
https://hackmd.io/@chiashengchen/S1wKOx0ct
https://drive.google.com/file/d/17IVHbxeDLxUjkUY13vTaBXwW0o15tAWN/view?usp=sharing
https://hackmd.io/@chiashengchen/Sy_tTnpZ5