# 2023年資訊科技產業專案設計 作業一 [影片](https://youtu.be/jAHPmNvnk-w?t=0) 👹 : interviewer 👾 : interviewee ## 21. Merge Two Sorted Lists > [影片](https://youtu.be/jAHPmNvnk-w?t=2) ### 測驗說明與問答 👹 : 屎地芬森先生你好，給你兩個linked list, 節點的順序都依照節點裡面的值排序好了, 請把它們合併然後回傳給我合併後的linked list head, 可以闡述你打算使用的解答做法, 然後實作 👾 : 我們先預設這個題目是升序排列的, 我的工作會是需要把`list1, list2`給合併成`mergeList`並且回傳list head 首先我的相法認為我們可以利用merge sort當中merge的做法來處理 一開始我會先定義一個結構體`struct node`如下 ```c struct node { int val; struct node *next; } ``` 👾 : 這裡使用的linked list是singly linked list 👾 : 接著考慮兩種特例也就是`list1`或`list2`其中一個為空, 或者兩者都為空的時候, 直接回傳即可 👾 : 接下來處理一般情況可以遞迴的處理, 每次挑出要加入`mergeHead`的node後, 把剩下的linked list繼續傳入`merge`當中處理 ```c struct node *merge(struct node *list1, struct node *list2) { struct node *mergeHead; if (!list1) return list2; if (!list2) return list1; struct node *cur_node1, *cur_node2; cur_node1 = list1; cur_node2 = list2; if (cur_node1->val > cur_node2->val) { mergeHead = cur_node2; mergeHead->next = merge(list1, list2->next); } else { mergeHead = cur_node1; mergeHead->next = merge(list1->next, list2); } return mergeHead; } ``` 👹 : `cur_node1, cur_node2`是否有存在的必要？另外可以分析時間複雜度嗎？ 👾 : 面試官說的沒錯, 確實不需要使用`cur_node1, cur_node2`就可以完成此算法, 改寫如下 ```c struct node *merge(struct node *list1, struct node *list2) { struct node *mergeHead; if (!list1) return list2; if (!list2) return list1; if (list1->val > list2->val) { mergeHead = list2; mergeHead->next = merge(list1, list2->next); } else { mergeHead = list1; mergeHead->next = merge(list1->next, list2); } return mergeHead; } ``` 👾 : 計算時間複雜度首先可以先列出遞迴式, 假設這個`merge`function的input size是$n$, 時間複雜度可以表示$T(n)$, 進行recursive call的時間複雜度會是$T(n-1)$, 其他部分的操作都是$O(1)$, 所以遞迴式可以表示成$T(n) = T(n-1) + O(1)$, 解這個遞迴式可以得到$T(n)=O(n)$ 👹 : 可以優化此算法嗎？ 👾 : 可以, 原本我沒有使用到編譯器的tail recursion特性導致遞迴呼叫之後會讓function stack不斷疊加, 我可以嘗試把程式改寫成non-recursive ```c struct node *merge(struct node *list1, struct node *list2) { struct node *mergeHead; if (!list1) return list2; if (!list2) return list1; struct node *cur_node; if (list1->val > list2->val) { mergeHead = list2; list2 = list2->next; } else { mergeHead = list1; list1 = list1->next; } cur_node = mergeHead; while (list1 && list2) { if (list1->val > list2->val) { cur_node->next = list2; list2 = list2->next; } else { cur_node->next = list1; list1 = list1->next; } cur_node = cur_node->next; } if (list1) cur_node->next = list1; if (list2) cur_node->next = list2; return mergeHead; } ``` 👾 : (使用測資測試...) 👹 : 屎地芬森先生謝謝你的作答, 答的不錯謝謝你 ## 24. Swap Nodes in Pairs > [影片](https://youtu.be/jAHPmNvnk-w?t=1717) ### 測驗說明與問答 👹 : 屎地芬森先生您好, 歡迎來到我們公司的面試, 我們給你一個問題, 給你一個linked list, 當中的值是隨機的, 希望你把節點兩兩交換, 並且不能直接修改node當中的值, 請你闡述你的解法之後再開始實作 👾 : 謝謝面試官，這個題目會提供給我一個linked list，之後把節點兩兩交換並且不能直接改變節點中的值 👾 : 首先我會先定義linked list的節點結構 ```c struct node { int val; struct node *next; } ``` 👾 : 再來思考兩個特別情況, 如果給我的linked list為空, 或者只有一個節點，那也沒有節點可以互換, 直接回傳即可 👾 : 再來處理一般情況, 使用`cnode`和`nnode`, `nnode`是`cnode`的下一個節點, 每次互換的時候把`cnode->next`指向原本的`nnode->next`, 然後把`nnode->next`指向`cnode` ```c struct node *SwapPairs(sturct node *head) { if (!head || !head->next) return head; struct node *cnode, *nnode; cnode = head; while (cnode && cnode->next) { nnode = cnode->next; cnode->next = nnode->next; nnode->next = cnode; cnode = cnode->next; } return head->next; } ``` 👹 : 可以使用一些測資確認正確性嗎？ 👾 : (測試...) 不好意思面試官, 有發現錯誤的部分, 請給我一點時間思考並修正 👹 : 沒問題 👾 : 謝謝面試官給我時間思考並修正, 我想可以利用一個指標來記錄前一組pairs的`cnode`, 因為錯誤的原因是`cnode->next`原本應該指向下一組的`nnode`, 但在我原本的做法中卻只會指向下一組的`cnode`, 所以我利用`pnode`來記錄上一組的`cnode`並把`pnode->next`指向當前的`nnode` ```c struct node *SwapPairs(sturct node *head) { if (!head || !head->next) return head; struct node *cnode, *nnode, *pnode; pnode = NULL; cnode = head; while (cnode && cnode->next) { nnode = cnode->next; if (pnode) pnode->next = nnode; pnode = cnode; cnode->next = nnode->next; nnode->next = cnode; cnode = cnode->next; } return head->next; } ``` 👹 : 可以請你計算時間複雜度嗎？ 👾 : 因為while loop在linked list上面走訪的時候不會往回走, 每個節點都只會走訪一次, 如果給定的linked list長度是$n$, 則時間複雜度就會是$O(n)$ 👹 : 屎地芬森先生謝謝你的作答 ## 83. Remove Duplicates from Sorted List > [影片](https://youtu.be/jAHPmNvnk-w?t=3103) ### 測驗說明與問答 👹 : Hello Mr.Stevenson, welcome to our company's interview. We have a question for you, you can describe your solution first and solve it. We're going to give you a sorted linked list with some duplicate values in it, please remove the duplicate nodes and make sure every value exists only once 👾 : Hello interviewer, I'm happy to be interviewed by your company and you. You're going to give me a head of a sorted linked list, and I'll have to remove all the duplicates, I want to make sure that I can assume the sorted order is ascending order right? and I still need remain the duplicate value in one node, not remove all of it right? 👹 : Yes your assumption is right, you can continue your answer 👾 : First I have to define a structure of the linked list node ```c struct node { int val; struct node *next; } ``` 👾 : I have to deal with speical case first, if you give me an empty linked list or a linked list with a single node. In both cases I'll just return the head back to you 👾 : For common cases, I'll use two pointer to `struct node`, `cnode, nnode`, and I'll compare the value of them like the following. Since we'll never remove the `head` node, the original `head` is still going to be the final `head` so we can just return `head` ```c struct node *RemoveDup(struct node *head) { if (!head || !head->next) return head; struct node *cnode, *nnode; cnode = head; nnode = head->next; while (nnode) { if (cnode->val == nnode->val) { cnode->next = nnode->next; } else { cnode = nnode; } nnode = nnode->next; } return head; } ``` 👹 : Can you calculate the time complexity of your algorithm? and I wonder that if you can use only one pointer to solve this problem? 👾 : I'll change my code using just one pointer first, becauze `nnode` is always `cnode->next`, so we can replace `nnode` ```c struct node *RemoveDup(struct node *head) { if (!head || !head->next) return head; struct node *cnode; cnode = head; while (cnode->next) { if (cnode->val == cnode->next->val) { cnode->next = cnode->next->next; } else { cnode = cnode->next; } } return head; } ``` 👾 : For the time complexity, assume the given linked list size is $n$, for each iteration in the while loop, the time complexity is $O(1)$, and we'll traverse each node exactly once, so the total time complexity is $O(n)$ 👹 : Thank you Mr. Stevenson. I've noticed that you remove the duplicate node by changing `cnode->next`, but the duplicate nodes are still alive in the system, can you try to delete it? 👾 : I know I didn't actually free the memory space of the duplicates node, I'll call these nodes as garbage node, and delete it like the following ```c struct node *RemoveDup(struct node *head) { if (!head || !head->next) return head; struct node *cnode; cnode = head; while (cnode->next) { if (cnode->val == cnode->next->val) { struct node *tmp = cnode->next; cnode->next = cnode->next->next; free(tmp); } else { cnode = cnode->next; } } return head; } ``` 👹 : Thank you very much Mr. Steveson.