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

暱稱: 呆呆獸 Slowpoke
👨‍💼： Interviewer
🙋‍♂️： Intreviewee

27. Remove Element (Easy)

錄影

模擬面試過程

👨‍💼： 今天的面試，我們希望你能夠實作 Remove Element，這個算法可以幫助我們快速地清理數據，我們會給你一段整數 array 跟一個指定的整數 K，希望你能將所有等於 K 的值排列在 array 的最前面，並回傳不等於 K 的數量，array 內的其他數值以及 array 的大小並不重要。要注意的是，所有動作必須要 in-place。
👨‍💼： Array 的長度為 0~100，數值大小介於 0~50。
🙋‍♂️： 我想舉個例子確認一下題意。

Input: nums = [1,3,2,2,3], K = 3
Output: 3, nums = [1,2,2,_,_]

🙋‍♂️： 請問這個例子正確嗎?
👨‍💼： 沒有問題。
🙋‍♂️： 我的想法是使用一個 for 迴圈去看過每一個數值，如果不等於 K，就會把他往前放，所以我會再添加一個指標來記錄上次往前放的位置。
👨‍💼： 了解，你可以開始進行實作了。

int removeElement(vector<int>& nums, int K) {
    int ptr = 0;
    for (int i=0; i<nums.size(); i++){
        if (nums[i] != K){
            nums[ptr] = nums[i];
            ptr++;
        }
    }
    return ptr;
}

🙋‍♂️： 由於只有一層 for 迴圈，所以時間複雜度為

$O(N)$。
👨‍💼： 程式碼沒問題。
👨‍💼： 但你的程式看似有一些多餘的步驟，比如在你的舉例當中，1 會寫入 1 自己的位置，你有什麼解決辦法嗎?
🙋‍♂️： 那我另一個指標應該要從 array 的後面開始找，如果前面的指標遇到等於 K 的數字，就要跟後面指標交換，接著更新指標位置，直到前後指標重合。

int removeElement(vector<int>& nums, int K) {
    int i=0;
    int j = nums.size()-1;
    while (i<=j){
        if (nums[i] == K){
            nums[i] = nums[j];
            j--;
        }
        else{ i++; }
    }
    return j+1;
}

👨‍💼： 看起來沒什麼問題，我們再舉個例子測試一下。

Input: nums = [1], K = 1
Output: 0, nums = [_]

👨‍💼： Okey，沒有問題。
👨‍💼： 但在現實情境中，有時候我們會希望資料經過刪除後，同時資料所占用的空間也變少。對應到這個題目，我們希望在 Remove Element 後， capacity 也可以降低，你會怎麼修改呢?
🙋‍♂️： 我會使用 C++ 中 copy 跟 swap 的特性來完成，首先將原本的 array 複製一份到新的空間，這個步驟配置剛剛好的容量，接下來使用 swap 來改變記憶體位置。

int removeElement(vector<int>& nums, int val) {
    int i=0;
    int j = nums.size()-1;
    while (i<=j){
        if (nums[i] == val){
            nums[i] = nums[j];
            j--;
        }
        else{ i++; }
    }
    int result = j+1;
    nums.erase(nums.begin()+result, nums.end());
    vector<int>(nums).swap(nums);
    return result;
}

15. 3Sum (Medium)

錄影

模擬面試過程

👨‍💼： "3Sum" 是一個經典的算法問題，稍加改良後，能夠應用在資料庫查詢或金融交易分析中。在這個問題中，輸入會是一串整數，我們希望找出所有不重複的三個數字組合，使它們的總和等於零，請注意你的答案不能有重複的組合。
👨‍💼： 總共有 3 ~ 3000 個數值，數值的大小介於

$-{10}^5$ ~

${10}^5$
🙋‍♂️： 請問 input 和 output 的資料型態, 我可以假設是 C++ 中的 vector 嗎？
👨‍💼： 可以這樣假設。
🙋‍♂️： 好的，為了更好的理解題目，我想舉個例子確認一下。

輸入： [-1,0,1,2,-1,-1,-1,2]
輸出： [[-1,-1,2],[-1,0,1]]

🙋‍♂️： 請問這樣有符合題意嗎?
👨‍💼： 這樣有符合。
🙋‍♂️： 那如果找不到符合條件的解，是不是回傳空的 vector 即可?
👨‍💼： 對。
🙋‍♂️： 我最初步的想法，是使用三層迴圈去找到所有解，並使用集合去儲存這些解以避免重複，不過這個演算法的時間複雜度是

$O(N^3)$，非常沒有效率，所以我會想使用雙指標來解決這個問題。首先，先對所有數值做升冪排序，接著使用一層 for 迴圈，每次固定一個值，剩下兩個值使用雙指標去選出來。
👨‍💼： 了解，你可以開始進行實作了。

vector<vector<int>> threeSum(vector<int>& nums) {
    int length = nums.size();
    set<vector<int>> result_set = {};

    sort(nums.begin(), nums.end());
    for (int i=0; i<length-2; i++){
        int left = i+1;
        int right = length -1;
        while (left < right){
            if ((nums[i] + nums[left] + nums[right]) > 0) { right--;}
            else if ((nums[i] + nums[left] + nums[right]) < 0) {left++;}
            else {
                result_set.insert({nums[left], nums[i], nums[right]});
                left++;
            }
        }

    }
    vector<vector<int>> result(result_set.begin(), result_set.end());
    return result;
}

🙋‍♂️： 排序的時間複雜度為

$O(N\log N)$，迴圈跟雙指標的時間複雜度為

$O(N^2)$，所以這個演算法的時間複雜度為

$O(N^2)$。
👨‍💼： 你目前的演算法有用到集合，插入元素的時候，會需要維護的成本，如果不要使用集合，你有什麼想法嗎?
🙋‍♂️： 有的，重複的組合是由於相同的數值被選擇多次造成的，我們可以利用排序過後的特性，當連續出現相同數值時，可以直接跳過，來避免選到重複的組合。

vector<vector<int>> threeSum(vector<int>& nums) {
    int length = nums.size();
    vector<vector<int>> result = {};

    sort(nums.begin(), nums.end());
    for (int i=0; i<length-2; i++){
        int left = i+1;
        int right = length -1;
        while (left < right){
            if ((nums[i] + nums[left] + nums[right]) < 0) {left++;}
            else if ((nums[i] + nums[left] + nums[right]) > 0) { right--;}
            else {
                result.push_back({nums[left], nums[i], nums[right]});
                while (left < right && nums[left] == nums[left+1]) {left++;}
                while (left < right && nums[right] == nums[right-1]) {right--;}
                left++;
            }
        }
        while (i < length-2 && nums[i] == nums[i+1]) {i++;}
    }
    return result;
}

637. Average of Levels in Binary Tree (Easy)

錄影

模擬面試過程

👨‍💼： Now I want to discuss a question about binary trees, "Average of Levels in Binary Tree" The number of nodes in the tree is in the range [1, 100]. Please follow the definition below for the structure of the binary tree.

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
};

🙋‍♂️： Could the node values be float?
👨‍💼： Let's assume they are integers.
🙋‍♂️： Okey. I want to provide an example to help me understand the question.

🙋‍♂️： In this example, I need to return [3, 14.5, 11]. Did I get it right? Even though the input values are integers, the output values might be float.
👨‍💼： Yes, your understanding is right.
🙋‍♂️： For this question, my initial idea is to use DFS to visit each node and use a table to keep track of the total sum and the number of nodes at each level. Finally, we can calculate the average.

void dfs(TreeNode* root, int level, vector<pair<double, int>>& sum_levels) {
    if (!root) return;
    int k = root->val;

    if (sum_levels.size() <= level) { sum_levels.push_back({k,1}); }
    else{
        sum_levels[level].first += k;
        sum_levels[level].second++;
    }
    dfs(root->left, level+1, sum_levels);
    dfs(root->right, level+1, sum_levels);
}

vector<double> averageOfLevels(TreeNode* root) {
    vector<pair<double, int>> sum_levels;
    vector<double> result;

    dfs(root, 0, sum_levels);

    for (int i=0; i<sum_levels.size(); i++){
        double sum = sum_levels[i].first;
        int num = sum_levels[i].second;
        result.push_back(sum/num);
    }
    return result;
}

🙋‍♂️： Since DFS visits each node only once, the time complexity is

$O(|V|)$, and the space complexity is also

$O(|V|)$ because, for imbalanced trees, the depth of recursion could be equal to the number of nodes.
👨‍💼： It looks good, but in some cases, I might only want to calculate the average for a specific level. With your method, I would still have to traverse the entire tree. Do you have a way to improve this issue?
🙋‍♂️： I want to use BFS to visit each node layer-by-layer and calculate the average for nodes on the same level. This way, we can compute averages in the order we want.

vector<double> averageOfLevels(TreeNode* root) {
    vector<double> result;
    queue<TreeNode*> node_queue;

    node_queue.push(root);

    while (!node_queue.empty()) {
        double sum = 0;
        int size = node_queue.size();
        for (int i=0; i<size; i++) {
            TreeNode* node = node_queue.front(); 
            sum += node->val;
            node_queue.pop();
            if (node->left != NULL) {node_queue.push(node->left);}
            if (node->right != NULL) {node_queue.push(node->right);}
        }
        result.push_back(sum/size);
    }
    return result;
}

🙋‍♂️： The time complexity and space complexity are both

$O(|V|)$. This is because BFS visits each node only once, and in the worst case, all nodes might be stored in the queue.

總體檢討

• 說話太糊，咬字不清楚，需要平常多注意。
• 聲音太小，語氣不夠肯定。
• 對話中太多 "嗯"，要改
• 英語口說要加強

• 針對 interviewer 的檢討

• 可以針對程式碼，進行更多的測試。

• 針對 interviewee 的檢討

• 打程式碼的時候，應該要配合階段性解說，讓 interviewer 更加清楚程式碼的脈絡。
• 會有過長的沉默時間，應蓋要盡量的講出 "預計要做" 或 "正在做" 的事。

---

他評01

• 優點

• 聲音柔和
• 第一題interviewer指出interviewee程式碼的問題並請其改正，有良好的互動性。
• 說明自己的想法後再開始實作。
• interviewee提出問題增進和interviewer的互動性。

• 可改進的地方

• 語氣可以更強這樣感覺起來更有自信。
• 聲音和背景音融合在一起，不容易聽清楚，也許說大聲點或是語氣有抑揚頓挫會更好。
• 那個打字一直出現的「拍噠」聲音聽起來好燥==
• 打程式碼的時候可以邊打邊說明程式碼的用途，不然好安靜。
• 第二題可以不用說出3sum，直接進入情境題。

他評02

Interviewer

• 優點

• 說明題目很清楚
• 英文口說不錯

• 可改進的地方

• 也許一開始就可以說明情境，把完整的題意更清楚的說明。

Interviewee

• 優點

• 在寫程式過程中，思考蠻清楚的。只要配上解釋應該就會好很多
• 寫程式中其實都沒卡頓，我認真覺得蠻厲害的
• 英文口說蠻好的
• 覺得可以再把整個思路講得更清楚一些
• 程式看起來很簡潔明瞭

• 可改進的地方

• 在撰寫程式碼過程中可以邊說明，不然過多留白會蠻尷尬的
• 可以跟面試官討論一下是否可以用C++
• 10:02: 為什麼Erase過後還要重新配置空間呢? C++的erase是真的會把size縮小的吧? 如果我理解錯誤有沒有參考資料plz。 Sundew 這是我的認知。查資料又查到一個很有趣的 這邊小弟去實驗stackoverflow std::remove+vector.erase 的結果
  
• 第二部2:58: 也許講話要大聲一點可能比較清晰? 我自己背景也會有噪音所以是有後製把噪音去掉，看有沒有人有推薦麥克風，可以改善雜音太多的問題，我是用Iphone耳機
• 第三部0:26: 題目上已經給int了 還是意思是return value..

他評03

Interviewer

• 優點

• 提問的時候有指出需要改進的地方。
• 英文口說咬字很清晰。

• 可改進的地方

• 文字可以稍微大一點。
• 提問環節時互動可以再多一點。

Iterviewee

• 優點

• 程式撰寫的時候很流暢。

• 可改進的地方

• 可以在邊撰寫程式邊說明，或是在寫某一行條件時候 (像是 while 的中止條件) 可以先講解後再寫。
• DFS 的時間複雜度，可以說明
  $V$ 的定義是節點數。

他評04

Interviewer

• 優點

• 清楚說明出題目的與可應用的地方
• 面試互動完整

• 可改進的地方

• 可以將題目直接套入情境之中
• 可以多給予點題目的解釋

Iterviewee

• 優點

• 遵循Reacto，與面試官互動良好
• 程式撰寫流暢
• 時間複雜度分析清楚

• 可改進的地方

• 程式撰寫時空白時間太長，宜適當加入註解與說明
• 第三題主體想法是DFS，可以先從這部分先進行撰寫與說明

他評05

interviewer

• 優點

• 有使用情景為什麼需要做這個東西
• 有另外舉一個input測試interviewee

• 可改進之處

• 如果interviewee寫程式走火入魔了完全沒解說，可以主動提出一些問題打破尷尬

interviewee

• 優點

• 有使用例子與interviewer確認自己的理解是否正確
• 有先用較差的時間復雜度再優化

• 可改進之處

• 沉默時間太長，在coding的時候應該伴隨著講解

他評06

interviewer

• 優點

• 舉出實作上可以應用的地方很棒。
• 向interviewee提出問題，交流是否有地方需要改進，互動良好。

• 可改進之處

• 有時候會有一小段字突然糊掉、聽不清楚。
• 第二題不需要特別說題目名稱關鍵字，這樣刷題者馬上就手癢想寫了XD。

interviewee

• 優點

• 對答橋段良好，REACTO完整。

• 可改進之處

• 一邊寫一邊卻沒有說明，建議在撰寫的時候配合說明，可以清楚讓面試主持人知道在幹嘛。
• 承上，配合在各個程式片段下註解，更可以有效傳達自己的想法。