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

貢獻者: 屎地芬森-Stevenson
模擬面試錄影: 中+英
👹 : interviewer
👾 : interviewee

21. Merge Two Sorted Lists

測驗說明與問答

👹 : 屎地芬森先生你好，給你兩個linked list, 節點的順序都依照節點裡面的值排序好了, 請把它們合併然後回傳給我合併後的linked list head, 可以闡述你打算使用的解答做法, 然後實作
👾 : 我們先預設這個題目是升序排列的, 我的工作會是需要把list1, list2給合併成mergeList並且回傳list head
首先我的相法認為我們可以利用merge sort當中merge的做法來處理
一開始我會先定義一個結構體struct node如下

struct node {
    int val;
    struct node *next;
}

👾 : 這裡使用的linked list是singly linked list
👾 : 接著考慮兩種特例也就是list1或list2其中一個為空, 或者兩者都為空的時候, 直接回傳即可
👾 : 接下來處理一般情況可以遞迴的處理, 每次挑出要加入mergeHead的node後, 把剩下的linked list繼續傳入merge當中處理

struct node *merge(struct node *list1, struct node *list2)
{
    struct node *mergeHead;
    if (!list1)
        return list2;
    if (!list2)
        return list1;
    
    struct node *cur_node1, *cur_node2;
    cur_node1 = list1;
    cur_node2 = list2;
    
    if (cur_node1->val > cur_node2->val) {
        mergeHead = cur_node2;
        mergeHead->next = merge(list1, list2->next);
    } else {
        mergeHead = cur_node1;
        mergeHead->next = merge(list1->next, list2);
    }
    
    return mergeHead;
}

👹 : cur_node1, cur_node2是否有存在的必要？另外可以分析時間複雜度嗎？
👾 : 面試官說的沒錯, 確實不需要使用cur_node1, cur_node2就可以完成此算法, 改寫如下

struct node *merge(struct node *list1, struct node *list2)
{
    struct node *mergeHead;
    if (!list1)
        return list2;
    if (!list2)
        return list1;
    
    if (list1->val > list2->val) {
        mergeHead = list2;
        mergeHead->next = merge(list1, list2->next);
    } else {
        mergeHead = list1;
        mergeHead->next = merge(list1->next, list2);
    }
    
    return mergeHead;
}

👾 : 計算時間複雜度首先可以先列出遞迴式, 假設這個mergefunction的input size是

$n$, 時間複雜度可以表示

$T(n)$, 進行recursive call的時間複雜度會是

$T(n-1)$, 其他部分的操作都是

$O(1)$, 所以遞迴式可以表示成

$T(n)=T(n-1)+O(1)$, 解這個遞迴式可以得到

$T(n)=O(n)$
👹 : 可以優化此算法嗎？
👾 : 可以, 原本我沒有使用到編譯器的tail recursion特性導致遞迴呼叫之後會讓function stack不斷疊加, 我可以嘗試把程式改寫成non-recursive

struct node *merge(struct node *list1, struct node *list2)
{
    struct node *mergeHead;
    if (!list1)
        return list2;
    if (!list2)
        return list1;
    
    struct node *cur_node;
    if (list1->val > list2->val) {
        mergeHead = list2;
        list2 = list2->next;
    } else {
        mergeHead = list1;
        list1 = list1->next;
    }
    
    cur_node = mergeHead;
    
    while (list1 && list2) {
        if (list1->val > list2->val) {
            cur_node->next = list2;
            list2 = list2->next;
        } else {
            cur_node->next = list1;
            list1 = list1->next;
        }
        cur_node = cur_node->next;
    }
    
    if (list1)
        cur_node->next = list1;
    if (list2)
        cur_node->next = list2;
    
    return mergeHead;
}

👾 : (使用測資測試…)
👹 : 屎地芬森先生謝謝你的作答, 答的不錯謝謝你

24. Swap Nodes in Pairs

測驗說明與問答

👹 : 屎地芬森先生您好, 歡迎來到我們公司的面試, 我們給你一個問題, 給你一個linked list, 當中的值是隨機的, 希望你把節點兩兩交換, 並且不能直接修改node當中的值, 請你闡述你的解法之後再開始實作
👾 : 謝謝面試官，這個題目會提供給我一個linked list，之後把節點兩兩交換並且不能直接改變節點中的值
👾 : 首先我會先定義linked list的節點結構

struct node {
    int val;
    struct node *next;
}

👾 : 再來思考兩個特別情況, 如果給我的linked list為空, 或者只有一個節點，那也沒有節點可以互換, 直接回傳即可
👾 : 再來處理一般情況, 使用cnode和nnode, nnode是cnode的下一個節點, 每次互換的時候把cnode->next指向原本的nnode->next, 然後把nnode->next指向cnode

struct node *SwapPairs(sturct node *head)
{
    if (!head || !head->next)
        return head;
    struct node *cnode, *nnode;
    cnode = head;
    while (cnode && cnode->next) {
        nnode = cnode->next;
        cnode->next = nnode->next;
        nnode->next = cnode;
        cnode = cnode->next;
    }
    return head->next;
}

👹 : 可以使用一些測資確認正確性嗎？
👾 : (測試…) 不好意思面試官, 有發現錯誤的部分, 請給我一點時間思考並修正
👹 : 沒問題
👾 : 謝謝面試官給我時間思考並修正, 我想可以利用一個指標來記錄前一組pairs的cnode, 因為錯誤的原因是cnode->next原本應該指向下一組的nnode, 但在我原本的做法中卻只會指向下一組的cnode, 所以我利用pnode來記錄上一組的cnode並把pnode->next指向當前的nnode

struct node *SwapPairs(sturct node *head)
{
    if (!head || !head->next)
        return head;
    struct node *cnode, *nnode, *pnode;
    pnode = NULL;
    cnode = head;
    while (cnode && cnode->next) {
        nnode = cnode->next;
        if (pnode)
            pnode->next = nnode;
        pnode = cnode;
        cnode->next = nnode->next;
        nnode->next = cnode;
        cnode = cnode->next;
    }
    return head->next;
}

👹 : 可以請你計算時間複雜度嗎？
👾 : 因為while loop在linked list上面走訪的時候不會往回走, 每個節點都只會走訪一次, 如果給定的linked list長度是

$n$, 則時間複雜度就會是

$O(n)$
👹 : 屎地芬森先生謝謝你的作答

83. Remove Duplicates from Sorted List

測驗說明與問答

👹 : Hello Mr.Stevenson, welcome to our company's interview. We have a question for you, you can describe your solution first and solve it. We're going to give you a sorted linked list with some duplicate values in it, please remove the duplicate nodes and make sure every value exists only once
👾 : Hello interviewer, I'm happy to be interviewed by your company and you. You're going to give me a head of a sorted linked list, and I'll have to remove all the duplicates, I want to make sure that I can assume the sorted order is ascending order right? and I still need remain the duplicate value in one node, not remove all of it right?
👹 : Yes your assumption is right, you can continue your answer
👾 : First I have to define a structure of the linked list node

struct node {
    int val;
    struct node *next;
}

👾 : I have to deal with speical case first, if you give me an empty linked list or a linked list with a single node. In both cases I'll just return the head back to you
👾 : For common cases, I'll use two pointer to struct node, cnode, nnode, and I'll compare the value of them like the following. Since we'll never remove the head node, the original head is still going to be the final head so we can just return head

struct node *RemoveDup(struct node *head)
{
    if (!head || !head->next)
        return head;
    struct node *cnode, *nnode;
    cnode = head;
    nnode = head->next;
    while (nnode) {
        if (cnode->val == nnode->val) {
            cnode->next = nnode->next;
        } else {
            cnode = nnode;
        }
        nnode = nnode->next;
    }
    return head;
}

👹 : Can you calculate the time complexity of your algorithm? and I wonder that if you can use only one pointer to solve this problem?
👾 : I'll change my code using just one pointer first, becauze nnode is always cnode->next, so we can replace nnode

struct node *RemoveDup(struct node *head)
{
    if (!head || !head->next)
        return head;
    struct node *cnode;
    cnode = head;
    while (cnode->next) {
        if (cnode->val == cnode->next->val) {
            cnode->next = cnode->next->next;
        } else {
            cnode = cnode->next;
        }
    }
    return head;
}

👾 : For the time complexity, assume the given linked list size is

$n$, for each iteration in the while loop, the time complexity is

$O(1)$, and we'll traverse each node exactly once, so the total time complexity is

$O(n)$
👹 : Thank you Mr. Stevenson. I've noticed that you remove the duplicate node by changing cnode->next, but the duplicate nodes are still alive in the system, can you try to delete it?
👾 : I know I didn't actually free the memory space of the duplicates node, I'll call these nodes as garbage node, and delete it like the following

struct node *RemoveDup(struct node *head)
{
    if (!head || !head->next)
        return head;
    struct node *cnode;
    cnode = head;
    while (cnode->next) {
        if (cnode->val == cnode->next->val) {
            struct node *tmp = cnode->next;
            cnode->next = cnode->next->next;
            free(tmp);
        } else {
            cnode = cnode->next;
        }
    }
    return head;
}

👹 : Thank you very much Mr. Steveson.

---

第二次作業 - 他評 01

Interviewer

• 優點

• 12:25: 有針對程式碼成改進的地方提出建議，感覺很棒。
• 1:14:00: 在提出改進問題的同時，有提到在真實的機器會這樣做，與現實連結很好，如果能有更情境式的回應應該會更有感覺（例如我們公司的服務通常會這樣做）。

• 可改善的部份

• 第二題的部份，Interviewee 在驗證時發現問題後，Interviewer 有說自己其實有發現錯誤，很高興看到 Interviewee 自己發現錯誤。感覺如果 Interviewer 發現時能多問問題引導 Interviewee，會比讓 Interviewee 自己驗證找問題還好。
• 1:13:33 小心不要叫錯對方的名字XD

Interviewee

• 優點

• 每一題驗證作法是否正確時，都有考慮到特例。
• 每一題撰寫程式時的說明很清楚。
• 第二題的驗證有自己發現錯誤，這樣的驗證很有意義。
• 打code時的講解，蠻流暢的。

• 可改善的部份

• 7:39: 如果指的是 Traversal，那應該要說「遍歷」而非「歷遍」。
• 10:49: 之後改寫程式碼的部份，有把本來已經寫好的部份改掉（cur_node2 = cur_node_2->next、cur_node1 = cur_node1->next），這部份感覺有點可惜，畢竟面試應該避免撰寫不必要的東西。雖然您講解的很詳細、順暢，但給我的感覺很像在聽課，如果能在撰寫程式前先簡單口頭說明一下作法，撰寫程式時再一邊寫一邊說自己目前正在寫什麼（也就是遵循 REACTO 的 Approach、Coding），我想就能避免寫了又刪除的情況。
• 16:04: 感覺本來差一點要講錯（我們都知道 O(1) 幾個加起來都一樣），不過後面有轉回來。如果您本來就確定是想說時間複雜度是
  $O(n)$，我認為可以省略這句話（我們都知道 O(1) 幾個加起來都一樣），列完遞迴式後說結論即可。
• cnode和nnode的命名或許可以更一目瞭然 32:29: 也可以嘗試在旁邊寫註解，尤其是cnode聽不太清楚。

他評02

Interviewer

• 優點

• 12:19: 對於程式碼的提問有明確指出問題。

• 可改進的地方

• 在定義 list 中的 node 的結構，是否是交給面試者去定義呢?這樣為了作答方便，面試者採取 doubly-linked list 也行，我認為應該由面試官來定義清楚吧。

Interviewee

• 優點

• 寫程式邊舉例子說出想法以及例子後再撰寫，不會有讓人模不著頭緒，為何這邊要這樣寫的感覺，很貼心!
• 有主動說出錯誤的地方，很棒!

• 可改進的地方

• 問完問題後應該可以大致講一下你的程式會如何去實作，程式當中一些細節可以再由撰寫程式中說出，像是 while 迴圈終止條件之類的。

第二次作業 - 他評 03

Interviewer

• 優點

• 開場白很完整自然

• 可改善的部份

• (第一題) 和 interviewee 互動較少
• 16:44 algorithm 的正體中文翻譯為「演算法」而非「算法」
• 說話時游標可以不要一直上下來回移動，如 16:52
• 52:27 duplicates 當形容詞和名詞時的發音為 [ˋdjupləkɪts] 而非 [ˋdʌpləkɪts]

Interviewee

• 優點

• (第一題) Repeat 的部分很清楚完整
• 口齒清晰

• 可改善的部份

• 說話時游標可以不要一直上下來回移動，如 2:13、12:45、14:35、17:01 等
• (第一題) 在假設題目為升序排列或 singly linked list 時，可以改為向面試官提問，而非自己直接假設，以免自己假設的情況和面試官想要的不符
• (第一、二、三題) C 和 C++ 中的 struct declaration 需要有分號結尾
• Approach 和 Code 的部分應該拆開來，先完整描述想到的解法，與面試官討論完後再進行實作，以免或是實作的方向不合面試官預期 (如面試官希望看到疊代的寫法，但面試者卻使用遞迴的寫法)
• 20:30 程式碼超出頁面時可以不需要用一堆 enter 把程式碼擠到下一頁，可以在程式碼上方插入新頁面，或是把「查看>顯示列印版面配置」的選項取消勾選 (如下圖)，即可讓跨頁面的文字內容連續呈現
  
  

他評04

Interviewer

• 優點

• 模擬面試先預設了題目已經預先傳送給Interviewee，解決了Interviewee畫面已經先有完整題目的不合理處。
• Interviewer 每次給的指示都很明確，不會讓Interviewee在實作時摸不清頭緒。

• 可改進的地方

• 一開始自稱面試官，以及說這是你的"工作"，聽起來蠻有壓迫感的，不太有利於後續的對等討論。

Interviewee

• 優點

• 在驗證作法可行性時連帶特殊的情況都有一併考慮，且撰寫程式的過程也會附帶說明。
• 撰寫程式碼與講解時，整體過程很流程。

• 可改進的地方

• 說明完解題思路後，可以跟Interviewer進行相應的討論，或是反向提問，來讓Interviewer 更加理解你的想法，也避免發生程式需求上的落差。