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

貢獻者: 月前龍馬-lonmu
模擬面試: 漢

Repeat
Example
Approach
Code
Test
Opmization

21. Merge Two Sorted Lists

🧔 : interviewer 👶：interviewee

🧔 : 您好 今天由我來主詞這場面試，這邊有個問題想要請你解一下，因為本公司有經營電子商務等相關業務，平常儲存訂單的內容我們會以singly ordered linked list去儲存 想請問那如果想合併兩個客戶的資料 而且預期得到以訂單編號由小到大合併好的結果 可以說明一下你會怎麼做

repeat & exmaple

👶 : 我可以理解為今天資料由 singly ordered linked list 去儲存 那想要合併兩個客戶資料 那就是將 兩個 singly ordered linked list 合併為一個 singly ordered linked list

簡單帶個例子 e.g. list1: 1->5, list2: 2->4, expected result: 1->2->4->5 這樣我對題目的理解是對的嗎
🧔 : 沒錯 你對題目的理解是對的

approach

👶 : 好的，那我這邊目前想到的方法為，先新開一個之後要回傳的空節點指標ans，和一個指向尾端的tail指標，使用while的方式當兩個linked list皆不為空，則將兩者擁有較小值的Head node的list，接到要回傳的ans的尾端，並將tail和該list指向下一個node做更新，而當兩者其中一條linked list為空時，跳出迴圈，並將不為空的linked list再接到ans list後方即完成merge了

​​​​// new node ptr: ans, tail
​​​​// while twolist both are not empty
​​​​//     link the list which has the smaller head to the tail 
​​​​//     update tail and the respond list
​​​​// check two list and link the rest one

🧔 : 方法大致沒問題 那你可以開始 implement 剛剛討論的方法了

code & test

👶 : coding. . . finished 帶入example 解釋code沒問題

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
// e.g. list1 = 1->5, list2 = 2->4; expected result: 1->2->4->5;
// ans = dummy->1->2->4->5, return ans


ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* ans = new ListNode;
    ListNode* tail = ans;

    while(list1&& list2){
        if(list1->val < list2->val){ //link list1 head & update
            tail->next = list1;
            list1 = list1->next;
        }
        else{        // link list2 head & update
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;

    }
    // link the rest one
    if(list1){ tail->next = list1;}
    else{tail->next = list2;}
    return ans->next;
}

🧔 : ok 那可以分析一下 你寫的程式 他的時間複雜度如何
👶 : 由於 while 迴圈的執行次數是取決於兩個 list 中較短者，假設 list 長度分別為 n 與 m ，時間複雜度為 O(n+m)。
🧔 : ok

follow up => 23. Merge k Sorted Lists

🧔 : 那今天系統有需求 需要合併的不是僅有兩個客戶的資料 而是同時有多個人的話你會怎麼做 鑒於時間關係 你可以大概說明你的想法就可以了
👶 : 可以使用 merge sort divide&conquer的概念 使用recursion陸續兩兩分堆做到divide的步驟 後再開始conquer 運用剛剛寫的程式碼 兩條兩條list去做merge 最後合併成一條 linked list

e.g. vector list: a,b,c,d,e
=> 1st level merge: ab, cd ,e
=> 2nd level merge: abcd,e
=> 3rd level merge: abcde
🧔 : 好 那今天就先到這邊 稍待與主管和人資討論 再連絡你 謝謝

初步檢討

• 影片中的方法概要的註解下的不夠精確，有可能導致interviewer誤解，後來將較精確的註解寫於本篇approach中
• 邊寫程式邊講解仍有一定難度，且因註解不精確，偶爾會口誤容易讓人誤解，例如
  2:20-講成較小條list 應該是有較小值head的list
  6:10-講成較短的list接到tail。
• 題目本身interviewer包裝的不夠，還是蠻接近leetcode原題的
• 缺少optmization, follow-up部分僅簡單說明實作方法
• 語助詞過多，沒有注意一直講"然後"

---

第二次作業-他評模板

關於 interviewer

• 優點

• 可改進的地方

關於 interviewee

• 優點

• 寫code前的pseudocode不錯。

• 可改進的地方

• 預期得到這樣…，或許直接照著講會比較好。

他評-01

關於 interviewer

• 可改進的地方
• 11:29 如果預期一個問題有20分鐘可以作答的話，剩下8分多鐘可以讓iterviewee在說完優化想法後試著開始寫程式，不用告訴interviewee因為時間不夠所以只講想法即可，說不定interviewee可以在剩下的時間內很快將想法實現。

關於 interviewee

• 優點
• 5:24 在寫code時，會在旁邊加上註解方便之後快速閱讀。

第四次作業-他評01

關於 interviewer

• 優點
• 問題陳述清楚。
• 可改進的地方
• 12:24這邊可以繼續討論此方法的時間複雜度等等。

關於 interviewee

• 優點

• 9:28test時候逐步分解 ，解釋詳細。

• 可改進的地方

• 7:07或許旁邊補上註解可以方便於interviewer 閱讀。

第四次作業-他評02

關於 interviewer

• 優點
  • 問題包裝良好。

關於 interviewee

• 優點
  • 03:41為止，REACTO的REA做得很完整，有適當舉例幫助了解，也有向主持人確認做法才開始實作。
• 可改進的地方
  • 07:03雖然你用反白標示出你在講什麼部分很好，但又配上滑鼠游標畫圈的動作，就扣分回來了，老師在上課有提到，應避免如此畫圈行為。
  • 整個coding下來，雖然在文件最上面已經用註解表示全體流程，但建議在coding時還是要把這個區塊在做什麼，把註解寫在該區塊，會清楚點。

第四次作業-他評03

• 問題有給予情境結合生活應用
• 1:54
  把要做的方法講解的很清楚
  對於要設立的變數也有清楚說出來
• 7:04
  滑鼠指標有反白要說的程式碼即可
• 7:49
  程式完成後說明即可，不要上下捲動
• 8:51
  測資用例說明的很清楚
• 11:19
  問題延伸得當，可以適時補充對於這個想法上的時間複雜度特別是針對 merge sort，可以讓interviewer 知道你對sort 的掌握度，Merge sort沒有最差與最佳的情況，時間複雜度都是n log(n)，但因為使用了Recursion的方式，所以Merge sort在空間複雜度相對於其他演算法較高