---
# System prepended metadata

title: 2025 年「資訊科技產業專案設計」作業 1
tags: [資訊科技產業專案設計]

---

# 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
- 打鍵盤聲音偏大, 編譯器的顏色可能導致看不清楚
- 應該先解釋完要幹麻再開始打字
- 全部打完的時候可以簡述程式碼會如何運作