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

貢獻者: 抹茶-Matcha
模擬面試錄影: 1、2、3

interviewer
: interviewee

509. Fibonacci Number

您好, 我是你今天的面試官, 接下來會問你程式問題。請你說出你的想法,並用程式去實作出來。
這題是費波納氣數列，每一個數字都是前兩個數字的加總。當 n 大於 1 時, 就是第 n 個數 是由 第 n-1, n-2 個數相加。 …

: 我想理解我是否理解這道問題。這題是要我們 …
: 你的理解正確。
那我講一下我這題的方法。因為會用到前兩個的結果。我想用 recursive 方式去解。recurson tree 會是這。舉例以 4 來說，…
: 好的，看起來沒問題，你可以開始實作了
: …
: 看起來實作和分析都沒問題。你可不可以在做一些優化。讓時間和空間複雜度在減少一些。也可以用其他方法
: 我想用 iterative 方式去解。 …
: 看起來沒問題，你可以開始實作了。
: …

recursive

int fib(int n){
    if(n <= 1)
        return n;
    else
        return fib(n-1) + fib(n-2);
}

time complexity: O(2^n)
space complexity: O(n)

iterative

int fib(int n){
    if(n <= 1)
        return n;
    int a = 0, b = 1;
    for(int i = 2; i<=n; i++){
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

time complexity: O(n)
space complexity: O(1)

104. Maximum Depth of Binary Tree

: 您好, 我是你今天的面試官, 接下來會問你程式問題。請你說出你的想法,並用程式去實作出來。
: 這題是 maximum depth of binary tree。 …
: 我想確認我是否理解題目。
: …
: 你的理解正確
: 好我想再確認 root 是 nullptr 的時候(edge case)
: 是的, 如沒有其他問題，你可以說出自己的想法。
: 這題我想使用 dfs
: …
: 想法沒有問題。可以開始實作了。
: …
: 但是這題還有其他做法。請你用其他做法實作。
: 可以用 bfs 解。 (略)
: 你的想法沒有太大問題，可以實作程式了。
: …

dfs

int maxDepth(TreeNode* root) {
    if(!root)
        return 0;
    int maxL = maxDepth(root->left);
    int maxR = maxDepth(root->right);
    return 1 + max(maxL, maxR);
}

time complexity: O(n)
space complexity: O(d), d: depth

bfs

int maxDepth(TreeNode* root) {
    if(!root) return 0;
    queue<TreeNode*> q({root});
    int level = 0;
    while(!q.empty()){
        level++;
        for(int i = q.size()-1; i>=0; i--){
            TreeNode* cur = q.front();
            q.pop();
            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
        }
    }
    return level;
}

time complexity: O(n)
space complexity: O(n)

215. Kth Largest Element in an Array

int findKthLargest(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    return nums[nums.size() - k];
}

time complexity:

$O(n\log n)$
space complexity: O(1)

int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for(auto& i:nums){
        pq.push(i);
        if(pq.size() > k)
            pq.pop();
    }
    return pq.top();
}

time complexity:

$O(n\log k)$
space complexity: O(k)

初步檢討

• 英文面試不夠流利
• 實做完程式沒有用 test case 去驗證

---

第二次作業-他評01:

interviewer

• 優點：

• 口齒凡清晰的，interviewee也是

• 可改進：

• 可以開頭自我介紹名字，後面interviewee可以用名字稱呼interviewer
• MaxDepth那題我覺得interviewer題目給得太清楚太明確，這樣會比較難看出interviewee的反應，其他題目也都有該情形
• interviewer應該多給interviewee一些展現的機會，例如以引導式的方式來讓interviewee回答

interviewee

• 優點：

• REACTO都有做到，讚👍
• 程式碼解釋清楚
• 有解釋自己所使用的演算法
• 撰寫程式時臨場感佳，有些部分寫到一半回去修改剛剛寫完的部分，比較不像是scripted的

• 可改進：

• 挑的題目都蠻制式化的，可以挑一些實際應用佳的，或是把題目轉化成實際場景
• 英文那題Kth Largest Element in an Array，題目本身就是一個sort問題了，不應該使用到C++ stl的sort來解，主要是interviewer應該提前告訴interviewee不要用到std:sort()或是看到interviewee使用sort作法做完後，interviewer要告知interviewee使用別的做法

第二次作業-他評02

關於interviewer

• 優點

• 聲音穩定。
• 有說明題目。

• 可改進的地方

• 對 interviewee 的回饋偏少。
• 適時變更題目限制。
• 針對 Test 的部分可以進一步詢問。

關於interviewee

• 優點

• 聲音穩定。
• 詢問並根據題目敘述舉出例子。
• 有說明時間複雜度。
• 邊打字邊講解。
• 有將思考方向先當作註解寫在程式上。

• 可改進的地方

• 字型可以放大，例如將瀏覽器設定為全螢幕。
• 509. Fibonacci Number
  • iteration 的程式可以用例子跑一遍。
• 104. Maximum Depth of Binary Tree
  • 2:20: 避免頻繁搖動滑鼠。
• 215. Kth Largest Element in an Array
  • Constrains 沒有提及 nums 陣列中的元素大小的範圍。

• 其他

• 我覺得不應該把整個人碼掉
• 英文那題hackmd沒有文本

第二次作業-他評03

interviewer

• 優點

• 說話清晰

• 可改進的地方

• 不該自稱是「面試官」，這樣會有「上對下」的隱含意思
• 建議將題目包裝成其他應用的場景，避免出現背答案導致鑑別度不足，也可以考驗 interviewee 的理解能力和應變能力
• 可留一點問題讓 interviewee 問，例如說先不講變數限制，看看 interviewee 是否有思考邊界條件

interviewee

• 優點

• 2:54: 有清楚表達解決問題的思路，例如：為什麼會想用遞迴的方法來解
• 主動分析時間和空間複雜度

• 可改進的地方

• 作答前應該先溝通使用的程式語言

第二次作業-他評04

interviewer

• 優點

• 口齒清晰，音量適當

• 可改進的地方

• interviewer 不應該自稱 interviewer
• 不應該使用 LeetCode 原題，可適度變形，鑑別並篩選掉只會刷題目的 interviewee

interviewee

• 優點

• 口齒清晰，音量適當
• Repeat 及 Example 部分解釋得非常清楚
• 邊寫程式邊做解釋，讓 interviewer 更容易了解你的想法

• 可改進的地方

• 0:44: 打錯字 test cast -> test case

第二次作業-他評05

interviewer

• 優點

• 會引導面試者接下來應該說什麼

• 可改進的地方

• 題目給得太詳細了，可以把舉例和確認條件的工作給面試者做。

interviewee

• 優點

• 舉例與分析很詳細，尤其是把遞迴的內容都寫出來

• 可改進的地方

• 將 fibonacci 改為 iterative 之後，應該舉例驗證正確性
• 不該自稱面試官

第二次作業-他評06

interviewer

• 優點

• 有給interviewee明確的指示，一步一動作。

• 可改進的地方

• 把題目給的過於明確，可能會導致後續與interviewee沒有更多的討論空間，coding interview淪為線上觀看別人寫LeetCode。
• 或許可以用一些實務場景來對題目進行包裝，也能夠以此延伸討論方向。

interviewee

• 優點

• 在畫面的呈現上有經過思考與設計，範例與遞迴的結構都能夠明確的呈現。

• 可改進的地方

• 08:01:有口誤，應該是空間複雜度。