# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 2
> 貢獻者: 月前龍馬-lonmu
> [模擬面試: 漢](https://youtu.be/Ire86ptjVtI)

**R**epeat
**E**xample
**A**pproach
**C**ode
**T**est
**O**pmization

## [21. Merge Two Sorted Lists](https://leetcode.com/problems/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](https://leetcode.com/problems/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](https://hackmd.io/dFTkZYO6RmKo-iFLTpZdlw?both#repeat-amp-exmaple)中
* 邊寫程式邊講解仍有一定難度，且因註解不精確，偶爾會口誤容易讓人誤解，例如
[2:20](https://youtu.be/Ire86ptjVtI?t=140)-講成較小條list 應該是有較小值head的list
[6:10](https://youtu.be/Ire86ptjVtI?t=360)-講成較短的list接到tail。
* 題目本身interviewer包裝的不夠，還是蠻接近leetcode原題的
* 缺少optmization, follow-up部分僅簡單說明實作方法
* 語助詞過多，沒有注意一直講"然後"

---

## 第二次作業-他評模板
### 關於 interviewer
- [ ] 優點

- [ ] 可改進的地方

### 關於 interviewee
- [ ] 優點
- 寫code前的pseudocode不錯。

- [ ] 可改進的地方
- [預期得到這樣...](https://youtu.be/Ire86ptjVtI)，或許直接照著講會比較好。

## 他評-01
### 關於 interviewer
- [ ] 可改進的地方
- [11:29](https://www.youtube.com/watch?v=Ire86ptjVtI&t=11m29s) 如果預期一個問題有20分鐘可以作答的話，剩下8分多鐘可以讓iterviewee在說完優化想法後試著開始寫程式，不用告訴interviewee因為時間不夠所以只講想法即可，說不定interviewee可以在剩下的時間內很快將想法實現。

### 關於 interviewee
- [ ] 優點
- [5:24](https://www.youtube.com/watch?v=Ire86ptjVtI&t=5m24s) 在寫code時，會在旁邊加上註解方便之後快速閱讀。

## 第四次作業-他評01
### 關於 interviewer
- [ ] 優點
- 問題陳述清楚。
- [ ] 可改進的地方
- [12:24](https://youtu.be/Ire86ptjVtI?t=744)這邊可以繼續討論此方法的時間複雜度等等。

### 關於 interviewee
- [ ] 優點
- [9:28](https://youtu.be/Ire86ptjVtI?t=568)test時候逐步分解 ，解釋詳細。

- [ ] 可改進的地方
- [7:07](https://youtu.be/Ire86ptjVtI?t=427)或許旁邊補上註解可以方便於interviewer 閱讀。

## 第四次作業-他評02
### 關於 interviewer
- [ ] 優點
- 問題包裝良好。

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

## 第四次作業-他評03

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