Try   HackMD

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

貢獻者: 輝瑞-BNT
video

REACTO

  1. Repeat problem -> 順便理解題目
  2. Examples -> 解釋範例測資
  3. Approach -> 講大概的解法
  4. Coding -> 開始解題
  5. Testing -> 將測資代入上一步驟的實做
  6. Optimize -> 討論優化可能

Two Sum

題目要求: 給定一個陣列和 target,要找出哪兩個 element 的總和可以剛好為 target

EX1:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Solution

思路: 因為題目說一定會有解,所以我們只需要迭代 nums,檢查是否經過元素 target - nums

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

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

題目要求: 檢查由 ('(', '{', '[', ')', '}', ']') 組成的字串是否合法,除了要成對,順序也要對

EX1:

Input: s = "([)]"
Output: false

Solution

思路: 用 stack 來紀錄成對的狀況

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

題目要求: 在陣列 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。

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, customize pq comparator

更好的方法 (bucket sort)

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 這裡提到說延伸 2-SUM 解法的複雜度會是
    O(n2)
    ,並解釋不使用這方法的原因是因為無法在
    O(n2)
    解決答案重複的問題。這邊應該可以解釋得更清楚些,因為如果將每一組答案正規化後置入 hashset 就可以解決這問題。真正的問題是在於 2-SUM 的
    O(n)
    解法是建立於該問題只須回傳一組解的前提下。若改為回傳所有解,其複雜度為
    O((n2))=O(n2)
    ,所以延伸的 3-SUM 解會是
    O(n3)

第三次作業-他評3

interviewer

優點

  • 0:06 實作第一題時,沒有直接說明題目名稱,而是講解完題目要求後舉例說明,方便interviewee快速進入狀況
  • 23:06 coding完成後和interviewee討論程式碼,真的有在互動

interviewee

優點

  • 1:51 12:54 用註解標示那段程式碼用意,讓他人能很快找到重點
  • 7:24 17:19 撰寫程式之前,先列舉程式預期會達到的目標
  • 10:36 很有邏輯的撰寫程式,並詳細說明每段程式碼用意

缺點

  • 23:28 花了將近一分鐘在驗證每段程式的時間複雜度,未來時間可能要稍微分配一下

第三次作業-他評4

面試過程檢討

總體

  • 人物分類薄弱,比較難看出Interviewer跟Interviewee的差別,且口吻上也比較無差異性
  • 口語表達較為薄弱,聽起來有點缺乏自信
  • 依照課堂需求應該使用如Google document來增加撰寫程式碼的困難度。
  • InterviwerInterviewee 比較缺乏攻防與問答。
  • 是不是應該要有三題才對,但是只有兩題。

Interviewer

  • 題目講解快速,沒有浪費過多時間舉例而浪費面試時間。
  • 直接說『你的答案看起來是對』不太精確,且像是在敷衍。
  • 講到延伸問題 3Sum 的時候,可以說仔細一點input 資料的型態,例如:有沒有重複值?;是否有排序過?;資料的大小等等。

Interviewee

  • 解題概念清楚,能很快讓人知道意思。但也有可能讓人認為是在死背。
  • 4:14 講到為了避免編譯器報錯所以最後要回傳,可能可以講仔細一點為什麼要這樣?
  • 時間複雜度的部分可以在講的仔細一點,例如說明比較跟暴力法的差別。
  • 7:15講到沒有辦法在 n 平方的複雜度就解決所以要新的方法,聽起來有點不合邏輯,可以在說明清楚。
  • 有一些口頭禪可以稍微改進(或是可以剪接剪掉)例如:像這樣,對
  • 講解 3Sum 的實作還有條件判斷很清楚,一聽就懂。

第三次作業-他評5

總體

  • 應使用 Google doc 或者文字編輯器(e.g. Vim、NotePad++)來增加程式碼撰寫的困難度。
  • 沒有回答 Valid Parantheses,我猜是忘了回答。

Interviewer

  • 題目講解快速,沒有用過多時間舉例而浪費面試時間。
  • 3Sum 部分,我覺得 input 資料型態要說明正多細節,例如:是否有重複值?是否有排序過?input 資料長度等等。
  • 直接說「你的答案看起來是對的」有夠敷衍。

Interviewee

  • 解題概念相當清楚,而且在跟 Interviewer 講解時的描述能力不錯(特別是 3Sum 部分)。
  • 講解解題概念同時開始打程式碼,節省時間之外,也讓 Interviewer 可以同時了解 Interviewee 的想法。
  • 4:02提到為了避免編譯器出現 compile error 所以要回傳 一個空的 vector,需要說明為什麼要這麼做。
  • 7:15提到用 O(n^2) 複雜度效率很低,所以需要換一個思路,我認為需要說明清楚。

第三次作業-他評6

Interviewer

0:21 避免直接將 LeetCode 的題目「英翻中」
4:14 沒有針對「防止他編譯錯誤」這句話進行提問
5:13 未對 unordered_map find 函式執行時間複雜度為

O(1) 的說法要求進一步的解釋
16:34 在 interviewee 寫完程式碼後,沒有針對其中的部分進行更進一步的討論或總結

19:09 可以要針對 unordered_map 元素的初始值進行詢問
23:15 「很明顯的你時間就是有慢到」這句話雖然很口語化,但是並不精準,可能會讓 interviewee 覺得你不專業

Interviewee

1:42 沒有完整講述自己的 approach 就開始寫程式碼,會讓 interviewer 有誤會背題目的可能性
4:26 盡量以手動驗證的方式,避免過於依賴手邊編輯環境的功能來檢視程式碼的正確性
6:23 實際情況應該不會有「如題目名字」一樣的思路可以參考,應避免使用這樣的詞彙來描述解題手法
16:31 在沒有檢查邊界條件的前提下,僅透過執行預設的 Test Case 就宣稱程式碼「看起來沒有問題」

17:20 沒有進行 REACTO 中的 "R" 以及 "E" 的步驟
17:22 可以進一步詢問 interviewer 輸入陣列中的數值範圍,如果數值範圍不大,不使用 map 就可以實作


第三次作業-他評7

Interviewer

  • 第一題two sum未告知interviewee題目有唯一解的限制
  • 23:12"有慢到" 太口語了

Interviewee

  • 有邊coding邊講解,Great。
  • 沒有詢問interviewer關於唯一解的問題,感覺像是背起來題目
  • 沒有Repeat interviewer的問題
  • 講解時都沒有舉例子
  • "看起來"、"應該" 口頭禪需要改掉
  • 4:58 這裡不只有access,還有hash map的搜尋時間
  • 6:21 不需要附和覺得這題是延伸題
  • 31:00
    O(n)
    O(klogn)
    好是從何得知的,應該說明一下。 若稍微代換一下
    O(n)
    =
    O(log2n)
    ,則
    2n
    如何與
    nk
    比較

第三次作業-他評8

Interviewer

  • 可以盡量避免直接拿leetcode頁面進行面試,它所提供的參數也許會限制住面試者的想法。
  • 第一題延伸題interviewee實作完成後,可以再多提出一些問題或是評論。
  • 第二題說到: 時間有慢到,口語化但在面試的過程中應該可以換個說法

Interviewee

  • 想法很清楚,也有邊coding邊說明想法
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
  • 第一題有講說為了要避免編譯器會報錯所以最後還是要回傳,可以的話盡量再多說明一點為什麼
  • 第一題延伸題,對於 為什麼沒辦法在O(N^2)的複雜度有效的判斷答案是否重複 的想法可以再多解釋。
  • 第二題自己也說有點慢,那最好可以說明一下是因為在coding時用到什麼東西所導致。

整體

  • 應對interviewer和interviewee做更仔細的分類,服裝、鏡頭、語氣皆一致。
  • 第一題有唯一解的限制,interviewer未說出、interviewee也沒有問到這個問題。

第三次作業-他評 9

整體

在打字與講解上的時間掌握得當,若在講解的過程加入更多的例子會更好

Interviewer

  • LeetCode 1 - Two Sum
    • 建議的點:
      1:37 這邊看到 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 將此題較難的題目與上一題較簡單的題目做連結(不過跳出時間複雜度是 n^2 這邊太快了,可以加一下回圈怎麼跑搭配 2sum 的時間複雜度後,推得為 n^2)。另外,能在一開始就想到如何針對 “重複的答案” 有解答且提出想法
    • 建議的點:
      13:00 這邊在講解避開重複的數值時,因為 while 裡頭又包 while,若 interviewer 這邊沒跟上的話,很難直接從 code 得知你的想法,建議能加個簡單例子輔以說明
      13:42 這邊有點怪XD先寫了第二個條件之後才回去寫第一個條件,這樣感覺不太自然(的確應該也演練蠻多次的),覺得這邊就是講到什麼就加什麼條件即可
  • LeetCode 347 - Top K Frequent Elements
    • 優點:
      能夠提出兩個版本,第二個版本針對第一個版本的缺點再去改進
    • 建議的點:
      24:06 這邊講 “priority queue 的 push 就是 logn” 應該還可以再講多一些(額外提到像是 heapify),或許會更好唷。另外,後面有用到 k 以及 n 來講解,口頭上有講到分別代表什麼意思,不過這邊自己也是回放回去聽才記起來,或許可以在註解後面補上 k=map size 之類的,會更清楚
      25:28 ~ 26:01 這段完全 get 不到想表達的內容(可能慧根不夠),可能對你來說是消化後用很精簡的方式講出,但是以聽的角度來說(至少我自己)是聽不太懂改用 bucket 能帶來的效益,這邊如果要講解的話就蠻需要例子來輔助了~

第三次作業-他評 10

interviewee 優點

  • 程式碼熟練

interviewee 可改進的地方

  • 解釋自己的做法時,不要只用講的,可以用寫一些註解來闡釋做法或是寫一些例子(REACTO),讓面試官可以更好更快的理解。
  • 解題的過程中,盡量不要突然不說話,把所想的事情給說出來,可以講一些更細節的事情。
  • 如果一開始就沒有想要打中文,輸入法可以一開始就調成全英文。
  • 9:19 對於 i 程式碼盡量放入初始化值,雖然程式會幫你歸0,和這不是一個好習慣。
  • 在闡述作法時,可以多一點多元的思考,即使知道最 Optimized 的解法,可以先講一些基礎解法,再提出最 Optimized 的解法,這樣看起來比較不像是在被題目。

interviewer 優點

  • 題目講解清楚

interviewer 可改進的地方

  • 關鍵台詞有點多
    ​​​​這樣看起來是對的
    ​​​​請解釋一下演算法的時間複雜度
    
  • 用 leetcode 寫,然後用 leetcode run code 來判斷程式碼對不對有點奇怪,白板題主要是在看想法,而不是程式碼完全的正確性。
  • 可以加入一些 follow up ,來讓整個測驗更有鑑別度。
  • 可以請 interviewee 帶入一些例子來討論,尤其是 special cases

第三次作業-他評 11

interviewee

00:10 建議使用google doc,leetcode 太好用了
01:00 可以一邊舉例一邊簡單打數字或方法,讓 interviewer 更清楚,只用聽的較難完全理解你的意思
01:38 應該先跟 interviewer 討論方法和 corner case,討論佔大部分時間,程式碼實作佔少部分
04:16 Interviewee 應該用自己的舉例去看程式對不對,面試沒有測資可以跑
18:28 interviewee 應避免用 “可能”、“類似” 等用語

interviewer
00:25 建議應該是 interviewee 來舉例,interviewer 講解題目就好
16:59 應由 interviewee 自己舉例
23:23 可以直接問有沒有其他改進方法
24:10 可以再追問為什麼 push 的 time complexity = O(logn)