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

貢獻者: 吳倚攝-ether
R:interviwer E:interviwee

1. two sum

video

測驗說明與問答

R:你好，我是這次負責面試的主要人員，我們這邊有個問題想要提供給你，請你幫我們解決一下。
R:就是呢，我們給你一個矩陣的數字，然後我們再給你一個要加起來的target，然後麻煩你可以從矩陣中array裡面找到兩個數字，是能夠加起來成為我們的目標的。
R:好，那可以先講一下你的想法，然後再接著實做。
E:面試官你好，我叫做吳倚攝，然後我這邊提供一下我一個目前最快想到的一個簡簡單的想法。
E:那就是因用暴力解的方法，然後這個的時間複雜度的話大概是O(

n^{2}

)。
E:我們看一下你提供的例子

E:如果從exmaple 1的話，明顯的目標是9的話，我們就是要抓2和7，所以我最簡單的想法就是用暴力解方法，針對每個元素並檢查他們的總和是否等於目標，然後用for迴圈來完成這件事情。
E:這的話會需要兩個for迴圈。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {}; 
    }
};

E:這是我目前最快想到的想法。
R:我看你的想法不錯，反應蠻快的，那你是否能夠提供一個時間複雜度更低的，或者是說記憶體呃空間複雜度更低的方法呢？
E:哦，好的，嗯，我想一下哦。
E:哦，想到一個就是在c++裡面有一個叫unordered_map的函式，他就是可以存一個key然後跟一個裡面的值。
E:我們就可以利用這個hashtable，我們可以就是真的就是每疊代一次陣列，我們就針對對於每個元素，然後我們檢查Hashtable裡面是否存在著目標減去當前元素的值？
E:如果有的話，那我們找到找到答案了，那如果沒有的話，那我們就把當前的元素存到hashtable裡面。
E:好，那我這邊來實作一下。
E:這樣子的話我們時間複雜度就來到O(n)。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> numMap;
        int n = nums.size();

        for (int i = 0; i < n; i++) {
            int complement = target - nums[i];
            if (numMap.count(complement)) {
                return {numMap[complement], nums[i]};
            }
            numMap[nums[i]] = i;
        }

        return {}; 
    }
};

E:那這是我想到一個更快的方法。
R:你這個實作的想法不錯，而且想到的速度也蠻快的，我還蠻喜歡你的臨場反應以及你的思緒，也覺得你的能力不錯，然後我們回去之後跟其他同仁討論看看，我們今天的會議就先到這邊結束，謝謝。

80. Remove Duplicates from Sorted Array II

video

測驗說明與問答

R:嗨，你好，我是這次面面試的主要負責人，我是資深工程師迪拉。
R:我們會給你一個，我們從下面自己可以看我們會給你一個array然後裡面有數字，裡面有有序的數字，然後呃，麻煩你就是要幫我們移除多餘的數字，然後每一數字只能出現兩次。
R:然後移除完數字之後，你要告訴我們，總共會有幾個總共一除完蟲多餘的數字之後總工會幾個，然後主要呃，然後另外還有一個限制的話，就是這裡的空間複雜度要是O(1)，就是這樣好，你可以開始嘗試，或者是先講講你的想法。
E:然後我這邊的想法的話，就是利用一個迴圈，然後直接去針對每個元素，然後做檢查的話。
呃。
E:然後如果超過兩次的話，就用前面的人數把它蓋掉，這樣的話，我們就不用把額外的，我們就不用需要花到額外的空間，這樣子的話，我們的空間複雜度的話，就會是O(1)。
哦，那我們這邊來實做一下。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i =0;
        // int ele= nums[0];
        for(auto ele : nums)
        {
            if(i==0 || i==1 || nums[i-2] != ele)
            {
                nums[i] = ele;
                i++;
            }
        }
    return i ;
    }
};

R:倚攝，我覺得你的想法很棒，你有實際的推倒之後可以證明你是正確的，然後也符合題目要求，那今天的會議就到這邊，謝謝。

242. Valid Anagram

video

測驗說明與問答

R:Today, I wiil give you one question,need you give me one solution ,as soon as good.
R:Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
R:have two exmaples.you can think how it work.
E:My name is Ether Wu.
E:I think the best solution is time complexity O(n).
E:We need to use hash table.First, I think we can create unordered map count character frequencies. The key of the map represents a character, and the value represents its frequency.
E:Now, we can iterate over each character x in string s. For each character, increment its frequency once.and next,each character x in..
E: we check each character x in string t.For each character, decrement its frequency onec,so we can check the frequency will be 0.
E:so it will be 0, it will be true.one of them not 0 , so it will be false.
E: Let me do it.Let me show you.

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char, int> count;
        
        for (auto x : s) {
            count[x]++;
        }
        
        for (auto x : t) {
            count[x]--;
        }
        
        for (auto x : count) {
            if (x.second != 0) {
                return false;
            }
        }
        
        return true;
    }
};

E:this's all of my think. it will work.
R:I like your ideal.this meeting is over. thank you

總體初步檢討

interviwee

在遠距面試的場合中，通常鏡頭會採正面且不會拍到鍵盤，有效的手勢範圍很窄，不該太依賴手勢，相反的，儘量用 REACTO 步驟的 Example，打字並說出輸入/預期輸出案例的「特性」
對話中舉例的測試資料 (或某一組輸入/預期輸出) 可敲入到指定的作答內文中，如 Google Docs，這樣在用英語解說時 (畢竟不是母語，說越多，錯誤就越多)，可說得少一點
用 Google Docs 撰寫程式碼，會發現程式碼縮排不好顧及，現有影片的程式碼在視覺上過於緊湊。其實書寫程式碼時，不用嚴格依據實際程式碼讀取的順序，反而可寫下「對應到 REACTO 步驟的 Approach 的關鍵程式碼」的函式呼叫、變數指派，或者迴圈主體
打字太慢，要練！
在撰寫程式之餘，可以邊說明此時撰寫的部分為何，避免等待撰寫的時間，場面太過安靜。
對自身答案可以展現多一些自信。
少用助語詞（舉例哪裡說那，啊，啦，之類比較多）
說話的聲量不定，會忽大忽小 (尤其打code時説話會很小聲)
英文文法注意，盡可能表達真正的想法。

interviwer

今天公司安排 interviewer 用上班時間跟 interviewee 互動，是為了「找人做事」，要儘量藉由互動來確認應徵者的能力和溝通方式是否對公司有助益。這裡可改提出 interviewee：「打算要用策略來實作？」「演算法是否需要額外配置空間？」等問題，這些需要基本的論述
關於輸入的數值範圍和行為，都該清楚說明
提問時，避免只拋出「時間複雜度是什麼等級？」這樣的問題，這樣對話欠缺上下文，可能 interviewee 憑藉猜測或背誦做答，從而喪失鑑別度 (注意對話時間，儘量讓問答有效率)，可改為一併要求 interviewee 解釋並簡介對應到現有程式碼該怎麼展現
interviewee 顯然在此處花了很多時間撰寫程式碼，卻看不出思維的特別之處，於是可適度打斷，跟 interviewee 討論可能的實作方式，給予提示，畢竟面試的重點是「認識一個人，包含專業能力及其展現」，適度略過細節，可讓雙向溝通更順暢
可以問一下有關應用場景的問題
舉例時，避免頻繁使用滑鼠游標，在視訊會議中，滑鼠游標的移動可能會落後，甚至某些系統無法正確展現滑鼠游標，可改為選取標注的方式
避免說「有幾個問題要你回答」，可改說「由於敝公司的產品開發中，不免會用到若干經典演算法，同仁想知道你的想法，因此我嘗試彙整過去的開發經驗，提出一兩個問題，請你稍候討論並在 Google Docs 撰寫程式碼」

第二次作業-他評01

關於interviewer

優點

說話清楚。

可改進的地方

對 interviewee 幾乎沒有回饋。
適時變更題目限制。
針對 Test 和 Optimize 的部分可以進一步詢問。

關於interviewee

優點

說話清楚。

可改進的地方

沒有討論 function 名稱、參數、參數範圍、回傳值。
變數、保留字是有區分大小寫的，可以關閉 word 英文字首大寫。
縮排須加強。
沒有完整討論每題的空間、時間複雜度。
寫程式前可多舉幾個例子。
可將思考方向用註解方式寫在程式上。
要向 interviewer 確認想法是否正確，再寫程式。
沒有用範例確認程式正確性。

第二次作業-他評02:

Interviewer

優點

口條清晰，語速正常
5:32: 有做引導至Interviewer想知道的方向

可改進的地方

00:04,11:01: 講話的時候一直晃會讓人覺得很不受尊重
沒有給Interviewee實際的一些反饋

Interviewee

優點

口條清晰，語速正常

可改進的地方

4:16: 此處的解釋其實算是你要採取的approach，可以在coding前就可以先說明，這樣會比較符合REACTO中，A到C的過程
缺乏Repeat的步驟
缺乏Examples的步驟
缺乏Test的步驟

第二次作業-他評03

interviewer

優點

講話清楚
有對interviewee的整體表現做出反饋

interviewee

優點

講話清楚
程式碼清晰

可改進之處

interviewee可以先說明想採取的方案，再討論時間複雜度
coding時可以帶入更多講解
整體有點缺乏溝通

第二次作業-他評04

interviewer

優點

講話清楚

interviewee

優點

講解演算法清晰易懂

可改進部分

缺少REACTO中的repeat
word有自動大寫的問題，可以換其他文書軟體
撰寫程式時可以多解釋程式內容
1:20: 「用前面的元素把它蓋掉」應該是「用後面的元素把前面的蓋掉」
1:55: character 發音不對

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

1. two sum

測驗說明與問答

80. Remove Duplicates from Sorted Array II

測驗說明與問答

242. Valid Anagram

測驗說明與問答

總體初步檢討

interviwee

interviwer

第二次作業-他評01

關於interviewer

關於interviewee

第二次作業-他評02:

Interviewer

Interviewee

第二次作業-他評03

interviewer

interviewee

第二次作業-他評04

interviewer

interviewee

Read more

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

從 √2 的存在談開平方根的快速運算

案例探討: Ring buffer

Linux 核心設計: Timer 及其管理機制