2023 Homework2
===

>貢獻者 喬喬 JOJO

>Video
>[模擬面試影片 (漢)](https://youtu.be/vqFhdXyVXwo)

👨‍💻：面試官
🧑‍：面試者
## [21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/description/)

👨‍💻：第一題是一個關於排程的問題，有兩位學生，他們分別列出他們能跟教授開會的時間並傳給教授，這時教授需要將學生們提出的時間整合，好讓教授能知道有哪些時間是需要騰出來的。
🧑‍：我重複一下問題，我需要將兩位學生的排程整合，好讓教授能知道哪些時間不可以安排事情?
👨‍💻：沒錯。
🧑‍：那我舉個例子，假如兩名學生的排程如下，給教授的排程表最前面的應該是 A 的 1，隨後是 B 的 2，第三個是 B 的 3，以此類推，是這樣嗎?


👨‍💻：對。
🧑‍：那如果遇到相同的時間安排，我只將一個時段放入要給教授的排程沒錯吧
👨‍💻：聽起來符合邏輯。
🧑‍：那我想到一個方法，首先我們需要定義出排程表的結構，我會定義一個 structure 作為節點，內容包含一個 int 叫 val 用於紀錄時間，在定義一個指標用於指向下一個時間點。再將數個節點串連成 list 來代表行程表，並宣告指標 `tail` 合併行程表的尾端。。

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

🧑‍：接著使用迴圈解決此問題，首先，當兩個行程表皆還有時間沒被放入合併的行程表時，可以從兩個 `list` 當前的開頭比較何者時間較小，放入合併的 `list` ，並記錄放入時間，這時我們可以將合併 `list` 的結尾與剛剛決定出的較小的時間節點相連，並移動 `tail` 使其成為合併 `list` 的新結尾，若當前最小者與記錄的值相同，將其跳過。直到兩個 `list` 其中一個不在具有節點時，將還剩餘時間的 `list` 與回傳 `list` 的 `tail` 相連，最後回傳。
👨‍💻：感覺都有考慮到，現在請你將他 coding 出來。

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode * dummy = new ListNode();
    ListNode * tail = dummy ;
    int record = -1;
    while( list1 != NULL && list2 != NULL ) {
        if ( list1->val <= list2->val ) { 
            if (record != list1->val) {
                tail->next = list1 ;
                tail = list1 ;
                record = list1->val;
            }
            list1 = list1->next ;
        } // if
        else {
            if (record != list2->val) {
                tail->next = list2 ;
                tail = list2 ;
                record = list2->val;
            }
            list2 = list2->next ;
        } // else
    } // while
        
    if( list1 != NULL ) {
        if ( record == list1->val)
            list1 = list1->next;
        tail->next = list1 ;
    }
    else if ( list2 != NULL ) {
        if ( record == list2->val)
            list2 = list2->next;
        tail->next = list2 ;
    } // else if
        
    return dummy->next ;
}

👨‍💻：很好，現在我有一個想法，如果老師本來就有一個排程表，當同學選定的時間點與老師預定課程相同時，就不將其加入要傳給老師的排程表了。
🧑‍：我會將老師的排程用 hash table 存放，並在原先判斷是否為已加入排成的判別式中增加一個判斷，當當前時間不與老師的時間重複時，才可加入到合併的排程中。
👨‍💻：請你將改動新增到原先的程式碼中。

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2, ListNode* list3) {
    unordered_set<int> table;
    ListNode * walk = list3;
    while ( walk != NULL) {
        table.insert(list3->val);
        walk = walk->next;
    }
    ListNode * dummy = new ListNode();
    ListNode * tail = dummy ;
    int record = -1;
    while( list1 != NULL || list2 != NULL ) {
        if ( list1->val <= list2->val ) { 
            if (record != list1->val && table.find(list1->val) == table.end()) {
                tail->next = list1 ;
                tail = list1 ;
                record = list1->val;
            }
            list1 = list1->next ;
        } // if
        else {
            if (record != list2->val && table.find(list2->val) == table.end()) {
                tail->next = list2 ;
                tail = list2 ;
                record = list2->val;
            }
            list2 = list2->next ;
        } // else
    } // while
        
    while (list1 != NULL) {
        if ( record != list1->val && table.find(list1->val) == table.end()) {
            tail->next = list1 ;
            tail = list1 ;
        }
        list1 = list1->next ;
    }
    while (list2 != NULL) {
        if ( record != list2->val && table.find(list2->val) == table.end()) {
            tail->next = list2 ;
            tail = list2 ;
        }
        list2 = list2->next ;
    }
        
    return dummy->next ;
}

👨‍💻：看起來可行，你能舉的例子來驗證程式碼的正確性嗎?
🧑‍：好的。
👨‍💻：那這題的時間複雜度在增加限制條件之後有改變嗎?
🧑‍：我們可以發現在原先的問題上，我們會將兩個 `list` 都走訪一遍，假設 `list` 長度分別為 n 與 m ，時間複雜度為 $O(n+m)$。而增加限制後對程式碼的影響始有判斷式的條件變多了，所以時間複雜度不變，但可以發現新的問題讓在與剩餘時間排程相連時增加了判別式，需要以 `while` 實現對個別時間的判斷，所以運算時間將會增加。

作業一得到的收穫
===
### 對同學給予建議得到的收穫
#### Interviewer
* 可以適當加入背景音樂，讓整體聽感改變。
* 可以將原題經過修飾改成情境題。
* 可以利用**圖**來講解題目，使面試過程更為順暢。
* 在說明題目時可以將文字放大並使用色系差異較大的顏色組合使 interviewee 可以更清楚的看到題目。
* 讀音相近的詞可以用其他語言來代稱，避免聽者被混淆。
* 可以先讓 interviewee 實作提出方法的程式碼再詢問改進方案，讓 interviewee 能先透過 coding 找出當前方法的不足之處，可以更全面的對方法做改進。
* 在 interviewee 完成題目作答後有**引導**答題者精簡程式碼。

#### Interviewee
* 注意不要跳過 Repeat 與 Test 這兩個步驟。
* 在與 interviewer 討論時，舉例(Example)應該搭配**畫面**才能使人更好理解，雖然簡單的問題可能並不複雜所以可以讓人很快進入狀況，但要是遇到更複雜的問題可能會導致溝通的效率降低。
* 用圖說明演算法如何執行時，在細節上解釋的不能馬虎，會使讀者不能快速理解講者的作法。
* 在解釋完自己的做法與例子後，可以先與 interviewer 交流，確認此作法合乎雙方的共識再開始 coding。

### 從同學給予建議得到的收穫
#### Interviewer
* 可以多和 interviewee 溝通，不要像問答機器人。
* 講解題目時，可以保留一部份資訊，用於後續溝通。
* 可以再多加討論空間複雜度。
#### Interviewee
* 講解時要減少口闢。
* 雜音過於明顯。