2022 年「資訊科技產業專案設計」作業 1

貢獻者: 鳳梨-Pineapple

模擬面試錄影(漢)
模擬面試錄影(英)

141. 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;
}

同儕互評

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

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

英文：

問題和漢一樣

英文可以更清晰一點。

整體：

~~解説method的時候盡量不要動太多滑鼠。~~

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

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

針對 interviewer 的檢討

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

針對 interviewee 的檢討:

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

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

針對 interviewee 的檢討

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