# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS11ooE4Rh)」作業 1
> 貢獻者: 林克-Link
> [video (英)](https://www.youtube.com/watch?v=sEyuWghSS2M)
> [video (漢)](https://www.youtube.com/watch?v=PoYD9bZQCsM)
> [video (漢)](https://www.youtube.com/watch?v=nd9EUHtTjdM)

🧔：interviewer 👶：interviewee
## [Easy 21. Merge Two Sorted List](https://leetcode.com/problems/merge-two-sorted-lists/)
### 測驗說明與問答
🧔: You're given two sorted linked lists, and you need to merge them into one list with the sorted order.
👶: Ok, Let me confirm the question. I need to make two sorted list into one list with ascending or decending order. Depend on the order of the given list. Is that correct?
🧔: Yes, and you can assume they are in ascending order.
👶: OK. So, if I have two lists with 1,2,3 and 2,3,4 respectively the answer should be 1,2,2,3,3,4
🧔: Exactly, you can start you code.
👶: In my intuition, I will approch it with iterate through every node in two list by comparing each other everytime.

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode *tmp = NULL, *ans = NULL;

    while (list1 && list2){
        if (list1->val > list2->val){
            if (tmp == NULL){
                ans = tmp = list2;
            }else{
                tmp->next = list2;
                tmp = tmp->next;
            }
            list2 = list2->next;
        }else{
            if (tmp == NULL){
                ans = tmp = list1;
            }else{
                tmp->next = list1;
                tmp = tmp->next;
            }
            list1 = list1->next;
        }
    }

    if (tmp){
        if (list2) tmp->next = list2;
        if (list1) tmp->next = list1;
    }else{
        ans = list1 ? list1 : list2;
    }

    return ans;
}

👶: So, Since we iterate though each node in worst case, the time complexity should be $O(m+n)$.
🧔: It looking great. But the control statement may cause control hazard. Can you reduce the if statement?
👶: I will start from reducing the special case. So the specail case is when ...

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;

    struct ListNode *ans = NULL, **tmp = &ans ;

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

    if (list2) *tmp = list2;
    else *tmp = list1;
    return ans;
}

🧔: OK, I think it great enough. Since we don't have too much time left. Let's end up here. Thank you for your time.
### 初步檢討
**Interviewer**
* [0:06](https://youtu.be/TBOPe1dJUhA?si=3tpTKjLlKHA7vbvj&t=6): "The question today will be in it" 可以改成 "The question we will discuss later will be in it" 避免讓面試聽起來像是在考試。
* 沒有發現 interviewee 在 [14:16](https://youtu.be/TBOPe1dJUhA?si=mpMpQjTfTbFLPW4k&t=856) 程式碼 trace 時發生錯誤。

**Interviewee**
* 最終程式碼還可以再更精簡
* [1:18](https://youtu.be/TBOPe1dJUhA?si=4TBYydeiTIOsPJXK&t=78): compare each other's value through the iteration 的 through 聽起來像 to。
* [2:41](https://youtu.be/TBOPe1dJUhA?si=Q-64rgxN8znpj48g&t=161): NULL 發音錯誤
* 有時候會講完整行要寫的程式碼才開始打字，應該要邊打邊寫，或者要講快一點。(e.g. [5:57](https://youtu.be/TBOPe1dJUhA?si=JLV8iE8p12DHZBSc&t=357))
* [14:16](https://youtu.be/TBOPe1dJUhA?si=mpMpQjTfTbFLPW4k&t=856) 程式碼 trace 錯誤。應該是要跳入 else statement。
## [Easy 83. Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list/description/)
> 銜接問題：[Medium 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/)

### 測驗說明與問答
🧔: 你會得到一個排序好的鏈結串列，你需要把相同數值的節點移除。
👶: 我確認一下問題，我有一個排序好的 Linked list，如果遇到重複的資料就刪掉，只留一個在 Linked list 裡面。
🧔: 對。
👶: 也就是說，如果我有的 Linked list 長 [1,1,3,4,4] 經過我的 function 後會變成 [1,3,4]，請問是這樣嗎？
🧔: 沒錯。
👶: 我的直覺是直接走訪每一個節點，然後拿當前走訪到的節點向後比較，如果相同就直接移除。

struct ListNode* deleteDuplicates(struct ListNode* head){
  if( head == NULL) return NULL;

  for(struct ListNode *cur = head; cur != NULL; cur = cur->next){
    while(cur->next && cur->next->val == cur->val){
      cur->next = cur->next->next;
    }
  }

  return head;
}

👶: 因為每個節點都需要訪問過，因此複雜度為 $O(n)$
🧔: 看起來沒問題，那如果我連重複的節點本身也要刪除呢？([Medium Leetcode 82.](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/))
👶: 這樣就要刪除 cur 指向的節點，因此我們需要一個 flag 判斷是否有進入 while 迴圈，同時要將 cur 改為指標的指標。

struct ListNode* deleteDuplicates(struct ListNode* head){
  if( head == NULL) return NULL;

  for(struct ListNode **cur = &head; *cur != NULL;){
    int flag = 0;
    while((*cur)->next && (*cur)->next->val == (*cur)->val){
      flag = 1;
      (*cur)->next = (*cur)->next->next;
    }

    if (flag){
      *cur = (*cur)->next;
    }else{
      cur = &(*cur)->next;
    }
  }

  return head;
}

### 初步檢討
**Interviewer**
* [0:00](https://youtu.be/D7rqwUFOw8M?si=Y2jB4kLP_h6wU78S): 開頭應該避免使用「面試官」這種上對下的詞，可以改成「你好，歡迎來到這次的面試」
* [16:05](https://youtu.be/D7rqwUFOw8M?si=9V85aKPlesukXAIZ&t=965): 結尾有點草率，應該要多說一些話然後在謝謝 interviewee 參加這場面試。

**Interviewee**
* 講話語調太平，我自己聽了都想睡覺了。
* [2:39](https://youtu.be/D7rqwUFOw8M?si=E4fk_bRNjuit2J9T&t=159): NULL 發音錯誤
* [7:02](https://youtu.be/D7rqwUFOw8M?si=CJ0RTZLwb6iJZEp1&t=422): 「離開 while 迴圈」的發音全部連在一起，聽不清楚。
* [14:13](https://youtu.be/D7rqwUFOw8M?si=BBN6qAGTSkycDyqa&t=853): NULL 發音錯誤

## [Medium 146. LRU Cahce](https://leetcode.com/problems/lru-cache/)

### 測驗說明與問答

🧔: 今天會要求你實作一個 LRU cache，總共有 3 個 function 需要你實作。lRUCacheCreate、lRUCacheGet、lRUCachePut。lRUCacheCreate 的功能是初始化 cache 大小，由於我們的 cache 皆是 key、value 成對的，因此 lRUCacheGet 會給定一個數值 key，你需要回傳相對應的 value，最後 lRUCachePut 會給定 key、value，如果資料存在 cache 中就更新 value，如果不在 cache 則加入 cache。
👶: 假如說 cache 的大小是 2，當我先做兩次 put 操作 put(1,1), put(2,2)，這時候如果再次進行 put 操作 put(3,3)，這時候被移出的資料為 1,1，因為他是最久沒被使用到的資料。
🧔: 對，你可以假設 cache 的 capacity 至少為 1。
👶: 我直覺的作法是使用一個鏈結串列，如果有對資料操作就將資料放到鏈結串列的開頭，這樣當 cache 放滿資料時，串列的最尾端的節點就會是需要被移除的節點。

struct Node{
    int key, val;
    struct Node *next;
};

typedef struct {
    int cap, size;
    struct Node *head;
} LRUCache;


LRUCache* lRUCacheCreate(int capacity) {
    LRUCache *cache = malloc(sizeof(LRUCache));
    cache->cap = capacity;
    cache->size = 0;
    cache->head = NULL;
    return cache;
}

void move_to_head(LRUCache *obj, struct Node **cur){
    struct Node *tmp = *cur;
    *cur = (*cur)->next;
    tmp->next = obj->head;
    obj->head = tmp;
    return;
}

int lRUCacheGet(LRUCache* obj, int key) {
    struct Node **cur = &obj->head;
    for (; *cur; cur = &(*cur)->next){
        if ((*cur)->key == key){
            move_to_head(obj, cur);
            return obj->head->val;
        }
    }
    return -1;
}

void lRUCachePut(LRUCache* obj, int key, int value) {
    struct Node **cur = &obj->head;
    struct Node **prev = NULL;
    for (; *cur; prev = cur, cur = &(*cur)->next){
        if ((*cur)->key == key){
            (*cur)->val = value;
            move_to_head(obj, cur);
            return;
        }
    }

    if (++obj->size > obj->cap){
        free(*prev);
        *prev = NULL;
        obj->size--;
    }

    struct Node *new = malloc(sizeof(struct Node));
    new->key = key;
    new->val = value;
    new->next = obj->head;
    obj->head = new;

    return;
}

👶: 最差的情況下複雜度為 $O(n)$，因為在比對 key 的時候需要一個節點一個節點慢慢往後比較。
🧔: 由於我們要實作 cache，複雜度還是希望可以控制在 $O(1)$，請問你會如何修改你的程式。
👶: 我會使用 hash 的方式，同時使用環狀鏈結的方式，這樣查找與移除節點都可以在 $O(1)$ 完成。

struct Node{
  int key, val;
  struct Node *next, *prev;
  struct Node *hnext;
};

typedef struct {
    int cap;
    int size;
    struct Node head;
    struct Node **table;
} LRUCache;

LRUCache *lRUCacheCreate(int capacity){
	LRUCache *new = malloc(sizeof(LRUCache));
	new->cap = capacity;
	new->size = 0;
	new->head.next = new->head.prev = &new->head;
    new->head.hnext = NULL;
    new->table = calloc(capacity, sizeof(struct Node *));
	return new;
}

void move_to_head(LRUCache *cache, struct Node *cur){
	cur->next->prev = cur->prev;
    cur->prev->next = cur->next;

    cur->next = cache->head.next;
    cur->prev = &cache->head;
    cache->head.next->prev = cur;
    cache->head.next = cur;
	return;
}

int hash(int cap, int key){
    return key % cap;
}

struct Node *hashget(LRUCache *cache, int key){
    struct Node *tmp = cache->table[hash(cache->cap, key)];
    for (; tmp && tmp->key != key; tmp = tmp->hnext)
        ;

    return tmp;
}

int lRUCacheGet(LRUCache *cache, int key){
    struct Node *n = hashget(cache, key);
    if (n){
        move_to_head(cache, n);
        return n->val;
    }

    return -1;
}

void add_node(LRUCache *cache, struct Node *new){
    struct Node **tmp = &cache->table[hash(cache->cap, new->key)];
    for (; *tmp; tmp = &(*tmp)->hnext)
        ;

    *tmp = new;
    new->next = cache->head.next;
    new->prev = &cache->head;
    cache->head.next = cache->head.next->prev = new;
    cache->size += 1;
    return;
}

void del_tail(LRUCache *cache){
    struct Node *tail  = cache->head.prev;
    tail->prev->next = tail->next;
    tail->next->prev = tail->prev;

    struct Node **tmp = &cache->table[hash(cache->cap, tail->key)];
    for (; *tmp && (*tmp)->key != tail->key; tmp = &(*tmp)->hnext)
        ;
    *tmp = tail->hnext;
    cache->size -= 1;
    free(tail);
    return;
}

void lRUCachePut(LRUCache *cache, int key, int value){
    struct Node *n = hashget(cache, key);
    if (n){
        move_to_head(cache, n);
        n->val = value;
        return;
    }

    struct Node *new = malloc(sizeof(struct Node));
    new->key = key;
    new->val = value;
    new->next = new->prev = new->hnext = NULL;
    add_node(cache, new);

	if (cache->size > cache->cap){
		del_tail(cache);
    }
    return;
}

### 初步檢討
**Interviewer**
* 題目選擇錯誤，導致面試時間拖太長。
* [0:00](https://youtu.be/nuNs1ZMWhic?si=Eht1arMG9X6eqG8c): 開頭應該避免使用「面試官」這種上對下的詞，可以改成「你好，歡迎來到這次的面試」
* [0:02](https://youtu.be/nuNs1ZMWhic?si=Eht1arMG9X6eqG8c&t=2): 「這次的題目是」可以改成「這裡有一個 Cache 實作想要跟你討論」
* [27:52](https://youtu.be/nuNs1ZMWhic?si=RU2voS2JZRttyf7n&t=1672): 沒有發現程式碼錯誤。

**Interviewee**
* node 可以使用「節點」來代替；circular linked list 可以使用「環狀鏈結串列」代替，避免中英頻繁交錯。
* [5:19](https://youtu.be/nuNs1ZMWhic?si=zxgcLczIBcu0KwOt&t=319): NULL 發音錯誤
* [20:40、20:45](https://youtu.be/nuNs1ZMWhic?si=5LFr-sZf2aCZiJow&t=1240): 「取值」發音發成「取址」
* [24:13](https://youtu.be/nuNs1ZMWhic?si=WDt_hLl0lxMeyBkH&t=1453): 「把 next 跟 prev 維護成 circular linked list」說法怪怪的，不應該是「維護」。應該說「把 next 跟 prev 當作 circular linked list 的指標」。
* [27:52](https://youtu.be/nuNs1ZMWhic?si=RU2voS2JZRttyf7n&t=1672): 程式碼錯誤，在 `move_to_head` 之後應該要將 value 進行修改。在後續的檢查過程也沒有檢查到。
* [32:21](https://youtu.be/nuNs1ZMWhic?si=QBj6znsuXRAj5hLN&t=1941): 停頓太久
* [37:15](https://youtu.be/nuNs1ZMWhic?si=lpFAM4gY4KbmI7vH&t=2235): 「那個 hash table 位址的 address」意思不明確，應該要說「那個 hash 後對應到的 pointer 的 address」
* [39:12](https://youtu.be/nuNs1ZMWhic?si=BXwm1TgcQ8eK5Cd5&t=2352): 發現講錯後應該要說「我更正一下」
* [47:39](https://youtu.be/nuNs1ZMWhic?si=eWZcOaCGggv8K03X&t=2859): 應該是要說「circular linked list」但實際聽不太出來到底在講什麼。
* 後面講話停頓越來越多，停頓的方式讓人想睡覺。

---

## 第二次作業 - 他評01
### for interviewer
- [ ] 優點
- 說明清楚
- 語速適中
- [ ] 可改進的地方
- 開頭應該避免使用「面試官」這種上對下的詞，可以簡單跟interviewee打招呼，並簡述流程即可
- 避免直接使用Leetcode題目原型，可以加以包裝，例如為什麼要刪除重複的節點？

### for interviewee
- [ ] 優點
- coding很流暢
- [2:54](https://youtu.be/PoYD9bZQCsM?si=TX8zCnQIw0e2MB3c&t=174) 有適度手勢，肢體語言恰到好處
- coding後有舉例加以驗證，確實做到Test

- [ ] 可改進的地方
- 咬字有時會較含糊，如 [5:03](https://youtu.be/PoYD9bZQCsM?si=OqPjSfMUA6HPjViW&t=303) 在說明時，部分地方語調較低時較難聽懂
- 整體語調較平淡

## 第二次作業 - 他評02
### for interviewer
- [ ] 優點
- 關於[Easy 83. Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list/description/)這題，有更進一步討論medium的變形，而且用不大的更動就實作出來
- [ ] 可改進的地方
- 關於[Easy 83. Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list/description/)這題，可以多討論一點，像是如果一開始給的linked list沒有排序的話，interviewee會怎麼想，不一定要實作出code，但是可以討論一下interviewee會怎麼做，例如建hash table看有無重複，或是interviewee就是直接排序，然後重複利用這題所寫的code

### for interviewee
- [ ] 優點
- coding很順，講話蠻穩的
- [ ] 可改進的地方
- 沒啥問題

## 第二次作業-他評03

### 針對 Interviewer 的檢討:
* 可以包裝一下題目
* 可以和 Interviewee 多一些互動，Interviewee 寫完程式碼後，可以給予一些回饋

### 針對 Interviewee 的檢討:
* 打完程式碼後有落實 Test 很棒!
* 有主動提及時間複雜度
* 確認題目時有帶一遍例子確認自己的理解，在寫程式碼前也有先闡述自己的做法很棒!
* Problem 2 有做 follow up 很棒!
* [44:09](https://youtu.be/nd9EUHtTjdM?t=2649)可以帶實際測資，不然很像是再把程式碼說一遍的感覺

## 第二次作業-他評04
**interviewer**
* 最後優化完程式之後可以再針對程式碼進行測試，並且可以跟 interviewee 多一點問答，像是延伸題目、程式碼效能如何等等。

**interviewee**
- [ ] 優點
* 有利用範例去講解自己的邏輯。
- [ ] 可改進的地方
* 音量可以再大聲一點。
* Merge Two Sorted List 中在講解程式碼的時候可以適當的寫註解，輔助敘述。
* 舉例講解的時候可以把舉例放在程式碼裡面註解，這樣講解的時候就不用一直上下滑動滑鼠。