Try   HackMD

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

貢獻者: 抹茶-Matcha
模擬面試錄影: 123

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 →
interviewer
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 →
: interviewee

509. Fibonacci Number

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

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

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

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

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(nlogn)
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(nlogk)
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

  • 優點
  • 聲音穩定。
  • 詢問並根據題目敘述舉出例子。
  • 有說明時間複雜度。
  • 邊打字邊講解。
  • 有將思考方向先當作註解寫在程式上。
  • 可改進的地方
  • 字型可以放大,例如將瀏覽器設定為全螢幕。
    1. Fibonacci Number
    • iteration 的程式可以用例子跑一遍。
    1. Maximum Depth of Binary Tree
    • 2:20: 避免頻繁搖動滑鼠。
    1. 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:有口誤,應該是空間複雜度。