# Homework 1
Author: 郝仁 / Goodman
## 20. Valid Parentheses
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
> 程式碼中的註解寫的是在面試當下應該用口語表達出的內容
### 版本一
#### 程式運作原理
使用 `stack` 來儲存最近的左括號，當程式讀取到右括號得時候，即可用 `stack` 的頂端去判斷當前的字符串是不是合法的。

#### 程式碼

class Solution {
    public boolean isValid(String s) {
        // 首先我們需要一個 stack
        Stack<Character> stack = new Stack<>();
        // 接著我們用一個 for 循環去走訪所有字符
        for (Character c : s.toCharArray()) {
            // 如果讀取到左括號，就把括號放進 stack 中。
            if (c.equals('(')) {
                stack.push(c);
                // 之後 continue
                continue;
            }
            if (c.equals('{')) {
                stack.push(c);
                continue;
            }
            if (c.equals('[')) {
                stack.push(c);
                continue;
            }

            // 如果不是左括號，那必定是右括號，如果遇到右括號的時候 stack 為空，代表沒有相對應的左括號，可以直接返回 false
            if(stack.empty()) return false;

            if (c.equals(')')) {
                if (stack.peek() == '(') {
                  stack.pop();
                  continue;
                }
            }

            if (c.equals('}')) {
                if (stack.peek() == '{') {
                  stack.pop();
                  continue;
                }
            }

            if (c.equals(']')) {
                if (stack.peek() == '[') {
                  stack.pop();
                  continue;
                }
            }
            // 如果不是上述的情況，代表輸入的字符串是不合法的，返回 false
            return false;
        }
        // 最後再檢查一次 stack 是不是空的，如果非空就代表是不合法的。
        return stack.empty();
    }
}

### 版本二
#### 改進
原本的程式碼之中類似的地方太多，我們可以透過替換推入棧中的值，來精簡程式碼。把推入棧中的值改成相對應的右括號，在進行右括號的比較時即可復用同一份程式碼。

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (Character c : s.toCharArray()) {
            // 我們把推進 stack 的東西改成右括號
            if (c.equals('(')) {
                stack.push(')');
                continue;
            }
            if (c.equals('{')) {
                stack.push('}');
                continue;
            }
            if (c.equals('[')) {
                stack.push(']');
                continue;
            }
            if(stack.empty()) return false;
            // 在比較的時候，直接比較棧頂是不是和當前的字符相同
            if (c.equals(stack.peek())) {
                stack.pop();
                continue;
            }
            return false;
        }

        return stack.empty();
    }
}

### 版本三
#### 題目變化
要求接收一個新的參數 `parentheses`:

String[] parentheses = new String[]{"{}", "[]", "[]"};

這個參數用來傳遞需要背判斷的括號種類。
#### 改進
原本的括號適用 hard code 寫死在程式碼裡面的，每次要改都會很麻煩，如果用參數的形式傳遞進去，程式碼的彈性會更大，且可以進一步精簡程式碼。對於如何查詢左右括號兩兩對應的關係，可以用 HashMap 去紀錄左括號對應的右括號。

#### 程式碼

class Solution {
    public boolean isValid(String[] parentheses, String s) {
        Stack<Character> stack = new Stack<>();
        // 我們需要一張表去查詢左括號對應的右括號，所以我這邊用一個 HashMap 來記錄。
        Map<Character, Character> parentheseDic = new HashMap<>();
        // 建立可以用來查詢的表
        for (String p : paratheses) {
            parentheseDic.put(p.charAt(0), p.chartAt(1))
        }

        for (Character c : s.toCharArray()) {
            // 這邊和原本的步驟一樣，如果是左括號，就把相對應的右括號放進 stack 中
            // 所以我們可以用 containsKey 去檢查是不是左括號，如果是的話把值，也就是右括號塞入 stack 中
            if(parentheseDic.containsKey(c)) {
                stack.push(parentheseDic.get(c));
                continue;
            }

            if(stack.empty()) return false;
            if (c.equals(stack.peek())) {
                stack.pop();
                continue;
            }
            return false;
        }

        return stack.empty();
    }
}

### 檢討
1. 花更多時間了解 stack 的應用。
2. 提出更複雜的應用場景，並對此做出相應的改動。
3. Interviewer 看見 interviewee 程式碼刪除沒有刪除乾淨的時候，應該當場指出錯誤。

## 121. Best Time to Buy and Sell Stock
You are given an array prices where `prices[i]` is the price of a given stock on the $i^{th}$ day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
### 版本一
#### 運作原理
透過窮舉的方式找出所有的日期區間，並比較這些區間的獲利。
#### 程式碼

class Solution {
    public int maxProfit(int[] prices) {
      // 首先我們需要一個值去紀錄最大的收益
      int max = 0;
      // 然後需要一個 for 循環。第一層的 for 只要到陣列的倒數第二個數就好了，因為不能當天買入當天賣出
      for (int i = 0; i < prices.length - 1; i++) {
        // 第二層的 for 循環從i+1開始，因為賣出的日期一定要在買入之後。
        for (int j = i + 1; j < prices.length; j++) {
          // 如果說當前日期組合的收益比過往的紀錄高，就更新 max
          max = Math.max(max, prices[j] - prices[i]);
        }
      }
      // 最後答案就返回 max
      return max;
    }
}

### 版本二
#### 改進
任意一天的股票售價 $price[i]$ 能夠帶來的最高獲利是減去在第 $i$ 天之前的最低售價，為了要讓時間複雜度來到 $O(n)$，我們只能對整個進行一次讀的動作，因此需要維護一個變量 $min$ 去紀錄在 $i$ 之前的最小值，透過這個變量，我們可以不用嵌套循環就可以找到當前天數獲利的最大值。
#### 程式碼

class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        // 我們這邊新增一個變量去紀錄股票市值最小的一天，並且把第一天設為初始值
        int min = prices[0];
        // 因為不能同一天買進賣出，所以可以從第二天開始，也就是 i = 1
        for (int i = 1; i < prices.length; i++) {
            // 如果當前的股價比有記錄到的最小值還小，就更新最小值。
            if(prices[i] < min) {
                min = prices[i];
                continue;
            }
            // 不然我們就計算獲利，如果獲利比記錄過的最大值還大，就更新
            max = Math.max(prices[i] - min, max);
        }

        return max;
    }
}

### 衍伸題目 122. Best Time to Buy and Sell Stock II
You are given an integer array prices where `prices[i]` is the price of a given stock on the $i^{th}$ day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.
#### 運作原理
任何一天的獲利都應該加總到結果之內，所以我們可以計算每兩天中間的獲利值，如果是正數就收集起來。這樣就能夠在只循環一次的情況下取得最高獲利。
#### 程式碼

class Solution {
    public int maxProfit(int[] prices) {
        // 我們需要一個變量去記錄總收益。我們把這個變量命名為total
        int total = 0;
        // 這邊我們需要對陣列進行一次循環。每個間格都要計算一次收益，總共有 n-1 個間隔
        for (int i = 0; i < prices.length-1; i++) {
            // 該次間隔的獲利就是後一天的價錢減去前一天的價錢
            int profit = prices[i+1] - prices[i];
            如果獲利是正數，就加入總收益之中。
            if (profit > 0) total += profit;
        }
        // 最後回傳 total
        return total;
    }
}

### 檢討
1. 進一步整合說話與打字，必須要能夠邊打邊說
2. 用其他時間朗誦英文，讓自己的舌頭熟悉發音的方式。

## 73. Set Matrix Zeroes(Deprecated)
### 程式碼
Version 1

class Solution {
    public void setZeroes(int[][] matrix) {
        int rowCount = matrix.length;
        int columnCount = matrix[0].length;

        boolean[] rowFlag = new boolean[matrix.length];
        boolean[] columnFlag = new boolean[matrix[0].length];

        for (int i = 0; i < rowCount; i++) {
          for (int j = 0; j < columnCount; j++) {
            if (matrix[i][j] == 0) {
              rowFlag[i] = true;
              columnFlag[j] = true;
            }
          }
        }

        for (int i = 0; i < rowCount; i++) {
          for (int j = 0; j < columnCount; j++) {
            if (rowFlag[i] || columnFlag[j]) {
              matrix[i][j] = 0;
            }
          }
        }
    }
}

Version 2

class Solution {
    public void setZeroes(int[][] matrix) {
        int rowCount = matrix.length;
        int columnCount = matrix[0].length;
        boolean firstColumn = false;
        boolean firstRow = false;
        for (int i = 0; i < columnCount; i++) {
            if (matrix[0][i] == 0) {
                firstRow = true;
            }
        }
        for (int i = 0; i < rowCount; i++) {
            if (matrix[i][0] == 0) {
                firstColumn = true;
            }
        }
        for (int i = 1; i < rowCount; i++) {
            for (int j = 1; j < columnCount; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        for (int i = 1; i < rowCount; i++) {
            for (int j = 1; j < columnCount; j++) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (firstRow) {
            for (int i = 0; i < columnCount; i++) {
                matrix[0][i] = 0;
            }
        }
        if (firstColumn) {
            for (int i = 0; i < rowCount; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

#### 程式運作原理
透過第一行與第一列當作標誌位去儲存該行或列之中是否有出現過0。由於第一行和第一列共用同一個標誌位，因此需要額外的一個變量去紀錄第一行或是第一列是否有出現0。
### 問題
1. 在已知有改善空間的情況下沒有做出相對應的修正。
2. 一邊打字就很難一邊說話。
### 改進方案
1. 下次不要把時程安排得這麼緊，就能夠有更多時間思考改善的空間和劇本。
2. 增加練習的次數，透過練習來習慣這種新的寫程式方式。

# Homework 3
## 歐帝-Odd
[HackMD](https://hackmd.io/@sysprog/BJ9DmAArF)
第一題:
1. Interviewer 直接給題目，容易讓背答案的人直接寫出來。
2. Interviewee 重複題目的時候只要講大概的意思就好，不用完全重複。
3. Interviewer 在對方講出要用暴力解的時候，應可以直接引導給出更好的答案。
4. Interviewer 基本上沒有互動。

第二題:
1. Interviewer 直接給題目，容易讓背答案的人直接寫出來。
2. Interviewee 在給例子的時候可以在螢幕上打出來，而不是只是用念的。
3. Interviewee 應用更嚴謹的說法表達時間複雜度為 O(n) 等級，而不是直接說時間複雜度是 O(n)。應該清楚的表達空間複雜度為 O(n)，而不是說用到的 space 是O(n)
4. Interviewee 講解所用的演算法的時候講的不清楚，如何進行抵銷、判斷等步驟，對第一次聽到這個演算法的人來說並沒有辦法從解釋中知道演算法具體如何實現。

第三題:
1. Interviewer 直接給題目，容易讓背答案的人直接寫出來。
2. Interviewee 應該確認移動後的陣列是否是把移出陣列的值填充到陣列開頭。
3. Interviewee 口語上不要講這樣子那樣子，用更明確清晰的方法表達。
4. Interviewee 講解程式的時候應該更多的解釋該行程式的意圖，而不是單純復述一遍寫了什麼東西。
5. Interviewer 在對方寫完之後，沒有講說到底哪裡做得不錯，或者哪裡做得不好。

## 齋羅 Zxiro
[HackMD](https://hackmd.io/@sysprog/rygfn6XLK)
整體問題:
1. 聲音太小

第一題:
1. Interviewee 回答問題時不要中英夾雜。
2. Interviewee 變量命名時如果要用 node a 當變量的名稱，應該使用 `nodeA` 或 `node_a`而不是`nodea`。
3. Interviewer 沒有根據這一題做出具體評價與互動，應該講出不錯是哪裡不錯。

第二題:
1. Interviewer 直接給題目，容易讓背答案的人混水摸魚。
2. 不要用反白或是游標位置去進行講解，Google meeting 或 Zoom 可能會讓 interviewer 看到不同的畫面。
3. Interviewee 在編寫程式碼的時候應該注意可讀性，符合業界要求的風格。舉例來說，變量和操作符之間該空格的地方要空格。
4. Interviewee 在解釋的時候慎用手勢。

第三題:
1. Interviewer 直接給題目，容易讓背答案的人混水摸魚。
2. Interviewee 在表達 a's start 的時候，要注意打出來的符號是不是符合自己想表達的意思。
3. [24:52] Interviewee 應該可以花更少的時間以及用更簡單的方式去定義什麼叫做「重疊到」。
4. [26:24] Interviewee 圖像化區間的方式很清楚，是個好方法。
5. [28:37] Interviewee 不要嘆氣。
6. Interviewee 花太多時間講解自己給出的例子，從 interviewer 給出題目後超過 7 分鐘都還沒有寫第一行程式。
7. [30:05] Interviewer 其實有說重疊到算不算，但 interviewee 這邊表示對方沒說。Interviewee 可能漏聽或忘了，這時候 Intervier 應該出來指正。
8. [34:34] Interviewee 不用把自己的範例刪掉。
9. Interviewee 最後沒有驗證自己程式碼的正確性。
10. Interviewer 最後沒有表達對於 interviewee 的程式的任何評語，應該有更多的互動。