# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 肥俠 (Billy)
> 模擬面試錄影: [1](https://www.youtube.com/watch?v=WCA4Hu7UXr4), [2](https://www.youtube.com/watch?v=VU6L1gBNy1A), [3](https://www.youtube.com/watch?v=rTADVXoSsX4)
> :santa: : interviewer
> :man: : interviewee

## [876. Middle of the Linked List](https://leetcode.com/problems/middle-of-the-linked-list/)
> Easy

### 題目描述
:santa: : 給你一個 singly-linked list 的 `head`，回傳這個 linked list 中間位子的位址。如果中間位子有兩個，則回傳第二個中間位子的位址。其中ListNode的結構只有該 node 的值以及指向下一個位址的指標。
:man: : 請問假如整個 singly-linked list 只有 4 個 node，從 `head` 開始依序為 1、2、3、4 ，那我要回傳 3 的這個 node 的位址嗎?
:santa: : 是的。
:man: : 那我會使用的方法為，先走訪所有的節點，並記錄長度，再利用這個長度，得到我們要求的中間節點的位子，接著回傳該點。這樣的時間複雜度為 $O(n)$，空間複雜度為 $O(1)$。
:santa: : 好的，那你可以將你的想法 coding 出來嗎?
:man: : 好的。

- [ ] 方法 1 : 先得出長度再來求中點的位址

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        int len = 0;
        ListNode *cur = head;
        while (cur) {
            len++;
            cur = cur->next;
        }
        cur = head;
        for (int i = 0; i < len / 2; i++) {
            cur = cur->next;
        }
        return cur;
    }
};

:santa: : 看起來沒有問題，但你有其他方法可以有更好的執行效率嗎?
:man: : 那我可以使用快慢指標，快的指標每一次移動兩步，慢的指標每次移動一步，當快的指標不能再走時，慢的指標就在這時候就會指向中點了。
:santa: : 能更仔細地描述你的快的指標的中止條件嗎?
:man: : 好的，我們可以考慮長度是 3 跟 4 的 singly-linked list，快慢指標同時從 `head` 出發，長度為 3 的 list ，再經過一次的移動，快的指標已經指向這個 singly-linked list 的最後一項的位址了，這時慢的指標指向第二個 node 的位址，正是我們要求的。而長度為 4 的 singly-linked list 再經過第一次的移動，快指標指向第三個 node 的位址，慢的指標指向第二個 node 的位址，再經過一次的移動，快的指標指向不存在的第五個 node ，也就是 NULL pointer，這時慢指標指向第 3 個 node，即為所求。所以我的中止條件會設置成當快指標為 NULL pointer 或是快指標的下一個為 NULL pointer。
:santa: : 好的，那你能將你的想法 coding 出來嗎?
:man: : 好的。

- [ ] 方法 2 : 利用快慢指標來求出

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode *slow = head, *fast = head;
        while(fast && fast->next) {
           slow = slow->next;
           fast = fast->next->next;
        }
        return slow;
    }
};

:man: : 雖然時間複雜度與空間複雜度與前一個方法一致，但利用快慢指標同時移動，不需要再一次從頭開始， while 迴圈約執行 $\frac{n}{2}$ 次。

### 面試過程檢討
#### Interviewer:
- [ ] 待改進
* 0:57: 於interviewee說完方法後感覺可以給些回應或討論或釋疑，例如說You mentioned using the length divided by 2 to find the address of the middle node, did you mean index? Can you elaborate on that? 直接說Yes，can you code it out似乎暗示這就是標準答案，所以yes這樣。

#### Interviewee:
- [ ] 待改進:
* 0:33: 可能是說visit，可是聽起來是fist

### 他評 01
- [ ] 優點
* 咬字清晰，語速適當
* 邊打程式碼邊講解，很讚
* 轉場的音效好可愛XD
* [4:34](https://www.youtube.com/watch?v=WCA4Hu7UXr4#t=4m34s): interviewee 有將例子打下來，方便理解

- [ ] 可改進的地方
* 英語口說卡卡的，要再加強
* [10:34](https://www.youtube.com/watch?v=WCA4Hu7UXr4#t=10m34s) interviewee 說的語意是對的，但小弟覺得可以再口語一點，要說什麼變成一半可以用 half
* 原句: "The while loop approximately runs n divided by 2 times"
* 小小建議: "Compared to the original algorithm, we only need half of the steps."

### 他評 02
- [ ] 優點
* 有字幕
* 講話語速適當，音量夠大聲。
* [3:43](https://www.youtube.com/watch?v=WCA4Hu7UXr4#t=3m43s): interviewer 有跟 interviewee 互動，指出是否有哪些地方可以再延伸。
- [ ] 可改進的地方

* [1:01](https://www.youtube.com/watch?v=WCA4Hu7UXr4#t=1m1s): 在這個地方之前，如 REACTO 的 E 所述， interviewee 事先可以跟 interviewer 討論預期的輸入例子與輸出結果應該會是什麼樣子，像是 Link List 長度奇數偶數可能會怎麼處理。

---

## [70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)
> Easy

### 題目描述
:santa: : 給一個整數 `n`，表示長度為 `n` 的樓梯，你只可以走一步或者兩步，請回傳有多少種方法走完這樓梯。
:man: : 請問長度為 3 的樓梯，先走一步再走兩步，跟先走兩步再走一步，是不同的方法嗎?
:santa: : 是的，排列不同就算不同方法。
:man: : 好的，那我可以採用遞迴的方式，我們已知長度為 `1` 的樓梯只有 1 個方式走完，長度為 `2` 的樓梯有兩種方式，走兩個一步或是一個兩步，以這當作我們的基礎條件，走完長度為 `n` 的樓梯，最後一個動作必為一步或兩步，那這樣方法數就是為走完長度為 `n-1` 的樓梯加上走完長度 `n - 2` 的樓梯的方法，再更簡單來說可以此問題就是費式數列問題求第 `n` 項。
:santa: : 好的，那請你把這方法 coding 出來。
:man: : 好的。
- [ ] 方法 1 : 遞迴

class Solution {
public:
    int climbStairs(int n) {
        if (n < 3) return n;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
};

:santa: : 這看起來很簡潔，但有執行時間上的疑慮，你有更好的方法嗎?
:man: : 那我們可以採用動態規劃，利用一個 array 來儲存已經計算過的值，這樣重新呼叫可以直接從 array 中取出，不用再重複呼叫函式。
:santa: : 好的，那請把你的想法 coding 出來吧。
:man: : 好的。

- [ ] 方法 2 : 動態規劃

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp;
        for (int i = 0; i <= n; i++) {
            if (i < 3) dp.push_back(i);
            else dp.push_back(dp[i - 1] + dp[i - 2]);
        }
        return dp[n];
    }
};

:man: : 這個方法的時間複雜度為 $O(n)$ ，空間複雜度為 $O(n)$。
:santa: : 嗯...，這問題並沒有很複雜，需要用到這麼大的陣列嗎?你有沒有其他方法可以節省空間呢?
:man: : 好的，因為每次計算實際上只需要取用到前兩項的值，我們可以利用暫存器，假設我們已知第 `n - 1` 的值以及第 `n - 2` 的值，將第 `n - 1` 的值放入暫存中，第 `n - 1` 已經被我們儲存起來，所以我們直接將第 `n - 1` 的值加上第 `n - 2` 的值，得到第 `n` 的值，因此我們手上就有剛剛儲存的 `n - 1` 以及剛剛計算出來的第 `n` 的值，我們又可以用同樣的方法來計算第 `n + 1` 的值了。
:santa: : 好的，那請你 coding 出來吧。
:man: : 好的。
- [ ] 方法 3 : space complexity $O(1)$

class Solution {
public:
    int climbStairs(int n) {
        int a = 0, b = 1;
        int tmp;
        for (int i = 0; i < n; i++) {
            tmp = b;
            b += a;
            a = tmp;    
        }
        return b;
    }
};

:man: : 這樣我們只需要 3 個額外的變數就能做完了，時間複雜度仍為 $O(n)$，但空間複雜度減少為 $O(1)$。

### 面試過程檢討
#### Interviewer
- [ ] 優點
* 口條清晰

- [ ] 可進步
* [0:01](https://www.youtube.com/watch?v=VU6L1gBNy1A?t=1): 面試官直接進入正題確實省時間，但應該可以自我介紹一下
* [8:08](https://www.youtube.com/watch?v=VU6L1gBNy1A?t=488): 滑鼠框到太多東西，哪個值應該指清楚

#### Interviewee
- [ ] 優點:
* 口條清晰

- [ ] 可改進的地方
* [0:33](https://www.youtube.com/watch?v=VU6L1gBNy1A?t=33): 在進入approach之前可以舉個小例子，比如說n = 1,2,3,4,5的狀況。另外如果口頭解釋approach以外，再輔以視覺呈現的解釋會更一目了然(在螢幕上解釋)
* [9:01](https://www.youtube.com/watch?v=VU6L1gBNy1A?t=541): temp寧可就直接念temp，不然說temperature變成溫度顯得語意不清

### 他評 01
- [ ] 優點
* [5:09](https://www.youtube.com/watch?v=VU6L1gBNy1A#t=5m9s): interviewee 舉例說明，並且每一個步驟的詳細記錄，簡單明瞭！

- [ ] 可改進的地方
* [2:22](https://www.youtube.com/watch?v=VU6L1gBNy1A#t=2m22s): interviewer 的回應是「這看起來很簡潔，但有執行時間上的疑慮，你有更好的方法嗎？」，感覺回應可以多一點，比較有互動的感覺，像是細講 interviewer 的疑慮是什麼?

### 他評 02
- [ ] 優點
* 題目層層遞進， interviewer 有加以延伸同一個題目的解法。
* 有探討到時間複雜度與空間複雜度。
* 口條清晰。

- [ ] 可改進的地方
* [4:32](https://www.youtube.com/watch?v=VU6L1gBNy1A#t=4m32s) 的部分可以再多加以說明解題思路，為什麼 vector 裡面的數字 n 位等於 n-1 位加上 n-2 位。而這個 n 位是該數字 1 與 2 加總的所有組合。也就是費式數列為什麼與這題有關。

---

## [199. Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/)
> Medium

### 題目描述
:santa: : 給定一個二元樹的 `root` ，回傳此二元樹每一層最右邊的值。
:man: : 如果是只有兩層的二元樹，第二層沒有右子點，那就是回傳左子點的值嗎?
:santa: : 是的，不要忘記要回傳的是個陣列， `root` 的值也要放進去要回傳的陣列裡面。
:man: : 了解，順序有要求嗎?從上到下或從下到上。
:santa: : 有的，回傳順序要從上到下。
:man: : 我將每一層的節點依序從左到右放入陣列中，可以知道該層有幾個節點，再透過迴圈將下一層的每個節點放入陣列，再將上一層的資料都刪除。因為我們每一層都是由左到右的放入陣列中，所以我們將陣列最後一項放入要回傳的陣列，然後直到沒有東西能放入陣列了，我們就做完了。
:santa: : 好的，請你把這想法 coding 出來。
:man: : 好的。

- [ ] 方法 1 : 用陣列記錄每一層的所有節點

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<TreeNode *> a;
        a.push_back(root);
        vector<int> ret;
        if (!root) return ret;
        while(!a.empty()) {
            int number = a.size();
            ret.push_back(a[number - 1]->val);
            for (int i = 0; i < number; i++) {
                if (a[i]->left) a.push_back(a[i]->left);
                if (a[i]->right) a.push_back(a[i]->right);
            }
            for (int i = 0; i < number; i++) {
                a.erase(a.begin());
            }
        }
        return ret;
    }
};

:man: : 因為我們會遍歷所有的節點，因此時間複雜度為 $O(n)$，我們要額外儲存每一層的節點，最差情況的空間複雜度為 $O(n)$。
:santa: : 可以說出最差情況的空間複雜度為何是 $O(n)$ 嗎?
:man: : 如果這二元樹為完滿二元樹，最後一層會有 $\frac{n + 1}{2}$ 個節點，因此空間複雜度為 $O(n)$。
:santa: : 那你有其他想法來優化，或是有其他的演算法來實現嗎?
:man: : 好的。我可以改用 DFS 來實作，總是先往右子樹走，右子樹不能走後才往左邊走，每一步都會記錄走到哪一層，因題目敘述，回傳的陣列長度會等於這二元樹的總層數，每一步檢查是不是走到該點的層數已經大於回傳的陣列的長度了，如果大於了，代表要將目前的位址的值存入陣列，否則繼續走。
:santa: : 好的，請你將這個方法 coding 出來。
:man: : 好的。
- [ ] 方法 2 : 利用 DFS

class Solution {
public:
    void find(vector<int> &ret, TreeNode *root, int level) {
        if (ret.size() <= level)
            ret.push_back(root->val);
        if (root->right) find(ret, root->right, level + 1);
        if (root->left) find(ret, root->left, level + 1);
        return;
    }

    vector<int> rightSideView(TreeNode* root) {
        vector<int> ret;
        if (!root) return ret;
        find(ret, root, 0);
        return ret;
    }
};

:man: : 時間複雜度為 $O(n)$ ，因為還是會遍歷所有的節點，除了要回傳的資料以外沒有用到其他空間，平均空間複雜度就是 $O(\log n)$ ，如果這棵樹很不平衡的話，那空間複雜度也會到 $O(n)$。

#### Interviewer
- [ ] 可改進的地方
* [7:10](https://www.youtube.com/watch?v=rTADVXoSsX4?t=430): 覺得面試官可以在說明要用面試者用其他演算法時做之前先說明目前問題在哪?
* [7:22](https://www.youtube.com/watch?v=rTADVXoSsX4?t=442): 這時候就可以問為什麼用DFS? 或是在第二種方法講完時，請面試者自己提出如何優化。

#### Interviewee
- [ ] 可改進的地方
* [12:28](https://www.youtube.com/watch?v=rTADVXoSsX4?t=748): 可以把空間複雜度為O(N)的狀況說完，說完左傾右傾樹，所以ret需要存N node。

### 他評 01
- [ ] 優點
* 程式碼很整齊。
* 有針對 tree 的各種情況去討論複雜度，讚讚。

- [ ] 可改進的地方
* interviewer 可以設定一些應用場景，使用引導的方式帶出題目，針對這一題，我有一些想法(可能沒有很好，但可參考看看):
* 在資料儲存上，我們常常會使用 tree 的結構以方便搜尋，通常數值大會放右邊，數值小的會放左邊，在這樣的情況下我們可以發現，Binary Tree Right Side View 剛好就是這棵 tree 前幾大的 nodes，可以幫助我們搜尋最感興趣，或是優先度最高的資料。

### 自評
- [ ] 優點
* 在講解程式碼，我最在意的地方是當有 while 迴圈時，我會注意終止條件為何要這樣設定，在影片中，我都有確實的講解，我覺得我要保持下去。
* 講解時，有用例子配合，好讓面試官更能了解我的想法。

- [ ] 可改進的地方
* 英文不好...， temporary 被我說成 temperature ，可能會讓聽者誤解，要注意，沒有把握寧願就講 temp 。
* 在利用其他演算法來實作，沒有提到為何要使用這樣的演算法，應該要講解才對，儘管是用直覺，也應該說明。
* 面試官的作用除了請人寫程式碼以及出題以外，作用不太大，應該多加點互動的，多提問，或改題目。

### 他評 02
#### interviewer
- [ ] 優點
* 第二題有連續兩個 follow up，能更好的看出面試者能不能不斷改進程式碼

- [ ] 可改進的地方
* 第二題說有執行時間上的疑慮前，可以先請對方分析時間複雜度，或是先討論這件事，不然結論可能會來得太武斷（說有疑慮就有）。
* 可以加強某些英文單字的發音，可以先特別注意專業用語
- fix
- address
- current
- complexity

#### interviewee
- [ ] 優點
* 有把範例寫在文件上，同時解釋
* 第二題第三個版本，舉例的寫法很清楚

    1 1 2 3 5 8
    a b
      a b
        a b

- [ ] 可改進的地方
* 英文單字發音，同上
* 第二題在解釋數學題目時，可以同時寫在文件上，更好理解是費氏數列，如: `S(n)=S(n-1)+S(n-2)` 或 `S(3)=S(2)+S(1)`