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

貢獻者: 卑鄙葛摟-Babygirl
🧔：interviewer 👶：interviewee

21. Merge Two Sorted Lists

模擬面試影片(英)

測驗說明與回答

🧔 : Hi,I am your interviewer. Here is the first question. You are given the heads of two sorted linked lists list1 and list2. Could you merge the two lists in a non-decreasing sorted list?
The list should be made by splicing together the nodes of the first two lists. And return the head of the merged linked list.
👶 : Okay, I have to deal with merging two sorted linked lists into a non-deccreasing sorted linked list. For example, list1=[1,2,4],list2=[1,3,4], Output=[1,1,2,3,4,4].
👶 : I think I will use iterative approach to solve this problem. Use the while loop and iterate through the array comparing the two current node's value. To decide which current node to add to the merge list. So the time complexity is

$O(|list1|+|list2|)$.
🧔 : Remember to consider empty linked lists. You can start to implement.
👶 : First, I check whether list1 and list2 are empty. If one of them is empty, I directly return the other list.
Then maintain a head pointer and a current pointer on the merged linked list.
And by comparing the first nodes of the two linked lists, the smaller node is used as the head of the merged linked list.
I use the while loop to comparing the node of two linked lists sequentially.
For all subsequent nodes in this two lists, I compare the current nodes of the two linked lists,
So I choose the smaller current node and link it to the tail of the merged list, and moving the current pointer of that list to the next node.
After adding a node to the merged linked list, the pointer of the merged list also points to the next node.
I continue this operation when there are some remaining elements in both lists.
Finally, if there are still some elements in only one list, this remaining list is linked to the tail of the merged list.

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

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if(list1 == NULL) return list2;
    if(list2 == NULL) return list1;
    
    struct ListNode *head = list1;
    if(list1->val > list2->val) head = list2;
    struct ListNode *curr = malloc(sizeof(*curr));

    while( list1 && list2)
    {
        if( list1->val <= list2->val)
        {
            curr->next = list1;
            list1 = list1->next;
        }
        else if( list1->val > list2->val)
        {
            curr->next = list2;
            list2 = list2->next;
        }
        curr = curr->next;
    }
    if(list1) curr->next = list1;
    if(list2) curr->next = list2;

    return head;
}

🧔 : Could you deal with recursive approach?
👶 : Yes, I can use the same concept to find the node with the smaller value in these two lists and splice them into a merged linked list.

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if(list1 == NULL) return list2;
    if(list2 == NULL) return list1;
    
    if( list1->val <= list2->val)
    {
       list1->next = mergeTwoLists(list1->next, list2);
       return list1;
    }
    else 
    {
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
  
}

🧔 : What is different between recursion and iteration?
👶 : About space, iteration can avoid the waste of space resources. If there are a lot of nodes, recursion may cause stack overflow.
👶 : About efficiency, recursion and iteration are similar.

206. Reverse Linked List

模擬面試影片(漢)

測驗說明與回答

🧔 : 我會提供你一個指向一個 linked list 的指標叫做 head，反轉該列表並回傳。
👶 : 好的，我可以使用迭代的方法，在這裡我用到兩個指標來進行反轉，一個指標指向當前節點，另一個指標指向當前節點的前一個節點，當我遍歷該 linked list，依次反轉每一個指標，最後實現整個 linked list 的反轉。

curr 
 1 -> 2 -> 3 -> NULL

prev    curr
NULL <- 1 -> 2 -> 3 -> NULL
       prev  curr
NULL <- 1 <- 2 -> 3 -> NULL
            prev  curr
NULL <- 1 <- 2 <- 3 -> NULL
                 prev
NULL <- 1 <- 2 <- 3 

🧔 : 好，你可以開始實作了。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head){

    struct ListNode* prev = NULL;
    struct ListNode* curr = head;

    while(curr != NULL){
        struct ListNode* forward = curr->next;
        curr->next = prev;
        prev = curr;
        curr = forward;
    }

    return prev;
}

👶 : 時間複雜度為 O(n)，空間複雜度為 O(1)。
🧔 : 這邊你有辦法改成用遞迴來實作嗎？
👶 : 可以的，遞迴的方法會不停呼叫函式直到最後一個節點，再將它的 next 指向前一個節點，依序返回直到遞迴結束。

curr
 1 -> 2 -> 3 -> NULL
        curr
1 -> 2 -> 3 -> NULL
    curr
1 -> 2 <-  3 
curr
1 -> 2 <-  3 
       curr
NULL <- 1 <- 2 <-  3 

🧔 : 好，你可以開始實作了。

struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL || head->next == NULL) return head;
    struct ListNode *prev = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return prev;
}

👶 : 在這裡因為使用到 stack 空間的關係，空間複雜度會是 O(n)。

287. Find the Duplicate Number

模擬面試影片(漢)

測驗說明與回答

🧔 : 我會提供妳一個包含 n + 1 個整數的整數陣列 nums，其中每個整數都在 [1, n] 範圍內（含）。而 nums 中只有一個重複的數字，請妳找出這個重複的數字。過程中不能修改 nums。
👶 : 好的，我的想法是額外使用一個陣列 array 來解決找出重複數字的問題。通過遍歷 nums，使用額外的 array 來記錄每個元素是否已經被訪問過。
🧔 : 這個方法的空間複雜度會是如何？
👶 : 會是 O(n) 。
🧔 : 請妳換個方法來保證只使用到常數額外空間。
👶 : 因為至少有一個數字重複，所以當遍歷 nums 時一定會進入一個循環。這個問題可以用 cycle detection 的方法來解決，也就是使用兩個指標 slow 和 fast 來追蹤數字，會分成兩步驟，第一個步驟檢查循環的存在，第二個步驟找到循環的起始點，也就是找到重複的數字。
👶 : 在第一步驟我們想要檢查循環的存在，當指標 slow 和 fast 從起點開始，slow 每次走一格，fast 每次走兩格，一直走下去如果它們能相遇，代表存在一個環。反之，若不存在環的話，兩個指標永遠不會相遇。而它們相遇的地點可能是在循環的任何位置，不一定是循環的起始點。
👶 : 在第二步驟我們想要找到循環的起始點，因為環周長減掉循環的起始點至相遇點的距離會等於從起點至環的起始點的距離，也就是說 slow 回到起點並每次走一格， fast 繼續每次走一格，它們再次相遇的點會是循環的起始點，就可以找到重複的數字。

環周長 - 循環的起始點至相遇點的距離 = 起點至環的起始點的距離

🧔 : 好，你可以開始實作了。

int findDuplicate(int* nums, int numsSize){
    int slow = nums[0];
    int fast = nums[0];

    do{
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    slow = nums[0];

    while(slow != fast)
    {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

---

第二次作業-他評01

關於interviewer

• 可改進之處

• 7:37: 我覺得直接講說可不可以用recursion表示有點太提示了，或許可以換個講法，像是有沒有辦法用比較少的程式碼來達到目的呢？

interviewee

• 優點

• Example跟Approach明瞭 👏

• 可改進之處

• 2:18: Merge Two Sorted List，這邊 interviewee 因為一些錯字修改了一下，有點尷尬，我覺得可以不用去修改，因為看得出你想宣告什麼型態。

• 其他建議

• 12:47: Find the Duplicate Number 在coding之前有講到有關環周長的公式，會希望在講解完之後簡單舉個例子帶入你的想法。

第二次作業-他評02

interviewer

• 可改進之處

• 10:33 可以讓interviewee完成這個方法之後，再進行詢問

interviewee

• 優點

• 0:47: 主動分析時間複雜度

• 可改進之處

• 9:03: 避免頻繁畫面捲動

第二次作業-他評03

interviewer

• 優點

• 有提點interviewee應注意的細節
• 有提問兩種做法的相異處，可以測試到interviewee對程式的了解，而不是死背。

• 可改進之處

• 7:42, 5:21: 感覺可以先對interviewee目前寫好的code做評論或提問，再請他優化，可能會比請他直接提供另外一種做法要更好
• 0:08: 建議可以把題目包裝成另一情境，避免聽到關鍵字就開始背答案導致鑑別度不足，也可以考驗interviewee的理解能力和應變能力

interviewee

• 優點

• 邊打code邊講解的很順暢
• 2:33: 將所舉的例子key出來很清楚詳細，讓人一看就明白

• 可改進之處

• 可以增加一些肢體動作或停頓(加強)來讓自己的整段對話重點更加突出。
• 較為缺乏REACTO的 Test部分(英)

第二次作業-他評04

Interviewer

• 優點

• 指示清晰

• 可改進的地方

• 要變換題型
• 互動太少，感受不到面試官有想認識面試者
• 感覺就很順的放水受試者

Interviewee

• 優點

• 咬字清晰，2倍速可聽
• 解釋有邊打字，有個圖示很棒
• 邊coding的解釋很棒，不會尷尬，還會再用簡單文字表示，避免面試官恍神很棒

• 可改進的地方

• 要遵守"確認，舉例，說明方案，撰寫程式，驗證程式"，可能要多確認下問題
• 測試可能要再多一點