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

# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1 > 瑞比-Rabbit > :man_in_tuxedo: : interviewer > :rabbit: : interviewee > > [模擬面試錄影(漢)](https://www.youtube.com/watch?v=8QrihLMbbxE) > [模擬面試錄影(漢)](https://www.youtube.com/watch?v=LMiuK6xIDN4) > [模擬面試錄影(英)](https://youtu.be/xAjuPWqfqGU) ## [104. Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/description/) > [錄影](https://www.youtube.com/watch?v=8QrihLMbbxE) ### 模擬面試過程 :man_in_tuxedo: : 你好，那現在開始我們的面試題目，給你一個Binary Tree，請回傳它的最大深度是多少。 :rabbit: : 我想確認我有沒有理解錯這個題目，如果用這個範例解釋的話，我要回傳的值就是從根節點3到離3最遠的節點15或7的距離，也就最大深度3，最後就是回傳這個數值，這樣我的理解有錯嗎? ![](https://hackmd.io/_uploads/H1Aqj1U16.png) :man_in_tuxedo: : 對你的理解是對的，請繼續你的解釋。 :rabbit: : 好，如果我的理解沒有錯的話，我想可以用遞迴的方式來解決這個問題。詳細方法是找到一個node，得到這個node的left child和right child的maximum depth，並取得這兩個數值中的最大值+1，就會是這個node的maximum depth。以上面的example來說，要得到20這個node的maximum depth，就是取15跟7的maxamum depth的最大值，也就是1，再加上1得到2，就是20這個node的maximum depth。再透過遞迴就可以歷遍整個Binary Tree，就可以得到這個Binary Tree的maximum depth了。 :rabbit: :實際的程式碼如下 ### Recursive ```cpp int maxDepth(TreeNode* root){ int maxLeft = maxDepth(root->left); int maxRight = maxDepth(root->right); return max(maxLeft, maxRight) + 1; } ``` :man_in_tuxedo: : 好，這程式基本上沒什麼問題，但它還不夠完整，如果要新增一行它更完整的話，你會怎麼做。 :rabbit: : 對，這樣我還缺一個判斷式，如果這個node是空的話要return0。 ### Complete Solution ```cpp int maxDepth(TreeNode* root){ if(!root) return 0; int maxLeft = maxDepth(root->left); int maxRight = maxDepth(root->right); return max(maxLeft, maxRight) + 1; } ``` :man_in_tuxedo: : 好，那我想問一下這個程式的時間複雜度跟空間複雜度是多少? :rabbit: : 時間複雜度是總結點的個數，因為它要用回來歷遍所有的節點。空間複雜度因為是recursive stack，所以是level的個數。 :man_in_tuxedo:: 好那今天的面試就到這裡，謝謝。 ### 初步檢討針對interviewer的檢討: * 在一開始講解題目的時候可以講一個example，讓interviewee更好了解題目。 * 可以再和interviewee有更多互動。針對interviewee的檢討: * 在寫程式的時候，說話音量可以再大聲自信一點。 * 減少語助詞(e.g., 恩) * 講解時間複雜度和空間複雜度時要用 $O(n)$，不要只是陳述個數。 * 在寫完第一版的程式後就要發現自己程式不夠完整。 ---- ## [199. Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/description/) > [錄影](https://www.youtube.com/watch?v=LMiuK6xIDN4) ### 模擬面試過程 :man_in_tuxedo: : 嗨你好，這次的題目是給你一個Binary Tree，你要想想你站在這個Binary Tree的右邊，我要你return從上到下順序的節點的數值。 :rabbit: : 我想確認一下我的想法是不是對的，我用exmaple來解釋，假設我站在這個Binary Tree的右邊的話，我要return的順序會是[1, 3, 4] 這樣理解是對的嗎? ![](https://hackmd.io/_uploads/SkXS-vSkT.png) :man_in_tuxedo: : 對你這個方向是對的，請繼續。 :rabbit: : 這個方向如果是對的話，我會用level order traversal 去歷遍整個Binary Tree。先寫一個array (ans)，來存我要返回的數值，也就是每一個level的最右邊節點的值，再創一個array (lot)來存訪問過的節點的value和level，再寫兩個迴圈並判斷現在的節點是不是在每個level的最右邊，是的話就加到叫ans的array裡，最後再return這個array(ans)的值，就會得到答案。 :man_in_tuxedo: :你的想法是對的，可以開始寫程式了。 ```cpp vector<int>rightSideView(TreeNode *root){ vector<int> ans; vector<pair<int, int>> lot; if(root == nullptr) return ans; queue<pair<TreeNode *, int>> q; q,push({root, 0}); while(!q.emy()){ TreeNode *current = q.front().first; int level = q.front().second; q.pop(); lot.push_back({current->val, level}); if(current->left) q.push({current->left, level + 1}); if(current->right) q.push({current->right, level + 1}); } for(int i = 0; i < lot.size()-1; i++){ if(lot[i].second != lot[i+1].second){ ans.push_back(lot[i].first); } } ans.push_back(lot[lot.size()-1].first); return ans; } ``` :man_in_tuxedo: : 好，那我們今天的面試就到這邊，謝謝。 ### 初步檢討針對interviewer的檢討: * 在解釋題目時可以搭配一個example讓interviewee更好的了解題目的問題。 * 在interviewee講解完解題概念之後，可以再更深入的和interviewee的討論實際的做法。針對interviewee的檢討: * 一開始在確定使否有理解題目錯誤時，應避免說，"我想確認這樣是不是對的"，而應該用 "我對題目的理解是..."。 * 因為這題在解釋概念上比較複雜，所以可以在講解時搭配打字在google document上，幫助interviewer更加了解這個解釋跟想法。 * 在打程式碼的時候要檢查是否有打錯的情況，像是變數名稱跟函式名稱、括號跟;有沒有少打。 * 因面試有時間限制，可以再增加自己的打字速度。 * 在邊打程式邊解說的時候，解釋的音量可以再大聲一點。 ## [136. Single Number](https://leetcode.com/problems/single-number/) > [錄影](https://youtu.be/xAjuPWqfqGU) ### 模擬面試過程 :man_in_tuxedo: : Hello, today's question is given a non-empty array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with a linear runtime complexity and use only constant extra space. :rabbit: : Ok, I have to make sure I've correctly understand of this question. If I've been given a array = [2,1,1], output=2 If I've been given a array = [4,2,1,2,1], output=4 ```cpp Input: nums = [2,1,1] Output: 2 Input: nums = [4,2,1,2,1] Output: 4 ``` :man_in_tuxedo: : Yes, you're on the right track. You can explain your solution. :rabbit: : For sovling this problem, first come into my mind is using maps, I'll map the given array's elements to their frequency, and traverse that map and return the key whose value is 1. :man_in_tuxedo: : OK, you can try. :rabbit: : So the code is like this. ### Maps ```cpp int singleNumber(vector<int>& nums){ unordered_map<int, int> a; for(auto x: nums) a[x]++; for(auto z:a) if(z.second==1) return z.first; return -1; } ``` :man_in_tuxedo: : OK, but this method uses variable extra space, so it's not gonna be our answer. If I ask you to use sorting, can you do so? :rabbit: : To use sorting, I'll first sort the array. And traverse that array and check if the current element is equal to its adjacent element. If not,I'll return the current element's value. ### Sorting ```cpp int singleNumber(vector<int>& nums){ sort(nums.begin(), nums.end()); for(int i=1; i<nums.size();i+=2){ if(nums[i] != nums[i-1]) return nums[i-1]; } return nums[nums.size()-1]; } ``` :man_in_tuxedo: : This solution might be the answer. But what if I want to improve the time complexity and I don't want to use sorting, can you come up with another method? :rabbit: : I'll use bitwise XOR operator, To imply this solution, I have to traverse the array and take the bitwise XOR of each element and then return the value. ### Bitwise XOR Operator ```cpp int singleNumber(vector<int>& nums){ int ans=0; for(auto x:nums) ans^=x; return ans; } ``` :man_in_tuxedo: : OK, so it's the interview for today, thank you. ### 初步檢討針對interviewer: * 在解釋題目的時候語速要放慢且咬字清晰，並舉例讓interviewee更好了解題目。 * 在知道interviewee的方法錯時，就應該讓他想其他方法，而不是打完程式後才說他這樣不對。 * 在一開始說話時不要一直說"Ok" 針對interviewee: * 在打字時可以加大說話音量，讓面試官更理解你在說什麼 * 英語表達要再更順暢一點 * 打字速度要加快，畢竟面試時間有限 --- ## 第二次作業-他評01 ### 關於interviewer - [ ] 可改進的地方 * [0:05](https://youtu.be/8QrihLMbbxE?si=YTcN3GooTBXPDpOG&t=5): 說"直接開始面試題目" 會讓人覺得今天是來考試的，建議可以改成"公司請我來了解你/妳的情況並協助你/妳更認識公司" * [0:08](https://youtu.be/8QrihLMbbxE?si=8yZf0DonMYiL0ksC&t=8): 如果是經典的題目，可能會需要包裝成另一情境，否則會出現背答案導致鑑別度不足，也可以考驗interviewee的理解能力和應變能力 * [1:33](https://youtu.be/8QrihLMbbxE?si=yGgjG9_fQkvr82Je&t=93): 當interviee 講完自己的做法時，interviewer 應給予適當的討論或提出一些可能會出錯的情況，而不是讓interviwee自顧自地開始寫code * [3:29](https://youtu.be/8QrihLMbbxE?si=MXYUMmL8bD2WjpCd&t=209): interviewer說:"這個程式不完整"，但沒有提出哪裡不完整，要是interviewee不知道自己哪裡漏寫，自然無法做出修改，建議interviewer可以用例子去讓interviewee帶入，使他自己發現哪裡有缺漏。 * [12:13](https://youtu.be/LMiuK6xIDN4?si=H67PAJLMC6kIbvEu&t=733): 在interviewee完成程式後，建議可以進行討論及改進，或是用實際example test過，若是寫完程式就結束會更像是程式設計的上機考。 * [4:38](https://youtu.be/xAjuPWqfqGU?si=D04gRENL8S_WRPbK&t=278): interviwer 應該可以在interviewee 解釋方法時就可以發現用了variable extra space，可以即時與interviewee討論 * [8:10](https://youtu.be/xAjuPWqfqGU?si=vxElwQYYr3N7kXkU&t=490): 建議可以與intervievee討論過時間複雜度再請他改進，否則也不確定對方是否會分析時間複雜度 ### 關於interviewee - [ ] 優點 * 邊寫code邊講解的很清楚 * 闡述解法的時候很清楚 * 有合適的肢體語言顯得不死板 - [ ] 可改進的地方 * [1:30](https://youtu.be/8QrihLMbbxE?si=1v2yQ3O4ZO6OP_nj&t=90): 建議可以停頓觀察interviewer的反應，也許對方會提出質疑或是不同的看法 * [1:10](https://youtu.be/LMiuK6xIDN4?si=0lsf97HqdBAKbirT&t=70): 建議interviewee 應當也向interviewer確認題目的條件，來確認所謂的constraint ## 第二次作業-他評02 ### 關於interviewer - [ ] 優點 * 說話清楚、聲音穩定。 * 英文通順。 - [ ] 可改進的地方 * 適時變更題目限制，以 Maximum Depth of Binary Tree 為例，可以改變節點數量或是用非遞迴的方式等等。 * 對 interviewee 的回饋偏少。 * 針對 Test 和 Optimize 的部分可以進一步詢問。 ### 關於interviewee - [ ] 優點 * 說話清楚、聲音穩定。 * 英文通順。 - [ ] 可改進的地方 * 寫程式前可以多舉幾個例子。 * 需要測試寫出來的程式。 * 要詢問題目限制，像是參數和回傳值的型態、範圍。 * Maximum Depth of Binary Tree * 需要詢問節點數量，節點數量會影響程式的實作 (e.g., 適不適合遞迴...) 和回傳值。 * Binary Tree Right Side View * 有錯字和縮排問題 * 單從字面上不容易知道 lot 這個變數的功能。 * 沒有提及時間和空間複雜度。 * 如果利用一個 level 的節點數量，即 queue 的 size，就可以知道該 level 的最後一個節點，而不需要用到 lot array。 ## 第二次作業-他評03 ### 關於 interviewer - [ ] 優點 * 語速正常，聲音清晰 * 會適時給予提示，並且與interviewee討論問題的改進方法，讓他去做嘗試 - [ ] 可改進的地方 * [3:20](https://youtu.be/8QrihLMbbxE?t=200): 可以不用說一行要加甚麼，或許可以請他先檢查看看是不是哪裡有問題，讓他自己先找看看，或是可以說你的遞迴中止條件並不完整等更明確的提示 ### 關於 interviewee - [ ] 優點 * 語速正常，聲音清晰 * 在寫code時，會不時講解現在寫到哪邊，或是說明方法，蠻不錯的 - [ ] 可改進的地方 * 未確實執行REACTO的Test部分，需再注意 * 再述說時間複雜度時，建議還是要講 Big O 等級會比較好 * [8:08](https://youtu.be/xAjuPWqfqGU?t=488): 能跟interviewer互動，進一步探討改進方法很好，但後面未經提示反而直接想出更優解，看起來有點奇怪

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.