---
tags: info2022-homework1
---

# 2022 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2022)」作業 1
> 貢獻者: 鳳梨-Pineapple

> [模擬面試錄影(漢)](https://youtu.be/tytmRjBKi_8)
> [模擬面試錄影(英)](https://youtu.be/fWPMz2cn1qI)

## [141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/)

### 題目描述
給定一個 linked list 的 `head`，判斷 linked list 中是否存在環。

如果 linked list 中有某個節點可以通過不斷跟隨 `next` 指針再次到達，則 linked list 中存在一個循環。在內部，`pos` 用於表示 `tail` 的 `next` 指針所連接的節點的索引。請注意，`pos` 不作為參數傳遞。

如果 linked list 中存在循環，則返回 true。否則，返回 false。

### 解題方法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

bool hasCycle(ListNode *head) {
    ListNode *fast = head, *slow=head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) return true;
    }
    return false;
}

### 同儕互評
<s>
漢：
interviewer：
- interviewer應該給一些評論interviewee或再討論一下method。之後再開始寫code。
- interviewer 應該再和interviewee 做跟多的討論。（如討論衍生的問題或對他提出的方法做跟多的討論，又或是有沒有其他的方法等）避免interviewee背答案的可能。

interviewee：
- interviewee 該和 interviewer 做交流。不該急著給答案，不然看起來就像是被好題目面試。面試重點在交流，其次是解決問題。

英文：
- 問題和漢一樣
- 英文可以更清晰一點。

整體：
- 解説method的時候盡量不要動太多滑鼠。
</s>

:::warning
上方的「心法」不能算是「檢討」，要具體幫助 interviewer/interviewee 改進面試過程才是「檢討」的本意，應該指出時間軸幾分幾秒要作什麼改進，什麼話該說清楚、什麼又該避免，又能怎樣改進「內容」本身。
:notes: jserv
:::

針對 interviewer 的檢討
* [00:04](https://youtu.be/tytmRjBKi_8?t=4): 避免說「面試官」，這對溝通沒幫助，還會營造距離感，更不要說「直接開始吧」。interview 著重在「交互」的「看法」，之所從 LeetCode 取題，只是縮減準備的成本，但若帶入考試的思維，那就違反「溝通」的初衷。以 [141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/) 來說，之所以 [cycle detection](https://en.wikipedia.org/wiki/Cycle_detection) 會是經典的演算法，就在於一連串的問題圍繞在此，例如在密碼學中的 PRNG 就要面對環狀與否的偵測。interviewee 舉出的 Floyd 演算法只是其中一種解法，尚有很多手段，例如 [R. W. Gosper 提出的演算法](https://en.wikipedia.org/wiki/Cycle_detection#Gosper's_algorithm)，真正的難題是時間和空間的取捨。這些是 interviewer 可在一開頭就指出，並期望 interviewee 予以互動的題材。
* [00:06](https://youtu.be/tytmRjBKi_8?t=6): 不要說「第一題」，改說「首先我們考慮 ___ 的情境」，避免 interviewee 賴皮地說「可以先跳過第一題，讓我看其他題目嗎？」(典型的台灣考生心態，以投機博取最大效益)，如上所提，面試的關鍵是「溝通」，題目只是輔助
* [00:11](https://youtu.be/tytmRjBKi_8?t=11): 避免頻繁使用滑鼠移動，既然題目很好理解，直接依序閱讀節點中的數值，如 `2` 和 `-4`，尤其在視訊會議中，更要留意溝通的效率，否則徒增 interviewee 視覺疲乏
* [00:33](https://youtu.be/tytmRjBKi_8?t=33): 應清楚標注是 singly-linked list 還是 doubly-linked list
* [00:48](https://youtu.be/tytmRjBKi_8?t=48): 避免說「底下幫你打好了這個 linked list 的 data structure」，至此僅有名為 `ListNode` 的結構體，但資料結構著重「資料」本身如何相互連結和組織，這顯然不在此刻具備。可改說「假設該鏈結串列由名為 `ListNode` 的結構體所組成，定義如下」，寧可說得慢，但要精準，這是應徵者對公司技術人員的初步印象
* [00:54](https://youtu.be/tytmRjBKi_8?t=54): 不要說「如果你有想法了，就可以告訴我」，面試本來就要「溝通」，而好的面試更是一種「表演」，節奏自然是關鍵，可改說「請你針對上述的條件撰寫程式碼，你不用寫出完整可執行的程式，先告知想法和關鍵程式碼，稍候我們可詳談」
* [05:05](https://youtu.be/tytmRjBKi_8?t=305): 不要說「好，那我們直接進入到下一題吧」，一來讓人覺得你敷衍 (這種裝可愛的話語，還是留給 HR 管理師來說)，二來因為 interviewee 像在背誦答案，於是可加上 follow-ups，例如:
* 「針對 doubly-linked list，是否依舊有效？能否加速偵測？」
* 「倘若改為 doubly-linked list，且可能存在多個 cycle，你的程式碼要如何變更，才能偵測到所有的 cycle 呢？」

針對 interviewee 的檢討:
* [01:07](https://youtu.be/tytmRjBKi_8?t=67): 在黑色主題的環境中，吊掛的藍色上衣很搶眼。在視訊會議中，儘量保持樸素，自己是面試「表演」的男/女主角，只要有助於他人聚焦在自身的調整，都該留意
* [01:10](https://youtu.be/tytmRjBKi_8?t=70): 在 REACTO 階段的重複題目，不用完整說一次 interviewer 的描述，反而該加上帶有自身特性/認知的素材，例如可說 PRNG 中可見到環狀結構的偵測，或是直接用範例的 $[2] \to [0] \to [-4] \to [2]$ 來解說，畢竟這很直覺，不過仍該確認是 singly-linked list 並強調後續的程式碼是針對這樣的條件 (稍候 interviewer 或許會有 follow-ups，例如可針對 doubly-linked list)
* [01:16](https://youtu.be/tytmRjBKi_8?t=76): 若存在 cycle，圖中的 `-4` 就不能叫做 tail，注意用語
* [01:25](https://youtu.be/tytmRjBKi_8?t=85): 沒必要說「我需要要做的就是...」，因為 interviewer 已說過，除非需要澄清或者請求 interviewer 給予更多的條件/限制/調整，否則不用重複 interviewer 提出的回傳值描述
* [01:35](https://youtu.be/tytmRjBKi_8?t=95): `NULL` 讀作 [nʌl/] (音似 **no**)，不要發「怒偶」，它沒有「怒」，是你的英文老師很生氣
* 參見 [台灣工程師常唸錯的英文單字](https://blog.privism.org/2012/06/blog-post.html)
* [YouGlish](https://youglish.com/) - Use YouTube to improve your English pronunciation，直接幫你列出 YouTube 上關於某個單字的發音片段
* [01:51](https://youtu.be/tytmRjBKi_8?t=111): 避免說「這題的話，我會想用 ___ 」的答覆，題目是溝通過程的一部分，不是主角，可改說「針對這個經典問題，我想到...」，注意「**這個經典問題**」的說法，隱含你看過很多題目並親自解決過，若這題回答不錯，interviewer 應該會指派更能看出你能力的題目。不要說「快慢指針」，一來 pointer 的繁體中文是「指標」，二來「快慢指標」不是經典演算法的描述，改說「我預計用二個移動速度不同的指標/索引，來走訪鏈結串列的節點，倘若移動快的指標/索引會在某個時間點遇到移動慢的對方，那就表示存在 cycle，一如在操場跑步的情境」
* [04:54](https://youtu.be/tytmRjBKi_8?t=294): 應該檢驗程式碼是否正確，倘若你知道其他 [cycle detection](https://en.wikipedia.org/wiki/Cycle_detection) 演算法，此刻可提出討論

---

## [814. Binary Tree Pruning](https://leetcode.com/problems/binary-tree-pruning/)

### 題目描述
給定一個 binary tree 的 `root`，返回同一棵 binary tree，其中每個不包含 `1` 的子樹（給定樹的）都會被刪除。

節點的子樹是節點加上作為節點後代的每個節點。

### 解題方法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

TreeNode* pruneTree(TreeNode* root) {
    if (!root) return NULL;

    root->left = pruneTree(root->left);
    root->right = pruneTree(root->right);

    if (!(root->left && root->right) && root->val == 0) 
        return NULL;
    else
        return root;
}

### 同儕互評

針對 intervier 的檢討
* [05:10](https://youtu.be/tytmRjBKi_8?t=310): 說明題目前，可總結 interviewee 在前一次的表現，例如可說「剛才 Linked List Cycle 的程式碼，讓我看到你在鏈結串列處理的認知，現在擴充為樹狀結構」這樣的引導話
* [05:12](https://youtu.be/tytmRjBKi_8?t=312): 修剪 (pruning) 二元樹也是經典問題，出題時最好附上可能的應用場景，可說「我們公司最常用的版本控制系統是 git，其歷史紀錄是用有向無環圖（DAG, [Directed Acyclic Graph](https://en.wikipedia.org/wiki/Directed_acyclic_graph)）來表示，我們常會依循某個分支 (branch) 發展的方向，去合併到不同的支線，甚至去刪除某個分支。倘若我們把 git 分支刪除的動作叫做修剪，並把有向無環圖改為二元樹，現在我們要把修剪的動作在二元樹上達成...」，這樣一來可避免 interviewee 背誦答案，二來可介紹公司內部主要使用的版本控制系統
* 參見 [Viewing the DAG](https://subscription.packtpub.com/book/application-development/9781782168454/1/ch01lvl1sec11/viewing-the-dag)
* [10:25](https://youtu.be/tytmRjBKi_8?t=625): 面對 interviewee 這樣疑似背誦答案的狀況，就要有 follow-ups，而且這題變形的空間很大，例如把 binary 的條件改為某個集合，以及不使用遞迴也不能用堆疊模擬遞迴的方式，如何達成同樣的目標

針對 interviewee 的檢討
* [06:15](https://youtu.be/tytmRjBKi_8?t=375): 不該說「沒有 1 的子樹」，因為
* 「沒有 1」可能讓人誤會，應該是「節點的內含值全部不是 1 的子二元數」
* 由於台灣人發音很難區分「ㄓ」和「ㄗ」，在視訊會議中更容易誤會 (看不清楚口型)，「子樹」會讓人誤會是「指數」，於是可改說 subtree
* [06:31](https://youtu.be/tytmRjBKi_8?t=391): node 的發音是 [noʊd]，而非 [nɑːd]，後者是 [nod](https://dictionary.cambridge.org/dictionary/english/nod)，這樣 leaf node 發音就類似 "leave nod"，令人誤會。REATO 的 Example 和 Approach 階段沒有完成，應該要舉例，這題可說「由左下往右上，順序為 $[1] \to [0] \to [1]$」
* [07:57](https://youtu.be/tytmRjBKi_8?t=477): 既然面試是一場「表演」，此刻不該說「那我就直接開始」，interviewer 想跟你溝通，結果過了三分鐘才說「開始」，那之前的難道在調情嗎？
* [08:17](https://youtu.be/tytmRjBKi_8?t=497): 之前沒有解釋你的遞迴形式和終止條件，到了程式碼解說，就可能讓人無法理解你的思維。之所以會有 REACTO，就是希望面試有「節奏」可言。說了很多，但為何不講關鍵的 DFS 呢？
* [08:33](https://youtu.be/tytmRjBKi_8?t=513): 看！有帥哥
* [08:34](https://youtu.be/tytmRjBKi_8?t=514): 「修剪完之後要接入到左邊的 left pointer」這樣的陳述就算是文字表達，也不算清晰，更別是口說，避免非必要中英夾雜，後續的「也要對右邊重複的再做一遍」則有誤導的狀況，「重複」用字不精準
* [08:57](https://youtu.be/tytmRjBKi_8?t=537): 這段程式碼撰寫前，應該用 REACTO 的 Example 來佐證

另一種可能實作: (更好解說)

static int dfs(struct TreeNode *root) {
    if (!root) return 0;
    int L = dfs(root->left), R = dfs(root->right);
    if (!L) root->left = NULL;
    if (!R) root->right = NULL;
    return root->val | L | R;
}

static struct TreeNode* pruneTree(struct TreeNode *root) {
    dfs(root);
    if (!root->left && !root->right && !root->val)
        return NULL;
    return root;
}