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

# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023/)」課程第 1 次作業 > 貢獻者: 抹茶-Matcha > 模擬面試錄影: [1](https://www.youtube.com/watch?v=mgyhMfmlL-o)、[2](https://www.youtube.com/watch?v=tg1ID5F-dUg)、[3](https://www.youtube.com/watch?v=7XhYtRiK8dc) > > :smiling_imp: interviewer > :smile:: interviewee ## [509. Fibonacci Number](https://leetcode.com/problems/fibonacci-number/) :smiling_imp: 您好, 我是你今天的面試官, 接下來會問你程式問題。請你說出你的想法,並用程式去實作出來。 :smiling_imp: 這題是費波納氣數列，每一個數字都是前兩個數字的加總。當 n 大於 1 時, 就是第 n 個數是由第 n-1, n-2 個數相加。 ...... :smiling_imp: :smile:: 我想理解我是否理解這道問題。這題是要我們 ... :smiling_imp:: 你的理解正確。 :smile: 那我講一下我這題的方法。因為會用到前兩個的結果。我想用 recursive 方式去解。recurson tree 會是這。舉例以 4 來說，...... :smiling_imp:: 好的，看起來沒問題，你可以開始實作了 :smile:: ...... :smiling_imp:: 看起來實作和分析都沒問題。你可不可以在做一些優化。讓時間和空間複雜度在減少一些。也可以用其他方法 :smile:: 我想用 iterative 方式去解。 ...... :smiling_imp:: 看起來沒問題，你可以開始實作了。 :smile:: ...... recursive ```cpp 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 ```cpp 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](https://leetcode.com/problems/maximum-depth-of-binary-tree/) :smiling_imp:: 您好, 我是你今天的面試官, 接下來會問你程式問題。請你說出你的想法,並用程式去實作出來。 :smiling_imp:: 這題是 maximum depth of binary tree。 ...... :smile:: 我想確認我是否理解題目。 :smile:: ...... :smiling_imp:: 你的理解正確 :smile:: 好我想再確認 root 是 nullptr 的時候(edge case) :smiling_imp:: 是的, 如沒有其他問題，你可以說出自己的想法。 :smile:: 這題我想使用 dfs :smile:: ...... :smiling_imp:: 想法沒有問題。可以開始實作了。 :smile:: ....... :smiling_imp:: 但是這題還有其他做法。請你用其他做法實作。 :smile:: 可以用 bfs 解。 (略) :smiling_imp:: 你的想法沒有太大問題，可以實作程式了。 :smile:: ...... dfs ```cpp 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 ```cpp 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](https://leetcode.com/problems/kth-largest-element-in-an-array/) ```cpp 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) ```cpp 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](https://youtu.be/tg1ID5F-dUg?t=140): 避免頻繁搖動滑鼠。 * 215. Kth Largest Element in an Array * Constrains 沒有提及 nums 陣列中的元素大小的範圍。 - [ ] 其他 * 我覺得不應該把整個人碼掉 * 英文那題hackmd沒有文本 ## 第二次作業-他評03 ### interviewer - [ ] 優點 * 說話清晰 - [ ] 可改進的地方 * 不該自稱是「面試官」，這樣會有「上對下」的隱含意思 * 建議將題目包裝成其他應用的場景，避免出現背答案導致鑑別度不足，也可以考驗 interviewee 的理解能力和應變能力 * 可留一點問題讓 interviewee 問，例如說先不講變數限制，看看 interviewee 是否有思考邊界條件 ### interviewee - [ ] 優點 * [2:54](https://youtu.be/mgyhMfmlL-o?si=OuyEpP3gyt2q1jgt&t=174): 有清楚表達解決問題的思路，例如：為什麼會想用遞迴的方法來解 * 主動分析時間和空間複雜度 - [ ] 可改進的地方 * 作答前應該先溝通使用的程式語言 ## 第二次作業-他評04 ### interviewer - [ ] 優點 * 口齒清晰，音量適當 - [ ] 可改進的地方 * interviewer 不應該自稱 interviewer * 不應該使用 LeetCode 原題，可適度變形，鑑別並篩選掉只會刷題目的 interviewee ### interviewee - [ ] 優點 * 口齒清晰，音量適當 * Repeat 及 Example 部分解釋得非常清楚 * 邊寫程式邊做解釋，讓 interviewer 更容易了解你的想法 - [ ] 可改進的地方 * [0:44](https://www.youtube.com/watch?v=7XhYtRiK8dc&t=44): 打錯字 test cast -> test case ## 第二次作業-他評05 ### interviewer - [ ] 優點 * 會引導面試者接下來應該說什麼 - [ ] 可改進的地方 * 題目給得太詳細了，可以把舉例和確認條件的工作給面試者做。 ### interviewee - [ ] 優點 * 舉例與分析很詳細，尤其是把遞迴的內容都寫出來 - [ ] 可改進的地方 * 將 fibonacci 改為 iterative 之後，應該舉例驗證正確性 * 不該自稱面試官 ## 第二次作業-他評06 ### interviewer - [ ] 優點 * 有給interviewee明確的指示，一步一動作。 - [ ] 可改進的地方 * 把題目給的過於明確，可能會導致後續與interviewee沒有更多的討論空間，coding interview淪為線上觀看別人寫LeetCode。 * 或許可以用一些實務場景來對題目進行包裝，也能夠以此延伸討論方向。 ### interviewee - [ ] 優點 * 在畫面的呈現上有經過思考與設計，範例與遞迴的結構都能夠明確的呈現。 - [ ] 可改進的地方 * [08:01](https://youtu.be/tg1ID5F-dUg?si=buE_qKSK6DKlWQbh&t=480):有口誤，應該是空間複雜度。