2021 年資訊科技產業專案設計課程面試範例

--- title: 2021 年資訊科技產業專案設計課程面試範例 tags: INFO2021 --- # 2021 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2021)」面試範例 > 貢獻者: 輝瑞-BNT > ==[video](https://youtu.be/O2llOMQ4m44)== ## REACTO 1. Repeat problem -> 順便理解題目 2. Examples -> 解釋範例測資 3. Approach -> 講大概的解法 4. Coding -> 開始解題 5. Testing -> 將測資代入上一步驟的實做 6. Optimize -> 討論優化可能 ## Two Sum [題目](https://leetcode.com/problems/two-sum/)要求: 給定一個陣列和 `target`，要找出哪兩個 element 的總和可以剛好為 `target` EX1: ``` Input: nums = [3,2,4], target = 6 Output: [1,2] ``` ### Solution 思路: 因為題目說一定會有解，所以我們只需要迭代 `nums`，檢查是否經過元素 `target` - `nums` ```cpp class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> mp; for(int i = 0; i < nums.size(); i++){ if(mp.find(target - nums[i]) != mp.end()){ return {mp[target - nums[i]], i}; } mp[nums[i]] = i; } return {}; } }; ``` ### Complexity 因為 hash 操作為 $O(1)$，而需要遍歷長度為 n 的陣列，所以時間複雜度為 $O(n)$ 缺失: * 忘記在寫程式前，於 code block 內用稍後將實做的方法來試跑測資 (方便面試官理解我方法的運作流程) ### 延伸題 3Sum Problem [link](https://leetcode.com/problems/3sum/submissions/) ```cpp class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> res; sort(nums.begin(), nums.end()); for(int i = 0; i < nums.size(); i++){ int target = -nums[i]; int second = i + 1; int third = nums.size() - 1; while(second < third){ if(nums[second] + nums[third] > target){ third--; }else if(nums[second] + nums[third] < target){ second++; }else{ res.push_back({nums[i], nums[second], nums[third]}); int a = nums[second], b = nums[third]; while(second < third && nums[second] == a){ second++; } while(second < third && nums[third] == b){ third--; } } } while(i < nums.size() - 1 && nums[i] == nums[i + 1]){ i++; } } return res; } }; ``` ## Valid Parentheses [題目](https://leetcode.com/problems/valid-parentheses/)要求: 檢查由 ('(', '{', '[', ')', '}', ']') 組成的字串是否合法，除了要成對，順序也要對 EX1: ``` Input: s = "([)]" Output: false ``` ### Solution 思路: 用 stack 來紀錄成對的狀況 ```cpp class Solution { public: bool isValid(string str) { stack<char> s; for(int i = 0; i < str.size(); i++){ if(s.empty()){ s.push(str[i]); continue; } if(str[i] == ')' && s.top() != '(') return false; if(str[i] == '}' && s.top() != '{') return false; if(str[i] == ']' && s.top() != '[') return false; if(str[i] == ')' || str[i] == '}' || str[i] == ']') s.pop(); else s.push(str[i]); } return !s.empty() ? false : true; } }; ``` ### Complexity 因為 stack 的 pop 和 push 都是 $O(1)$，所以本題的時間複雜度為 $O(n)$ ## Medium: Top K Frequent Elements [題目](https://leetcode.com/problems/top-k-frequent-elements/)要求: 在陣列 `nums` 中找出最頻繁出現的 k 的元素 EX1: ``` Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] ``` ### Solution 思路: 透過 hash map 紀錄不同 elements 出現的頻率，接著透過 priority queue 來排序，並取出 top K 的 node。 ```cpp class Compare { public: bool operator() (vector<int> a, vector<int> b) { return a[1] < b[1]; } }; class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { vector<int> res; unordered_map<int, int> mp; // (times, number) priority_queue<vector<int>, vector<vector<int>>, Compare> pq; for(int i = 0; i < nums.size(); i++){ mp[nums[i]]++; } for(auto &it: mp){ pq.push({it.first, it.second}); } while(k-- > 0){ res.push_back(pq.top()[0]); pq.pop(); } return res; } }; ``` ### Complexity 1. time complexity of insertion: $O(logN)$ 2. iterate at most N times 所以解法的時間複雜度為 $O(NlogN)$ reference: [priority queue](https://www.cnblogs.com/Deribs4/p/5657746.html), [customize pq comparator](https://stackoverflow.com/questions/16111337/declaring-a-priority-queue-in-c-with-a-custom-comparator) ### 更好的方法 (bucket sort) ```cpp class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { vector<int> res; unordered_map<int, int> mp; vector<vector<int>> bucket(nums.size() + 1); for(int i = 0; i < nums.size(); i++){ mp[nums[i]]++; } for(auto &it : mp){ bucket[it.second].push_back(it.first); } for(int i = bucket.size() - 1; i >= 0 && k != 0; i--){ for(int j = 0; j < bucket[i].size(); j++){ res.push_back(bucket[i][j]); k--; if(k == 0) break; } } return res; } }; ``` ## 第三次作業-他評 * 建議使用 Google Docs，減少工具輔助以應對各式情況 * 說明解法前應向 interviewer 確認題目內容 * 編寫前應增加範例說明及演示 * 編寫程式碼時都有使用打字來輔助說明 ## 第三次作業-他評2 * [6:48](https://youtu.be/O2llOMQ4m44?t=408) 這裡提到說延伸 2-SUM 解法的複雜度會是 $O(n^2)$，並解釋不使用這方法的原因是因為無法在$O(n^2)$解決答案重複的問題。這邊應該可以解釋得更清楚些，因為如果將每一組答案正規化後置入 hashset 就可以解決這問題。真正的問題是在於 2-SUM 的 $O(n)$ 解法是建立於該問題只須回傳一組解的前提下。若改為回傳所有解，其複雜度為 $O(\binom n2) = O(n^2)$，所以延伸的 3-SUM 解會是 $O(n^3)$。 ## 第三次作業-他評3 ### interviewer 優點 - [0:06](https://youtu.be/O2llOMQ4m44?t=6) 實作第一題時，沒有直接說明題目名稱，而是講解完題目要求後舉例說明，方便interviewee快速進入狀況 - [23:06](https://youtu.be/O2llOMQ4m44?t=1386) coding完成後和interviewee討論程式碼，真的有在互動 ### interviewee 優點 - [1:51](https://youtu.be/O2llOMQ4m44?t=111) [12:54](https://youtu.be/O2llOMQ4m44?t=774) 用註解標示那段程式碼用意，讓他人能很快找到重點 - [7:24](https://youtu.be/O2llOMQ4m44?t=444) [17:19](https://youtu.be/O2llOMQ4m44?t=1039) 撰寫程式之前，先列舉程式預期會達到的目標 - [10:36](https://youtu.be/O2llOMQ4m44?t=636) 很有邏輯的撰寫程式，並詳細說明每段程式碼用意缺點 - [23:28](https://youtu.be/O2llOMQ4m44?t=1408) 花了將近一分鐘在驗證每段程式的時間複雜度，未來時間可能要稍微分配一下 ## 第三次作業-他評4 ### 面試過程檢討 #### **總體** * 人物分類薄弱，比較難看出Interviewer跟Interviewee的差別，且口吻上也比較無差異性 * 口語表達較為薄弱，聽起來有點缺乏自信 * 依照課堂需求應該使用如Google document來增加撰寫程式碼的困難度。 * **Interviwer** 跟 **Interviewee** 比較缺乏攻防與問答。 * 是不是應該要有三題才對，但是只有兩題。 #### **Interviewer** * 題目講解快速，沒有浪費過多時間舉例而浪費面試時間。 * 直接說『你的答案看起來是對』不太精確，且像是在敷衍。 * 講到延伸問題 **3Sum** 的時候，可以說仔細一點**input** 資料的型態，例如：有沒有重複值？;是否有排序過？;資料的大小等等。 #### **Interviewee** * 解題概念清楚，能很快讓人知道意思。但也有可能讓人認為是在死背。 * [4:14](https://www.youtube.com/watch?v=O2llOMQ4m44&t=254) 講到為了避免編譯器報錯所以最後要回傳，可能可以講仔細一點為什麼要這樣？ * 時間複雜度的部分可以在講的仔細一點，例如說明比較跟暴力法的差別。 * [7:15](https://www.youtube.com/watch?v=O2llOMQ4m44&t=435)講到沒有辦法在 **n** 平方的複雜度就解決所以要新的方法，聽起來有點不合邏輯，可以在說明清楚。 * 有一些口頭禪可以稍微改進（或是可以剪接剪掉）例如：像這樣，對 * 講解 **3Sum** 的實作還有條件判斷很清楚，一聽就懂。 --- ## 第三次作業-他評5 ### 總體 * 應使用 Google doc 或者文字編輯器（e.g. Vim、NotePad++）來增加程式碼撰寫的困難度。 * 沒有回答 Valid Parantheses，我猜是忘了回答。 ### Interviewer * 題目講解快速，沒有用過多時間舉例而浪費面試時間。 * **3Sum** 部分，我覺得 **input** 資料型態要說明正多細節，例如：是否有重複值？是否有排序過？**input** 資料長度等等。 * 直接說「你的答案看起來是對的」有夠敷衍。 ### Interviewee * 解題概念相當清楚，而且在跟 Interviewer 講解時的描述能力不錯（特別是 **3Sum** 部分）。 * 講解解題概念同時開始打程式碼，節省時間之外，也讓 Interviewer 可以同時了解 Interviewee 的想法。 * [4:02](https://youtu.be/O2llOMQ4m44?t=242)提到為了避免編譯器出現 compile error 所以要回傳一個空的 `vector`，需要說明為什麼要這麼做。 * [7:15](https://www.youtube.com/watch?v=O2llOMQ4m44&t=435)提到用 O(n^2) 複雜度效率很低，所以需要換一個思路，我認為需要說明清楚。 --- ## 第三次作業-他評6 ### Interviewer [0:21](https://youtu.be/O2llOMQ4m44?t=21) 避免直接將 LeetCode 的題目「英翻中」 [4:14](https://youtu.be/O2llOMQ4m44?t=254) 沒有針對「防止他編譯錯誤」這句話進行提問 [5:13](https://youtu.be/O2llOMQ4m44?t=313) 未對 unordered_map find 函式執行時間複雜度為 $O(1)$ 的說法要求進一步的解釋 [16:34](https://youtu.be/O2llOMQ4m44?t=994) 在 interviewee 寫完程式碼後，沒有針對其中的部分進行更進一步的討論或總結 [19:09](https://youtu.be/O2llOMQ4m44?t=1149) 可以要針對 unordered_map 元素的初始值進行詢問 [23:15](https://youtu.be/O2llOMQ4m44?t=1395) 「很明顯的你時間就是有慢到」這句話雖然很口語化，但是並不精準，可能會讓 interviewee 覺得你不專業 ### Interviewee [1:42](https://youtu.be/O2llOMQ4m44?t=102) 沒有完整講述自己的 approach 就開始寫程式碼，會讓 interviewer 有誤會背題目的可能性 [4:26](https://youtu.be/O2llOMQ4m44?t=266) 盡量以手動驗證的方式，避免過於依賴手邊編輯環境的功能來檢視程式碼的正確性 [6:23](https://youtu.be/O2llOMQ4m44?t=383) 實際情況應該不會有「如題目名字」一樣的思路可以參考，應避免使用這樣的詞彙來描述解題手法 [16:31](https://youtu.be/O2llOMQ4m44?t=991) 在沒有檢查邊界條件的前提下，僅透過執行預設的 Test Case 就宣稱程式碼「看起來沒有問題」 [17:20](https://youtu.be/O2llOMQ4m44?t=1040) 沒有進行 REACTO 中的 "R" 以及 "E" 的步驟 [17:22](https://youtu.be/O2llOMQ4m44?t=1042) 可以進一步詢問 interviewer 輸入陣列中的數值範圍，如果數值範圍不大，不使用 map 就可以實作 --- ## 第三次作業-他評7 ### Interviewer * 第一題two sum未告知interviewee題目有唯一解的限制 * [23:12](https://youtu.be/O2llOMQ4m44?t=1392)"有慢到" 太口語了 ### Interviewee * 有邊coding邊講解，Great。 * 沒有詢問interviewer關於唯一解的問題，感覺像是背起來題目 * 沒有Repeat interviewer的問題 * 講解時都沒有舉例子 * "看起來"、"應該" 口頭禪需要改掉 * [4:58](https://youtu.be/O2llOMQ4m44?t=298) 這裡不只有access，還有hash map的搜尋時間 * [6:21](https://youtu.be/O2llOMQ4m44?t=381) 不需要附和覺得這題是延伸題 * [31:00](https://youtu.be/O2llOMQ4m44?t=1860) 說$O(n)$ 比 $O(klogn)$ 好是從何得知的，應該說明一下。若稍微代換一下 $O(n)$ = $O(log2^n)$，則$2^n$如何與$n^k$比較 --- ## 第三次作業-他評8 ### Interviewer * 可以盡量避免直接拿leetcode頁面進行面試，它所提供的參數也許會限制住面試者的想法。 * 第一題延伸題interviewee實作完成後，可以再多提出一些問題或是評論。 * 第二題說到: 時間有慢到，口語化但在面試的過程中應該可以換個說法 ### Interviewee * 想法很清楚，也有邊coding邊說明想法:+1: * 第一題有講說為了要避免編譯器會報錯所以最後還是要回傳，可以的話盡量再多說明一點為什麼 * 第一題延伸題，對於為什麼沒辦法在O(N^2)的複雜度有效的判斷答案是否重複的想法可以再多解釋。 * 第二題自己也說有點慢，那最好可以說明一下是因為在coding時用到什麼東西所導致。 ### 整體 * 應對interviewer和interviewee做更仔細的分類，服裝、鏡頭、語氣皆一致。 * 第一題有唯一解的限制，interviewer未說出、interviewee也沒有問到這個問題。 ---- ## 第三次作業-他評 9 ### 整體在打字與講解上的時間掌握得當，若在講解的過程加入更多的例子會更好 ### Interviewer - **LeetCode 1 - Two Sum** - 建議的點： [1:37](https://www.youtube.com/watch?v=O2llOMQ4m44&t=1m37) 這邊看到 interviewee 開始使用 `unordered_map` 的時候，或許可以問說是否可以先不使用這個 container 來完成原本這題目，而不使用 container 完成題目的時間複雜度為何這樣 - **LeetCode 15 - Three Sum** - 優點：接續上一題來問延伸題 - **LeetCode 347 - Top K Frequent Elements** - 建議的點：覺得可以在 interviewee 寫 code 的過程中去問（不過就要做更多剪接了），不然在呈現上很像是讓 interviewee 都先把 code 寫完之後，再開始問剛剛寫了什麼，在過程中或許可以加入更多的討論（為何不那樣寫？多了一個限制的話目前的 code 要怎麼改？） ### Interviewee - **LeetCode 1 - Two Sum** - 優點：講解過程清楚，也使用到了 container 來完成題目 - 建議的點：若在使用 `unordered_map` container 前，主動的粗略講一次不用到該 container 要怎麼做，時間複雜度為何，或許會更好唷。這邊可能會直覺使用 brute-force 方法用 2 個 for 迴圈找，但因為這樣太慢了，所以可以改成 binary search 的方法找，這樣的延伸都可以使得在回覆上的內容更豐富唷 - **LeetCode 15 - Three Sum** - 優點： [6:42](https://www.youtube.com/watch?v=O2llOMQ4m44&t=6m42) 將此題較難的題目與上一題較簡單的題目做連結（不過跳出時間複雜度是 `n^2` 這邊太快了，可以加一下回圈怎麼跑搭配 2sum 的時間複雜度後，推得為 `n^2`）。另外，能在一開始就想到如何針對 “重複的答案” 有解答且提出想法 - 建議的點： [13:00](https://www.youtube.com/watch?v=O2llOMQ4m44&t=13m) 這邊在講解避開重複的數值時，因為 `while` 裡頭又包 `while`，若 interviewer 這邊沒跟上的話，很難直接從 code 得知你的想法，建議能加個簡單例子輔以說明 [13:42](https://www.youtube.com/watch?v=O2llOMQ4m44&t=13m42s) 這邊有點怪ＸＤ先寫了第二個條件之後才回去寫第一個條件，這樣感覺不太自然（的確應該也演練蠻多次的），覺得這邊就是講到什麼就加什麼條件即可 - **LeetCode 347 - Top K Frequent Elements** - 優點：能夠提出兩個版本，第二個版本針對第一個版本的缺點再去改進 - 建議的點： [24:06](https://www.youtube.com/watch?v=O2llOMQ4m44&t=24m06s) 這邊講 “priority queue 的 push 就是 logn” 應該還可以再講多一些（額外提到像是 heapify），或許會更好唷。另外，後面有用到 `k` 以及 `n` 來講解，口頭上有講到分別代表什麼意思，不過這邊自己也是回放回去聽才記起來，或許可以在註解後面補上 k=map size 之類的，會更清楚 [25:28](https://www.youtube.com/watch?v=O2llOMQ4m44&t=25m28s) ~ [26:01](https://www.youtube.com/watch?v=O2llOMQ4m44&t=26m01s) 這段完全 get 不到想表達的內容（可能慧根不夠），可能對你來說是消化後用很精簡的方式講出，但是以聽的角度來說（至少我自己）是聽不太懂改用 bucket 能帶來的效益，這邊如果要講解的話就蠻需要例子來輔助了～ ## 第三次作業-他評 10 ### interviewee 優點 * 程式碼熟練 ### interviewee 可改進的地方 * 解釋自己的做法時，不要只用講的，可以用寫一些註解來闡釋做法或是寫一些例子(R**E**ACTO)，讓面試官可以更好更快的理解。 * 解題的過程中，盡量不要突然不說話，把所想的事情給說出來，可以講一些更細節的事情。 * 如果一開始就沒有想要打中文，輸入法可以一開始就調成全英文。 * [9:19](https://youtu.be/O2llOMQ4m44) 對於 `i` 程式碼盡量放入初始化值，雖然程式會幫你歸0，和這不是一個好習慣。 * 在闡述作法時，可以多一點多元的思考，即使知道最 Optimized 的解法，可以先講一些基礎解法，再提出最 Optimized 的解法，這樣看起來比較不像是在被題目。 ### interviewer 優點 * 題目講解清楚 ### interviewer 可改進的地方 * 關鍵台詞有點多 ``` 這樣看起來是對的請解釋一下演算法的時間複雜度 ``` * 用 leetcode 寫，然後用 leetcode run code 來判斷程式碼對不對有點奇怪，白板題主要是在看想法，而不是程式碼完全的正確性。 * 可以加入一些 follow up ，來讓整個測驗更有鑑別度。 * 可以請 interviewee 帶入一些例子來討論，尤其是 special cases ## 第三次作業-他評 11 ## interviewee [00:10](https://youtu.be/O2llOMQ4m44?t=10s) 建議使用google doc，leetcode 太好用了 [01:00](https://youtu.be/O2llOMQ4m44?t=60s) 可以一邊舉例一邊簡單打數字或方法，讓 interviewer 更清楚，只用聽的較難完全理解你的意思 [01:38](https://youtu.be/O2llOMQ4m44?t=98s) 應該先跟 interviewer 討論方法和 corner case，討論佔大部分時間，程式碼實作佔少部分 [04:16](https://youtu.be/O2llOMQ4m44?t=256s) Interviewee 應該用自己的舉例去看程式對不對，面試沒有測資可以跑 [18：28](https://youtu.be/O2llOMQ4m44?t=1108s) interviewee 應避免用 “可能”、“類似” 等用語 interviewer [00:25](https://youtu.be/O2llOMQ4m44?t=25s) 建議應該是 interviewee 來舉例，interviewer 講解題目就好 [16:59](https://youtu.be/O2llOMQ4m44?t=1019s) 應由 interviewee 自己舉例 [23:23](https://youtu.be/O2llOMQ4m44?t=1403s) 可以直接問有沒有其他改進方法 [24:10](https://youtu.be/O2llOMQ4m44?t=1450s) 可以再追問為什麼 push 的 time complexity = O(logn)