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

# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1 > 貢獻者: 屎地芬森-Stevenson > [模擬面試錄影: 中+英](https://youtu.be/JMWfE7LiMiY) > 👹 : interviewer > 👾 : interviewee ## 21. Merge Two Sorted Lists ### 測驗說明與問答 👹 : 屎地芬森先生你好，給你兩個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 ### 測驗說明與問答 👹 : 屎地芬森先生您好, 歡迎來到我們公司的面試, 我們給你一個問題, 給你一個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 ### 測驗說明與問答 👹 : 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. --- ## 第二次作業 - 他評 01 ### Interviewer - [ ] 優點 * [12:25](https://youtu.be/JMWfE7LiMiY?si=aYz1Qfkp0Y-YadhK&t=745): 有針對程式碼成改進的地方提出建議，感覺很棒。 * [1:14:00](https://youtu.be/JMWfE7LiMiY?si=i7mpB0XAer06ZbMA&t=4440): 在提出改進問題的同時，有提到在真實的機器會這樣做，與現實連結很好，如果能有更情境式的回應應該會更有感覺（例如我們公司的服務通常會這樣做）。 - [ ] 可改善的部份 * 第二題的部份，Interviewee 在驗證時發現問題後，Interviewer 有說自己其實有發現錯誤，很高興看到 Interviewee 自己發現錯誤。感覺如果 Interviewer 發現時能多問問題引導 Interviewee，會比讓 Interviewee 自己驗證找問題還好。 * [1:13:33](https://youtu.be/JMWfE7LiMiY?si=HJ6DBOneySI3TFdH&t=4413) 小心不要叫錯對方的名字XD ### Interviewee - [ ] 優點 * 每一題驗證作法是否正確時，都有考慮到特例。 * 每一題撰寫程式時的說明很清楚。 * 第二題的驗證有自己發現錯誤，這樣的驗證很有意義。 * 打code時的講解，蠻流暢的。 - [ ] 可改善的部份 * [7:39](https://youtu.be/JMWfE7LiMiY?si=rJKJ3kZiGrj6KdN-&t=459): 如果指的是 Traversal，那應該要說「遍歷」而非「歷遍」。 * [10:49](https://youtu.be/JMWfE7LiMiY?si=i9NpH4Lp7RglaBF1&t=649): 之後改寫程式碼的部份，有把本來已經寫好的部份改掉（cur_node2 = cur_node_2->next、cur_node1 = cur_node1->next），這部份感覺有點可惜，畢竟面試應該避免撰寫不必要的東西。雖然您講解的很詳細、順暢，但給我的感覺很像在聽課，如果能在撰寫程式前先簡單口頭說明一下作法，撰寫程式時再一邊寫一邊說自己目前正在寫什麼（也就是遵循 REACTO 的 Approach、Coding），我想就能避免寫了又刪除的情況。 * [16:04](https://youtu.be/JMWfE7LiMiY?si=z7mHKqnSLbgdJief&t=964): 感覺本來差一點要講錯（我們都知道 O(1) 幾個加起來都一樣），不過後面有轉回來。如果您本來就確定是想說時間複雜度是 $O(n)$，我認為可以省略這句話（我們都知道 O(1) 幾個加起來都一樣），列完遞迴式後說結論即可。 * cnode和nnode的命名或許可以更一目瞭然 [32:29](https://youtu.be/JMWfE7LiMiY?t=1949): 也可以嘗試在旁邊寫註解，尤其是cnode聽不太清楚。 ## 他評02 ### Interviewer - [ ] 優點 * [12:19](https://youtu.be/JMWfE7LiMiY?t=739): 對於程式碼的提問有明確指出問題。 - [ ] 可改進的地方 * 在定義 list 中的 node 的結構，是否是交給面試者去定義呢?這樣為了作答方便，面試者採取 doubly-linked list 也行，我認為應該由面試官來定義清楚吧。 ### Interviewee - [ ] 優點 * 寫程式邊舉例子說出想法以及例子後再撰寫，不會有讓人模不著頭緒，為何這邊要這樣寫的感覺，很貼心! * 有主動說出錯誤的地方，很棒! - [ ] 可改進的地方 * 問完問題後應該可以大致講一下你的程式會如何去實作，程式當中一些細節可以再由撰寫程式中說出，像是 while 迴圈終止條件之類的。 ## 第二次作業 - 他評 03 ### Interviewer - [ ] 優點 * 開場白很完整自然 - [ ] 可改善的部份 * (第一題) 和 interviewee 互動較少 * [16:44](https://youtu.be/JMWfE7LiMiY?si=9EfBr6Zu5kk2q3i0&t=1004) algorithm 的正體中文翻譯為「演算法」而非「算法」 * 說話時游標可以不要一直上下來回移動，如 [16:52](https://youtu.be/JMWfE7LiMiY?si=-ufIrtpBpxvRKuC_&t=1013) * [52:27](https://youtu.be/JMWfE7LiMiY?si=xN7uD_MH-rFX1kP2&t=3147) duplicates 當形容詞和名詞時的發音為 [ˋdjupləkɪts] 而非 [ˋdʌpləkɪts] ### Interviewee - [ ] 優點 * (第一題) Repeat 的部分很清楚完整 * 口齒清晰 - [ ] 可改善的部份 * 說話時游標可以不要一直上下來回移動，如 [2:13](https://youtu.be/JMWfE7LiMiY?si=YPTXFsHV2bYmMckB&t=133)、[12:45](https://youtu.be/JMWfE7LiMiY?si=mTp4BqoboSTZulLB&t=765)、[14:35](https://youtu.be/JMWfE7LiMiY?si=85fPgwm9K92IENPy&t=875)、[17:01](https://youtu.be/JMWfE7LiMiY?si=y_g6d33Na8Ad5Cad&t=1021) 等 * (第一題) 在假設題目為升序排列或 singly linked list 時，可以改為向面試官提問，而非自己直接假設，以免自己假設的情況和面試官想要的不符 * (第一、二、三題) C 和 C++ 中的 [struct declaration](https://en.cppreference.com/w/c/language/struct) 需要有分號結尾 * Approach 和 Code 的部分應該拆開來，先完整描述想到的解法，與面試官討論完後再進行實作，以免或是實作的方向不合面試官預期 (如面試官希望看到疊代的寫法，但面試者卻使用遞迴的寫法) * [20:30](https://youtu.be/JMWfE7LiMiY?si=TVDqqfigikNcxLVj&t=1230) 程式碼超出頁面時可以不需要用一堆 enter 把程式碼擠到下一頁，可以在程式碼上方插入新頁面，或是把「查看>顯示列印版面配置」的選項取消勾選 (如下圖)，即可讓跨頁面的文字內容連續呈現 ![](https://hackmd.io/_uploads/H1LmInKZ6.png) ## 他評04 ### Interviewer - [ ] 優點 * 模擬面試先預設了題目已經預先傳送給Interviewee，解決了Interviewee畫面已經先有完整題目的不合理處。 * Interviewer 每次給的指示都很明確，不會讓Interviewee在實作時摸不清頭緒。 - [ ] 可改進的地方 * 一開始自稱面試官，以及說這是你的"工作"，聽起來蠻有壓迫感的，不太有利於後續的對等討論。 ### Interviewee - [ ] 優點 * 在驗證作法可行性時連帶特殊的情況都有一併考慮，且撰寫程式的過程也會附帶說明。 * 撰寫程式碼與講解時，整體過程很流程。 - [ ] 可改進的地方 * 說明完解題思路後，可以跟Interviewer進行相應的討論，或是反向提問，來讓Interviewer 更加理解你的想法，也避免發生程式需求上的落差。