# 2025 年「資訊科技產業專案設計」作業 1
> 貢獻者: 摩斯 Morse
> [video]()
🧑💻 : interviewer 👨🎓 : interviewee
> [模擬面試錄影: 漢1](https://youtu.be/bIImb870RAE)
> [模擬面試錄影: 漢2](https://youtu.be/__W9F6W3Cos)
> [模擬面試錄影: 英](https://youtu.be/egmHJLuDYLU)
## [21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/description/)
#### 測驗說明與問答
>You are given the heads of two sorted linked lists list1 and list2.
>
>Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
>
>Return the head of the merged linked list.
#### 面試紀錄
🧑💻 : 在第一道題目中，給你兩個排序過的 linked list ，請你將這兩者合併後，回傳合併後的 linked list 的 head。
👨🎓 : 所以我的程式碼的輸入會是兩個 list 的 head ， 我需要將這兩個 list 做合併後回傳合併後 list 的 head 這樣正確嗎 ?
🧑💻 : 沒錯，你的理解是對的。
👨🎓 : 想請問合併後的 linked list 需要排序完成嗎 ?
🧑💻 : 是的，合併後的陣列應該要是排序過的。
👨🎓 : 有可能會有空的 list 的情況嗎 ?
🧑💻 : 有可能，需要考慮進去。
👨🎓 : 了解。為了確認我有理解，我想舉個例子。假設題目給兩個排序過的 list 分別是 (1 $\to$ 4 $\to$ 5 $\to$ 6) 及 (1 $\to$ 3 $\to$ 4 $\to$ 7) 最後結果應該要是 (1 $\to$ 1 $\to$ 3 $\to$ 4 $\to$ 5 $\to$ 6 $\to$ 7), 這樣正確嗎 ?
🧑💻 : 沒錯。
👨🎓 : 我目前直覺的想法是，先建立一個 dummyHead 並且用一個變數 curr 來追蹤目前處理到哪個 node。在兩個 list 都還有元素的情況下，先判斷哪個目前的 head 值最小，依序接在 head 這個新的 list 後方，當有一個 list 已經空掉後便把另一個直接接在 curr 後方，最後再回傳 dummyHead 的 next 。
🧑💻 : 這樣時間複雜度為何呢 ?
👨🎓 : 假設兩個 list 分別長度是 m 跟 n ，最差的情況下我會需要迴圈到每個元素，因此會是 O(m+n)。
#### Iterative version
```cpp
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode dummyHead = ListNode();
ListNode* curr = &dummyHead;
while(list1 && list2){
if(list1->val < list2->val){
curr->next = list1;
list1 = list1->next;
}else{
curr->next = list2;
list2 = list2->next;
}
curr = curr->next;
}
curr->next = (list1)?list1:list2;
return dummyHead.next;
}
```
<!-- Optimize:
```cpp
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode *head;
ListNode** tail = &head;
while(list1 && list2){
if(list1->val < list2->val){
*tail = list1;
list1 = list1->next;
}else{
*tail = list2;
list2 = list2->next;
}
tail = &((*tail)->next);
}
*tail = (list1)?list1:list2;
return head;
}
``` -->
🧑💻 : 是否有不是 iterative 的方法呢?
👨🎓 : 我的想法是可以把問題切成小塊，每次先比較兩個 list 目前 node 的數值後，遞迴處理剩下的內容。如果目前的 list 是空的，則直接回傳另一個 list 接在後面。
#### Recursive version
```cpp
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(!list1) return list2;
if(!list2) return list1;
if(list1->val < list2->val){
list1->next = mergeTwoLists(list1->next,list2);
return list1;
}else{
list2->next = mergeTwoLists(list1,list2->next);
return list2;
}
}
```
## [104. Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/description/)
#### 測驗說明與問答
> Given the root of a binary tree, return its maximum depth.
>
>A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
#### 面試紀錄
🧑💻 : 在第二道題目中，你會有一個 Binary Tree 當作 input，你需要回傳這棵 Binary Tree 的 Maximum Depth。
👨🎓 : 好，所以我的程式碼會需要一個 input ，可能會是一個 Binary Tree 的 root，我需要去計算整棵 Binary Tree 的最大深度之後回傳一個整數值，表示這顆樹的深度。
👨🎓 : 我這邊想到的是用 DFS 的方式去處理，因為 root 的深度會比左右兩個子節點深度中最大的那個再加一，因此我的 DFS 回傳數值會是兩者做 DFS 後的最大值再加上 1。這樣就可以一路從葉節點往上推得 Binary Tree 的深度了。
🧑💻 : 這樣時間複雜度會是多少呢?
👨🎓 : 因為每個節點都會被探索到一次，所以時間複雜度會是 O(N)，其中 N 是節點數量。
🧑💻 : 好，你可以開始打程式碼了。
#### dfs
```cpp
int dfs(TreeNode* root) {
if(!root){
return 0;
}
return max(dfs(root->right), dfs(root->left)) + 1;
}
int maxDepth(TreeNode* root) {
return dfs(root);
}
```
<!-- #### bfs
```cpp
int maxDepth(TreeNode* root) {
if (!root) return 0;
std::queue<TreeNode*> q;
q.push(root);
int depth = 0;
while(!q.empty()){
int size = q.size();
for(int i = 0; i< size; i++){
TreeNode* node = q.front();
q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
depth ++;
}
return depth;
}
``` -->
## [621. Task Scheduler](https://leetcode.com/problems/task-scheduler/description/)
#### 測驗說明與問答
>You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there's a constraint: there has to be a gap of at least n intervals between two tasks with the same label.
>
>Return the minimum number of CPU intervals required to complete all tasks.
#### 面試紀錄
🧑💻 : Since you have some experience developing schedulers with sched_ext, let’s have a small exam about scheduling.
👨🎓 : Sure!
🧑💻 : Here’s the problem. You are given an array of tasks, each labeled with a letter from A to Z. In each CPU interval, the CPU can either stay idle or execute one task. There is one constraint: there must be at least n intervals between two tasks with the same label.
👨🎓 : Is there only a single CPU?
🧑💻 : Yes, assume there is just one CPU available.
👨🎓 : Okay! My first approach would be to build a max-heap that stores the remaining counts of tasks that are ready to be scheduled. In addition, I would maintain a waiting queue to keep track of tasks that are cooling down. For each entry in the waiting queue, I would store both the remaining count of that task and the earliest time when it can be scheduled again.
🧑💻 : And how would you represent the tasks in the max-heap?
👨🎓 : Instead of storing the task labels themselves, I would store their remaining counts, since the actual scheduling only depends on how many times each task still needs to be executed.
```cpp
int leastInterval(vector<char>& tasks, int n) {
vector<int> Count(26, 0);
for (int i = 0; i < tasks.size(); i++) {
Count[tasks[i] - 'A']++;
}
priority_queue<int> maxHeap;
for (int i = 0; i < 26; i++) {
if (Count[i] != 0) {
maxHeap.push(Count[i]);
}
}
queue<pair<int, int>> waiting_queue;
int time = 0;
while (!maxHeap.empty() || !waiting_queue.empty()) {
time++;
while (!waiting_queue.empty() &&
waiting_queue.front().second <= time) {
maxHeap.push(waiting_queue.front().first);
waiting_queue.pop();
}
if (!maxHeap.empty()) {
int top = maxHeap.top() - 1;
maxHeap.pop();
if (top != 0) {
waiting_queue.push({top, time + n + 1});
}
}
}
return time;
}
```
🧑💻 : Great. Then what’s the time complexity of your algorithm?
👨🎓 : To build the frequency count of the tasks, we only need to traverse all T tasks, so that takes O(T). Building the max-heap involves at most 26 task types, which is effectively O(1). In the main loop, each push and pop operation on the max-heap costs O(log k), where k is the heap size. Since each task can only be pushed and popped once, this part totals to O(T log k). But since k ≤ 26, we can treat log k as a constant. So overall, the time complexity is O(T).
🧑💻 : Well done. That concludes today’s interview. Thanks for your time, and I hope to see you again!
## 初步檢討
#### 21. Merge Two Sorted Lists
##### Interviewer
- 回應較少, 只是單純回答是非題而已
- 沒有回答到 interviewee 詢問舉例是否正確
- 對於完成的程式碼沒有過多的詢問，尤其後半段 recursive 部份
##### Interviewee
- 應關閉編譯器提示功能或是改用記事本, 避免彈出視窗干擾。Ex: 打範例時輸錯成 int_64
- 精確的說回傳的是"指向 1 這個的指標" 而不是說 "回傳 1 這個的位置"，不夠精確
- 在 Approach 部份說明較亂，並沒有明確的說到解題的關鍵，只是單純把後面要打的程式碼一步一步講出來, 但沒看程式碼的人可能會聽不懂自己在講啥。
- Coding 部份，可以適時的打上一些註解。沒有解釋為何需要建立 dummyHead 或是解釋目前這樣寫的目的為何。
- 雖然問了 "有可能會有空的 list 的情況嗎 ?" 但並沒有特別處理。
- 在說明 recursive 方式部份講解不清楚
#### 104. Maximum Depth of Binary Tree
##### Interviewer
- 沒有回應到 Interviewee 重述題目的部份
##### Interviewee
- 同樣的應該要關閉編譯器提示功能
- 解釋 revursive 時不太清楚，沒有確實的講到為何需要用 recursive ，這樣聽起來很像本來就知道答案了。
- 舉例時花太多時間畫樹，且忘記打成註解
#### 621. Task Scheduler
##### Interviewer
- Interviewee 講完 Approach 後沒有再追問相關的內容
##### Interviewee
- 太多常用的語助詞: so, that... 之類的
- 沒有先確認就直接講 Approach
- 打鍵盤聲音偏大, 編譯器的顏色可能導致看不清楚
- 應該先解釋完要幹麻再開始打字
- 全部打完的時候可以簡述程式碼會如何運作
Sign in with Wallet
Connect another wallet