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

貢獻者: 曉榕-Dawn

1. Two Sum

模擬面試錄影

面試官： 首先，讓我重複一下問題以確保我們理解了要求。給定一個整數數組 nums 和一個整數 target，我們需要找到數組中兩個不同的元素，它們的和等於 target，然後返回這兩個元素的索引。你的代碼已經實現了這個功能，但我們需要考慮一下它的時間複雜度。

曉榕： 我想我可以使用兩個迴圈來實行，因為題目保證有解，所以不用考慮其他情況。

vector<int> twoSum(vector<int>& nums, int target) {
    int tmp = 0;
    vector<int> answer(2,-1);
    for(int i = 0 ; i < nums.size(); i++){
        tmp = nums[i];
        for(int j = i+1; j < nums.size(); j++){
            if(tmp+nums[j] == target){
                answer[0] = i;
                answer[1] = j;
                break;
            }
        }
        if(answer[0] != -1){break;}
    }
    return answer;
}

面試官： 你的代碼已經實現了這個功能，但我們需要考慮一下它的時間複雜度。

曉榕： 是的，我使用了兩個嵌套的循環，所以時間複雜度是

O (n^{2})

，對嗎？

面試官： 是的，你的理解正確。但是，

O (n^{2})

的時間複雜度可能不適用於大型輸入數組。你能想到一種更有效率的方法來解決這個問題嗎？

曉榕： 我認為可以使用雜湊表來提高效率。首先，我可以遍歷一次數組，將每個元素及其索引存儲在雜湊表中。然後，再次遍歷數組，對於每個元素 nums[i]，我可以查找 target - nums[i] 是否存在於雜湊表中，如果存在，就可以找到滿足條件的兩個元素。

面試官： 你的思路是對的，使用雜湊表可以將時間複雜度降低到 O(n)，因為雜湊表的查找操作是平均常數時間。請嘗試實現這個思路並編寫代碼。

曉榕： 好的，我會嘗試編寫代碼。

vector<int> twoSum(std::vector<int>& nums, int target) {
    unordered_map<int, int> numToIndex; // 雜湊表，用於存儲元素及其索引
    vector<int> result; // 用於存儲結果

    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i]; // 計算當前元素的補數
        if (numToIndex.find(complement) != numToIndex.end()) {
            // 如果補數已經在雜湊表中，說明找到了答案
            result.push_back(numToIndex[complement]); // 補數的索引
            result.push_back(i); // 當前元素的索引
            return result;
        }
        // 將當前元素及其索引存入雜湊表
        numToIndex[nums[i]] = i;
    }

    // 如果沒有找到答案，返回一個空的結果
    return result;
}

曉榕： 新代碼的時間複雜度是 O(n)，因為我只遍歷了數組兩次，雜湊表的查找操作是常數時間。

面試官： 非常好，你已經成功降低了時間複雜度並提供了一個更有效的解決方案。這是一個很好的改進！你已經展示了很好的問題解決能力和編程技巧。非常感謝你的參與，曉榕！如果你有其他問題或需要進一步討論，請隨時告訴我。

1282. Group the People Given the Group Size They Belong To

模擬面試錄影

面試官（面）：你好，曉榕。我是你的面試官。

(唸題目部份剪掉，因為影片太長)

在這個問題中，我們有一組人分成一些未知數量的小組。每個人都有一個唯一的 ID，我們知道每個人應該在一個特定大小的小組中。你可以告訴我你對這個問題的理解嗎？

曉榕（新人）：所以…題目會給我一個陣列 groupSizes 裡面的index，對應到person i應該所待的組別大小?

面（面試官）：沒錯。接下來，你打算採用什麼解決方案?

曉榕: 使用了一個循環來遍歷人員和組的大小，然後根據大小將人員放入組中。

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> answer;
        vector<int> gSize;
        bool flag = false; //確認是否放入
        for(int pID=0; pID < groupSizes.size(); pID++){
            flag = false;
            for(int gID = 0; gID != gSize.size(); gID++){
                if(answer[gID].size()<gSize[gID] && groupSizes[pID] == gSize[gID]){ 
                    //同樣大小就放入且尚未滿員
                    answer[gID].push_back(pID);
                    flag = true;
                    break;
                }           
            }
            if(!flag){ //沒找到相同組別，就創一個新的
                answer.push_back({pID});
                gSize.push_back(groupSizes[pID]);
            }
        }
        return answer;
    }
};

面：很棒，請解釋時間複雜度。

曉榕: 整體的時間複雜度可以表示為 O(n * m)，其中 n 是輸入數組 groupSizes 的大小，m 是 gSize 數組的最大大小（最大組大小）。在最壞的情況下，m 可能等於 n，因此可以簡化為

O (n^{2})

。

面：那你有考慮其他方法來降低時間複雜度嗎?

曉榕：是的，我考慮過了。我可以優化我的方案，使用一個雜湊表來記錄每個小組的人員分配情況，然後在遍歷 groupSizes 數組時，根據小組大小直接將人員添加到對應的小組中。這樣，我只需要一次遍歷就能完成任務，而不需要多次查找和操作雜湊表。

面：很好，你可以嘗試實現這個優化的方案，然後與我分享你的代碼嗎？

曉榕：當然，我會嘗試實現並分享我的代碼。

#include <vector>
#include <unordered_map>

class Solution {
public:
    std::vector<std::vector<int>> groupThePeople(std::vector<int>& groupSizes) {
        std::unordered_map<int, std::vector<int>> groupMap;
        std::vector<std::vector<int>> answer;
        
        for (int i = 0; i < groupSizes.size(); ++i) {
            int size = groupSizes[i];
            groupMap[size].push_back(i);
            
            if (groupMap[size].size() == size) {
                answer.push_back(groupMap[size]);
                groupMap[size].clear();
            }
        }
        
        return answer;
    }
};

面：很棒，請解釋時間複雜度。

曉榕：這個代碼使用雜湊表 groupMap 來記錄每個小組的人員分配情況，然後一次遍歷 groupSizes 數組，根據小組大小直接將人員添加到對應的小組中。這樣，我們只需要一次遍歷就能完成任務，時間複雜度較低為O(n)。

面：你的優化方案看起來很不錯，時間複雜度降低了。有沒有考慮過對你的代碼進行測試以確保它能正常工作？

曉榕：是的，我會編寫一些測試用例來驗證我的代碼的正確性。
Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]

141. Linked List Cycle

模擬面試錄影

Interviewer: Welcome! Let's start with a coding question. The problem is as follows:

You are given the head of a linked list. Your task is to determine if the linked list has a cycle in it. A cycle in a linked list occurs if any node in the list can be reached again by continuously following the next pointer. You do not have access to the value of pos, which denotes the index of the node that the tail's next pointer is connected to.

Your job is to write a function that returns true if there is a cycle in the linked list, otherwise, return false.

Dawn: Okay, I think I understand the problem. I can use the two-pointer technique to solve this problem.

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;
        while(fast != NULL && fast -> next != NULL){
            slow = slow -> next;
            fast = fast -> next -> next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }
};

head = [3,2,0,-4], pos = 1

Interviewer: Thank you for your response. It seems you've implemented the two-pointer technique commonly known as Floyd's Tortoise and Hare algorithm, which is a popular and efficient way to detect cycles in a linked list. Can you explain how this algorithm works?

Dawn: Certainly! The idea behind the algorithm is to have two pointers traverse the linked list at different speeds. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there is a cycle in the linked list, the fast pointer will eventually catch up to the slow pointer, and they will meet at the same node. On the other hand, if there is no cycle, the fast pointer will reach the end of the list (become nullptr) before the slow pointer, and we can conclude that there's no cycle.

Interviewer: That's an excellent explanation of how the algorithm works. Now, let's discuss the time and space complexity of your solution. Can you analyze its time and space complexity?

Dawn: Certainly. The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. Both the slow and fast pointers traverse the list once. The space complexity is O(1) because we only use two pointers regardless of the size of the linked list.

Interviewer: Excellent job! You've provided a clear explanation of the algorithm and analyzed its time and space complexity. This is indeed the correct approach for solving this problem.

Dawn: Thank you!

自評-面試者

面試者不可自稱面試官。
應該要避免直接提出關鍵字，設計情境來讓應試者做思考。
三題的面試時間長短不一，應該要計時一下，作時間上的控管。
英文口語要多練習。

自評-應試者

應先將想發都提出，再進行複雜度的比較，這樣可以及減少寫不必要的程式的時間。
多跟面試者要反饋，畢竟這是一個溝通的過程。
這次過程中有盡量使用五個步驟原則（Repeat、Examples、Approach、Code、Test）來組織答案，但認為下次可以再更準確的實施此技巧。
英文口語要多練習。

第二次作業-他評01

interviewer

可改進的地方

如果面試官在出題的時候就將題目關鍵字表現出來，再加上function的名字就是leetcode其中一個題目的話，可能會無法考驗interviewee臨場的應變及想法。可以換一種方式描述問題，讓interviewee不會看到題目就有反射動作。
面試官直接把題目照著唸一遍, 念得斷斷續續, 完全沒有幫助到題目的理解還不如不要念
題目可以給一些example input output，會比較清楚。
interviewer可以將公司遇到的問題帶入題目來敘述會更好
以中文的抑揚頓挫來講英文會有聽起來不太順的感覺

interviewee

優點

最後的test階段講得很仔細欸~讚讚 👏
test和optimize的部分做的很確實

可改進的地方

可以在程式碼適當加上註解，方便interviewer回頭檢視
interviewer應該要依據公司需求再提出查看複雜度的要求
1:19: TwoSum題目當中Approach有點講的太少了，面試官只聽到interviewee要使用兩個迴圈就開始解題，應要在Approach階段解釋兩個迴圈分別是做什麼用途。
1:36: 第二題一樣Approach太少(我自己覺得)，原因如上。
3:31: 撰寫完程式碼應要解釋程式碼個部分的目的，在撰寫程式碼過程中透過interviewee的言語並未能完全了解像是nums陣列是代表什麼或是你解題的主要辦法是什麼，在影片中只聽到你宣告什麼東西或是用了什麼迴圈。(我覺得是因為interviewee在Approach階段並未能解釋完整)，覺得可以多增加一點在程式碼當中的講解。
1:35: 應該是英語對話但是interviewee說: …is also 呢，我有聽錯嗎 😆
可能需要先介紹何謂補數 4:36。

第二次作業-他評02

interviewer

優點

會給面試者鼓勵

可改進的地方

00:12，如果是中文面試的話直接用中文描述完問題就行了，逐字念的幫助不大
00:37, 1:04: 可以提供一個簡單的例子

interviewee

優點

程式碼indent對應整齊易看
說話速度適中，清晰

可改進的地方

1:06: 應該說明清楚他們兩個的index就是要回傳的東西，不是他們兩個本身
1:13, 1:30: approach只說用兩個for迴圈就沒了，其實可以說第一個迴圈做什麼?第二個迴圈做什麼等等
1:28: nums直接念整個字其實比較清楚，影片中tmp都可以念temp了
4:47: 「我的map裡面會放num array裡面的值」可改說 map裡面是如何會存入這些值的，不然聽起來會是一開始map就是題目陣列的duplicate。這個問題可以透過更詳細的解釋，甚至帶一個小例子解釋就不容易出現了。
2:57: gSize[size]的index是size嗎? 前面size沒有當index的說明
6:36: 如果像這樣的解釋可以在描述approach時就說，並搭配示意圖會更好
6:54: 「這個人」、「這個組別」、「他」、「這個」，這些指示代名詞在沒有東西呈現在畫面上單獨用口頭說的會不容易理解此時你在指哪個東西。可以真的將東西呈現在畫面上，舉個很小的例子，用滑鼠指會清楚很多。在寫程式的過程中也會說「這個」，其實可以更精確地描述是指什麼。
4:46 面試者請自行提出時間空間複雜度分析
3:03 fast 不是念作first，這樣念可能會有理解錯誤的可能

第二次作業-他評 03

關於 interviewer

優點

剪輯還有片頭片尾。

可改進的地方

00:05: 可以請對方把word上面的工具列收起來，畫面更乾淨。
不要直接使用leetcode上的題目。
可以多多練習英文口說。

關於 interviewee

優點

覺得講話速度適中。
有做優化不錯。
(漢1) 06:53 和(漢2) 07:24 以實際數字來細部清晰解釋程式邏輯。

可改進的地方

可以多多練習英文口說。
錄影背景一直閃爍，影響觀影。
REACTO，在Example和Approach並沒有做得很扎實。
- 像是 (漢語2) 01:28: 雖然有提出解題的approach，但講得太模糊。

第二次作業-他評04

interviewer

優點

說明題目的速度適中，聽得很清楚。
提出優化的方向，並給出需要優化的理由。

可改進的地方

00:11: 因為是中文面試，可以直接用中文將題意描述出來，不用以英文逐字念題。

interviewee

優點

口齒清晰，表達明確。
在寫新的程式碼段落前，都會先說明接下來程式碼的作用。
寫程式時，會同時說明這麼寫的優點是什麼👍。

可改進的地方

00:38: 可以將實際的數值範例打在word上，以此來說明對題目的了解。

第二次作業-他評05

interviewer

優點

面試官很友善，都會大致上引導方向

可改進的地方

互動稍微少

interviewee

優點

說話的語速剛好，聽得很清楚。
邊寫程式邊解釋自己正在寫的部分，沒有讓整個畫面尷尬。

可改進的地方

REACTO的部分可以做更好，雖然題目滿簡單的，但Example及test還是要做。
(Two sum) 3:40: 沒測試

第二次作業-他評06:

interviewer

優點

影片有片頭音效！

可改進

不過片頭音效還沒結束前，面試官就開始講話了，有點干擾到。
題目可以試著用別的情境包裝起來。

interviewee

優點

一邊coding一邊講解的很清楚。
口齒很清晰，很容易聽得懂在說什麼

可改進

REACTO可以再確實一點。

第二次作業-他評07

Interviewer

優點

問答清晰，點到問題
面試官友善

可改進的地方

感覺要變形下題目

Interviewee

優點

咬字清晰，2倍速下可聽，好評
每行都有清晰講解code的功能
片頭片尾好讚

可改進的地方

直接進入coding好像太快，可能可以遵守"確認，舉例，說明方案，撰寫程式，驗證程式"，延長時間，多點展現自己，不然好像考試刷提，特別是驗證程式

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

1. Two Sum

1282. Group the People Given the Group Size They Belong To

141. Linked List Cycle

自評-面試者

自評-應試者

第二次作業-他評01

interviewer

interviewee

第二次作業-他評02

interviewer

interviewee

第二次作業-他評 03

關於 interviewer

關於 interviewee

第二次作業-他評04

interviewer

interviewee

第二次作業-他評05

interviewer

interviewee

第二次作業-他評06:

interviewer

interviewee

第二次作業-他評07

Interviewer

Interviewee

Read more

淺談 Microkernel 設計和真實世界中的應用

並行程式設計: 概念

並行程式設計: Lock-Free Programming

2025 年 Linux 核心設計課程期末專題