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

貢獻者: 霍夫曼-Mark Hoffman
英文模擬面試錄影-1
英文模擬面試錄影-1
英文模擬面試錄影-3

🧑‍🦳面試官
👦面試者 - Mark Hoffman (霍夫曼)

重點摘要：

LeetCode 268 - Missing Number

🧑‍🦳: 給你一個長度為 n 的整數陣列，其中應該包含 [0, n] 所有整數，請你找出陣列中遺漏的數字。

👦: 我的作法是建立一個長度為 n+1 的整數陣列，在原始陣列的迭代過程中紀錄每一個數字的出現次數，最後再從新建的陣列中找出 0 並回傳索引值。

👦: 程式實作。

class Solution {
public:
    int missingNumber(vector <int> & nums) {

        int n = nums.size();

        vector <int> occurrences(n + 1, 0);

        int i = 0;

        for (; i < n; ++i) {
            occurrences[nums[i]] += 1;
        }

        for (i = 0; i <= n; ++i) {
            if (occurrences[i] == 0) {
                return i;
            }
        }

        return -1;
        
    }
};

🧑‍🦳: However, this approach might have issues with overflow when dealing with very large ranges of numbers. Can you improve your code to handle all cases?

👦: 我可以把陣列的資料型態從「32位元的整數」改成「8位元的布林值」，這樣應該能節省一些空間。程式實作。

class Solution {
public:
    int missingNumber(vector <int> & nums) {

        int n = nums.size();

        vector <bool> occurrences(n + 1, false);

        int i = 0;

        for (; i < n; ++i) {
            occurrences[nums[i]] = true;
        }

        for (i = 0; i <= n; ++i) {
            if (!occurrences[i]) {
                return i;
            }
        }

        return -1;
        
    }
};

🧑‍🦳: 你這樣確實能節省記憶體的使用量，但是效果有限，請你分析一下你的時間複雜度和空間複雜度。

👦: 由於程式共進行了兩次 O(n) 的迭代，故時間複雜度為 O(2n) = O(n)，而空間複雜度則是 O(n)，因為我們建立了一個長度為 n+1 的陣列。

🧑‍🦳: 分析得不錯！你說你的空間複雜度是 O(n)？我希望你把它降到 O(1)。

👦: 我想到一個更好的解法，因為每一個數字只會出現一次，他們的總和會是 1+2+3+…+n = (n+1)×n÷2，與其記錄出現次數，我們可以將所有數字加總起來，最後再與公式解相減，它們的差就會是漏掉的數字。

👦: 程式實作。

class Solution {
public:
    int missingNumber(vector <int> & nums) {

        int n = nums.size();

        int expect = (n + 1) * n / 2;

        int actual = 0;

        for (int i = 0; i < n; ++i) {
            actual += nums[i];
        }

        int difference = expect - actual;

        return difference;
        
    }
};

LeetCode 387 - First Unique Character in a String

🧑‍🦳: 給你一個只有小寫字母的英文字串，請你找出第一個只出現一次的字元。

👦: 我的作法是透過第一次的迭代記錄每一個字元的出現次數，並在第二次的迭代檢查其出現次數，如果次數為 1 就回傳索引值，如果最後沒有符合條件的字元就回傳 -1。

👦: 程式實作。

class Solution {
public:
    int firstUniqChar(string s) {

        map <char, int> occurrences;

        int n = s.length();

        int i = 0;

        for (; i < n; ++i) {

            if (occurrences.find(s[i]) == occurrences.end()) {
                occurrences[s[i]] = 1;
                continue;
            }

            occurrences[s[i]] += 1;

        }

        for (i = 0; i < n; ++i) {

            if (occurrences[s[i]] == 1) {
                return i;
            }
        }

        return -1;

    }
};

🧑‍🦳: 請你分析一下你的程式的時間複雜度與空間複雜度。

👦: 程式碼有用到 map 這個結構，存取裡面的值為 O(log n)，但因為總共只有 26 個英文字母作為 key，因此其複雜度可視作 O(1)，而呼叫次數又為 n 次，故時間複雜度為 O(n)。空間複雜度則為 O(1)，原因同上（只有 26 個英文字母）。
🧑‍🦳: 你能不能讓你的程式跑得更快一點？

👦: 我可以把 map 換成一般的 C 陣列，這樣存取資料只要一個指令，而不是進行二分搜尋（Binary Search）。

👦: 程式實作。

class Solution {
public:
    int firstUniqChar(string s) {

        constexpr int p = 123;

        int n = s.length();

        int occurrences[p];

        int i = 97;

        for (; i < p; ++i) {
            occurrences[i] = 0;
        }

        for (i = 0; i < n; ++i) {
            occurrences[s[i]] += 1;
        }

        for (i = 0; i < n; ++i) {
            if (occurrences[s[i]] == 1) {
                return i;
            }
        }

        return -1;
        
    }
};

LeetCode 16 - 3-Sum Closest

🧑‍🦳: 給你一個整數陣列 nums 和一個整數 target，請你找出最接近 target 的三個數的和。

👦: 我的作法是用三層巢狀迴圈，找出陣列中所有可能三個數的和，並記錄最接近 target 的答案。

👦: 程式實作。

class Solution {
public:
    int threeSumClosest(vector <int> & nums, int target) {
        
        int i, j, k, n = nums.size(), n_1 = n - 1, n_2 = n - 2;

        int tmpSum, closestSum = INT_MAX / 2;

        for (i = 0; i < n_2; ++i) {

            for (j = i + 1; j < n_1; ++j) {

                for (k = j + 1; k < n; ++k) {

                    tmpSum = nums[i] + nums[j] + nums[k];

                    if (std::abs(tmpSum - target) < std::abs(closestSum - target)) {
                        closestSum = tmpSum;
                    }

                }
            }
        }

        return closestSum;
        
    }
};

🧑‍🦳: 我想請你分析你的程式碼的複雜度。

👦: 因為我用了三層的巢狀迴圈，而每一層都會進行 O(n) 的迭代，因此我的程式碼的時間複雜度是 O(n^3)。空間複雜度則是 O(1)。

🧑‍🦳: 你的時間複雜度是 O(n^3)？

👦: 是的，不過我想到了一個降低複雜度的方法。與其用三層的巢狀迴圈，我們可以先將陣列進行排序，再將最內層的迴圈改為二分搜尋。程式實作。

class Solution {
public:
    int threeSumClosest(vector <int> & nums, int target) {
        
        int i, j, k, n = nums.size(), n_1 = n - 1, n_2 = n - 2;

        int tmpSum, closestSum = INT_MAX / 2;

        std::sort(nums.begin(), nums.end());

        for (i = 0; i < n_2; ++i) {

            for (j = i + 1; j < n_1; ++j) {

                auto sectBegin = nums.begin() + j + 1;

                int remain = target - nums[i] - nums[j];

                auto found = std::lower_bound(sectBegin, nums.end(), remain);

                if (found < nums.end()) {

                    tmpSum = *found;

                    if (found > sectBegin) {
                        if (std::abs(*(found - 1) - remain) < std::abs(tmpSum - remain)) {
                            tmpSum = *(found - 1);
                        }
                    }

                }
                else {

                    tmpSum = *(found - 1);

                    if (found < (nums.end() - 1)) {
                        if (std::abs(*(found + 1) - remain) < std::abs(tmpSum - remain)) {
                            tmpSum = *(found + 1);
                        }
                    }

                }

                tmpSum = tmpSum + nums[i] + nums[j];

                if (std::abs(tmpSum - target) < std::abs(closestSum - target)) {
                    closestSum = tmpSum;
                }
                
                
            }

        } 

        return closestSum;

    }
};

🧑‍🦳: 不錯，那麼你的時間複雜度現在是多少？

👦: 兩層的巢狀迴圈加上一個二分搜尋的複雜度是 O(n^2 log n)。

🧑‍🦳: 你說你的時間複雜度是 O(n^2 log n)？你不覺得它還是有點慢嗎？你能讓它再快一點嗎？

👦: 你要我讓它再快一點？因為陣列已經排序過了，因此隨機三個數，靠左的數較小，而靠右的數較大。如果三數的和過大，就把最小值（左）換成更小的值；如果三數和過小，就把最大值（右）換成更大的值。這樣時間複雜度就會是 O(n log n)。程式實作。

class Solution {
public:
    int threeSumClosest(vector <int> & nums, int target) {
        
        int i, j, k, n = nums.size(), n_1 = n - 1, n_2 = n - 2;

        int tmpSum, closestSum = INT_MAX / 2;

        std::sort(nums.begin(), nums.end());

        for (i = 1; i < n_1; ++i) {

            j = i - 1;

            k = i + 1;

            while ((j >= 0) && (k < n)) {

                tmpSum = nums[i] + nums[j] + nums[k];

                if (std::abs(tmpSum - target) < std::abs(closestSum - target)) {
                    closestSum = tmpSum;
                }

                if (tmpSum < target) {
                    k += 1;
                    continue;
                }

                if (tmpSum > target) {
                    j -= 1;
                    continue;
                }

                break;
                
            }

        } 

        return closestSum;

    }
};

初步檢討：

REACTO 之 E 部分，應該更全面列舉例子，尤其是第三場面試。
受試者及面試官說話之節奏過於單調，缺乏熱忱。
受試者應盡可能一開始就提出最佳解，以免浪費時間。
受試者與面試官應多互動，尤其是受試者，應該取得面試官的回饋。
若遇到意外（第三場面試），受試者應立即修正錯誤，而非等面試官指點。

第二次作業-他評01

關於interviewer

可改進之處
4:51: 就如同你上面說的，若是受試者在test階段發現錯誤時要請受試者修改程式碼。

interviewee

優點

有在撰寫程式碼時適當加入註解讓 code 更明瞭
REACTO各階段講的都蠻詳細的

可改進之處

因為是在leetcode上直接做編譯跟測資，但是我會比較想要受試者自己用測資帶入程式內部去做測試。
建議不要使用leetcode當作coding工具，受試者可能會看到leetcode題目當中關鍵字就容易想出解題方針。

第二次作業-他評02

關於interviewer

面試者提出
$O (n^{2})$ 可以適時的提點面試者，因為本來就會預期大概在submit階段過不了
提示不會太多也很剛好，很符合實際卡關時會面對的情況

關於interviewee

對暴力解的優化展現面試者對C++語言上操作的靈活性跟熟悉度。
整體上對於暴力解跟優化解法都給出很清楚的解釋

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

重點摘要：

LeetCode 268 - Missing Number

LeetCode 387 - First Unique Character in a String

LeetCode 16 - 3-Sum Closest

初步檢討：

第二次作業-他評01

關於interviewer

interviewee

第二次作業-他評02

關於interviewer

關於interviewee

Read more

解析 Linux 共享記憶體機制

Linux 核心設計: 記憶體管理

運用 Perf 分析程式效能並改善

你所不知道的 C 語言：動態連結器篇