Try   HackMD

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

貢獻者: 林克-Link
video (英)
video (漢)
video (漢)

🧔：interviewer 👶：interviewee

Easy 21. Merge Two Sorted List

測驗說明與問答

🧔: 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: "The question today will be in it" 可以改成 "The question we will discuss later will be in it" 避免讓面試聽起來像是在考試。
  • 沒有發現 interviewee 在 14:16 程式碼 trace 時發生錯誤。

Interviewee

  • 最終程式碼還可以再更精簡
  • 1:18: compare each other's value through the iteration 的 through 聽起來像 to。
  • 2:41: NULL 發音錯誤
  • 有時候會講完整行要寫的程式碼才開始打字，應該要邊打邊寫，或者要講快一點。(e.g. 5:57)
  • 14:16 程式碼 trace 錯誤。應該是要跳入 else statement。

Easy 83. Remove Duplicates from Sorted List

銜接問題：Medium 82. Remove Duplicates from Sorted List II

測驗說明與問答

🧔: 你會得到一個排序好的鏈結串列，你需要把相同數值的節點移除。
👶: 我確認一下問題，我有一個排序好的 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.)
👶: 這樣就要刪除 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: 開頭應該避免使用「面試官」這種上對下的詞，可以改成「你好，歡迎來到這次的面試」
  • 16:05: 結尾有點草率，應該要多說一些話然後在謝謝 interviewee 參加這場面試。

Interviewee

  • 講話語調太平，我自己聽了都想睡覺了。
  • 2:39: NULL 發音錯誤
  • 7:02: 「離開 while 迴圈」的發音全部連在一起，聽不清楚。
  • 14:13: NULL 發音錯誤

Medium 146. LRU Cahce

測驗說明與問答

🧔: 今天會要求你實作一個 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: 開頭應該避免使用「面試官」這種上對下的詞，可以改成「你好，歡迎來到這次的面試」
  • 0:02: 「這次的題目是」可以改成「這裡有一個 Cache 實作想要跟你討論」
  • 27:52: 沒有發現程式碼錯誤。

Interviewee

  • node 可以使用「節點」來代替；circular linked list 可以使用「環狀鏈結串列」代替，避免中英頻繁交錯。
  • 5:19: NULL 發音錯誤
  • 20:40、20:45: 「取值」發音發成「取址」
  • 24:13: 「把 next 跟 prev 維護成 circular linked list」說法怪怪的，不應該是「維護」。應該說「把 next 跟 prev 當作 circular linked list 的指標」。
  • 27:52: 程式碼錯誤，在 move_to_head 之後應該要將 value 進行修改。在後續的檢查過程也沒有檢查到。
  • 32:21: 停頓太久
  • 37:15: 「那個 hash table 位址的 address」意思不明確，應該要說「那個 hash 後對應到的 pointer 的 address」
  • 39:12: 發現講錯後應該要說「我更正一下」
  • 47:39: 應該是要說「circular linked list」但實際聽不太出來到底在講什麼。
  • 後面講話停頓越來越多，停頓的方式讓人想睡覺。

第二次作業 - 他評01

for interviewer

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

for interviewee

  • 優點

    • coding很流暢
    • 2:54 有適度手勢，肢體語言恰到好處
    • coding後有舉例加以驗證，確實做到Test

  • 可改進的地方

    • 咬字有時會較含糊，如 5:03 在說明時，部分地方語調較低時較難聽懂
    • 整體語調較平淡

第二次作業 - 他評02

for interviewer

  • 優點
  • 關於Easy 83. Remove Duplicates from Sorted List這題，有更進一步討論medium的變形，而且用不大的更動就實作出來
  • 可改進的地方
  • 關於Easy 83. Remove Duplicates from Sorted List這題，可以多討論一點，像是如果一開始給的linked list沒有排序的話，interviewee會怎麼想，不一定要實作出code，但是可以討論一下interviewee會怎麼做，例如建hash table看有無重複，或是interviewee就是直接排序，然後重複利用這題所寫的code

for interviewee

  • 優點
  • coding很順，講話蠻穩的
  • 可改進的地方
  • 沒啥問題

第二次作業-他評03

針對 Interviewer 的檢討:

  • 可以包裝一下題目
  • 可以和 Interviewee 多一些互動，Interviewee 寫完程式碼後，可以給予一些回饋

針對 Interviewee 的檢討:

  • 打完程式碼後有落實 Test 很棒!
  • 有主動提及時間複雜度
  • 確認題目時有帶一遍例子確認自己的理解，在寫程式碼前也有先闡述自己的做法很棒!
  • Problem 2 有做 follow up 很棒!
  • 44:09可以帶實際測資，不然很像是再把程式碼說一遍的感覺

第二次作業-他評04

interviewer

  • 最後優化完程式之後可以再針對程式碼進行測試，並且可以跟 interviewee 多一點問答，像是延伸題目、程式碼效能如何等等。

interviewee

  • 優點
  • 有利用範例去講解自己的邏輯。
  • 可改進的地方
  • 音量可以再大聲一點。
  • Merge Two Sorted List 中在講解程式碼的時候可以適當的寫註解，輔助敘述。
  • 舉例講解的時候可以把舉例放在程式碼裡面註解，這樣講解的時候就不用一直上下滑動滑鼠。
Last changed by 
 
sysprog
System Software Programming
0
142
Published on HackMD