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

--- title: info2023-homework1 tags: 資訊科技產業專案設計2023 --- # 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1 > 中文名稱：梅治玄 > English name: Marlin > 🧔：interviewer > 👶：interviewee > [模擬面試錄影兩題(漢)](https://youtu.be/e26UBgzbv3A) > [模擬面試錄影一題(英)](https://youtu.be/_MDo9wR-2hI) ## [1. 2sum](https://leetcode.com/problems/two-sum/) ### 模擬面試過程 🧔: 好，我先來口頭敘述一下題目，這題簡單來說是想要您選出一維陣列裡面的兩個數字的加總相等於函式輸入中要求的數值。輸出的陣列則是輸入的一維陣列的兩個index值。 👶: 我先整理一下思緒，如果輸入的一維陣列沒有函數想要的數值，輸出預計是？ 🧔: 因為沒有匹配的項目，輸出預計是空陣列。 👶: 我有看到一個例子，如果陣列裡的兩個數字一樣，輸出是 [0, 1] 或是 [1, 0] 都是合法的嗎？ 🧔: 是可以的，事實上就算數字不一樣，最後的輸出只要有抓對就可以。你看example 1的輸出是 [0, 1] ，但是輸出成 [1, 0] 也可以。 👶: 謝謝，我如果要寫這題，首先想到的是使用兩個迴圈寫這題，第一個迴圈裡面會先抓輸入的陣列的第一個元素，接著第二個迴圈會再抓除了第一個迴圈以外的元素進行加總，接著再比對加總的值，最後輸出該兩個元素的index值，如果都沒有的話會輸出空的陣列。 🧔: 聽起來不錯，可以實作看看嗎？ 👶: 可以。 ### 暴力解法（兩個迴圈） ```cpp class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int numlength = nums.size(); for(int i=0;i<numlength-1;i++){ for(int j=i+1;j<numlength; j++){ if((nums[i] + nums[j]) == target) return {i, j}; } } return {}; } }; ``` 🧔: 不錯，如果以您的寫法，時間複雜度應該是？ 👶: 應該會是 $O(N^2)$。 🧔: 是的，但是這樣的話雖然從電腦效能上來說空間複雜度是 $O(1)$，時間複雜度卻是 $O(N^2)$。請問您有其他方式來達到時間複雜度是 $O(N)$ 嗎？ 👶: 這樣可能需要使用到一些工具，如果以雜湊表來配合的話，因為雜湊表搜尋元素只要 $O(1)$ 的時間複雜度，再配合一次的一維陣列檢索 $O(N)$，最後這題的時間複雜度就會進步到 $O(N)$。 ### 利用 unordered_map<k, v> 查找索引值 ```cpp class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { // O(n^2) -> O(n) hash table: search O(1) unordered_map<int, int> umap; // complement = target - num[i] // example: <11, 0> <2, 1> <7, 2> <15, 3> for(int i=0;i<nums.size();i++){ int complement = target - nums[i]; if(umap.count(complement)) return {umap[complement], i}; umap.insert(pair<int, int>(nums[i], i)); } return {}; } }; } ``` 👶：這樣時間複雜度是 $O(N)$，同時空間複雜度也會從 $O(1)$ 到 $O(N)$。 ### 初步檢討針對 interviewer 的檢討: * 待定針對 interviewee 的檢討: * 待定 ### 同儕檢討針對 interviewer 的檢討 * 待定針對 interviewee 的檢討 * 待定 --- ## [102. Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/) ### 模擬面試過程 🧔: 好，這題我就先來口頭敘述一下題目Binary Tree Level Order Traversal，首先，題目這邊會有一個輸入root，而這個root代表著這棵二元樹的根節點，並且預計的輸出會是一個二維的陣列。而這個二維的陣列就包含著這棵樹的值。並且這些值會依照此二元樹的層級依序排列。 👶: 依照我的理解，這一題的輸入是這棵樹的根節點，而不是一個一維陣列? 🧔: 是的，是這棵樹的根結點。 👶: 我有一個疑惑，輸入的一維陣列，他的表示方式看起來像是能用Preorder的方式顯示？ 🧔: 不是，這題的範例其實出的不好，可能對你而言有些誤解，但是他的規則是，輸入的一維陣列都會輸出每一層的節點，即使是空節點也會以Null的方式呈現。例如3是根結點第一層、9, 20是第二層、null, null, 15, 7是第三層。把他們連接在一起就會變成題目輸入的一維陣列。 👶: 那麼輸出的地方不會包含NULL對吧？遇到NULL應該要把它給忽略，而且輸出的二維陣列，會先從根結點開始表示，接著再表示第二層節點、再表示第三層… 依此類推。 🧔: 是的。 👶: 那我舉一些例子，如果輸入換成 [1, 2, 3, 4, 5, 6, 7]，輸出應該會是 [[1], [2, 3], [4, 5, 6, 7]]？ 🧔: 對。 👶: 如果輸入換成 [1, null, 3, null, null, null, 5]，輸出應該是 [[1], [3], [5]] 對嗎？ 🧔: 不對，如果您想輸出這樣的結果，輸入陣列應該為 [1, null, 3, null, 5]，要注意NULL是代表著空節點。 👶: 我的想法是，先使用一維的vector先把包含根結點在內的每一層節點的值存起來，然後再把該一維的vector儲存到二維的vector裡面，所以應該需要一個迴圈去重複做這件事情。 🧔: 聽起來是個合理的方式，那如何從上層的節點得知下層的節點呢？ 👶: 每個節點都有其左右子節點的指標。 🧔: 但您剛剛是說用vector儲存值對吧？也就是節點的整數值，但是依照您的邏輯來講，無法直接透過vector來得知TreeNode的結構內容。 👶: 那可能需要額外透過某種容器來儲存這些必要資訊。 🧔: 沒錯，我認為這部分您需要注意。 ```cpp /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { // make a result vector<vector<int>> result; // if root is NULL pointer, return empty 2-dimen vector if(root == nullptr) return {}; //ld vector: [3] -> [9, 20] -> [15, 7] //vector<int> layer; queue<TreeNode*> q; // queue: // 1d vector layer: 15, 7 q.push(root); while(!q.empty()){ vector<int> layer; int q_size = q.size(); for(int i=0;i<q_size;i++){ TreeNode* current_node = q.front(); q.pop(); if(current_node->left != nullptr) q.push(current_node->left); if(current_node->right != nullptr) q.push(current_node->right); layer.push_back(current_node->val); } result.push_back(layer); } return result; } }; */ ``` ### 初步檢討針對 interviewer 的檢討: * 待定針對 interviewee 的檢討: * 待定 ### 同儕檢討 * 待定 --- ## [9. Palindrome Number](https://leetcode.com/problems/palindrome-number/) ### 模擬面試過程 🧔: Great. I explain this coding question. The theme is palindrome. So you need to write the function which return value is Boolean. The input value is integer. If the input x is a palindrome, returns true. Otherwise, returns false. 👶: Okay. As for as I know, the input value must be integer. It seems to return false when I enter any negative integer into this function. 🧔: According to the question, it’s correct. 👶: If I enter 123321 into this function, it will return true, right? 🧔: Yes. 👶: It’s not limited to odd-digit numbers, even-digit numbers is also possible as long as it meets the requirement. 🧔: Yes. 👶: Great. Here is my opinion. If x is less than zero, return false. I create an array to contain each number of x. And then I reverse it. If the reversed number is same to the original one, the function returns true. Otherwise, it returns false. 🧔: Good. It sounds feasible. 👶: Let me start to implement. ### 使用 vector ```cpp class Solution { public: bool isPalindrome(int x) { if(x < 0) return false; vector<int> numbers; // this loop separate the digits numbers x while(x > 0){ numbers.push_back(x-x/10*10); x /= 10; } // compare the every digits to ensure x is palindrome number int reverse = numbers.size(); for(int i = 0;i < numbers.size()/2; i++){ if(numbers[i] != numbers[reverse - 1]) return false; reverse--; } return true; } }; ``` 🧔: The result seems to be correct. 🧔: But I think you can simplify your code. It wastes memory space in computer. Some parts can be improved. 👶: … Sorry, can you give me a tip? 🧔: Sure. You use a vector to save each number of digits in elements. Right? Maybe you don’t need it. 👶: Thanks! let me try it. ### Digit by Digit ```cpp class Solution { public: bool isPalindrome(int x) { if(x < 0) return false; long long reverse = 0; int temp = x; // extract the last digit of number using % and store it to digit variable while(temp != 0){ int digit = temp % 10; reverse = reverse*10 + digit; temp /= 10; } if(x == reverse) return true; else return false; } }; ``` 👶: I forgot to say I use long long data type in reverse variable. Because I want to handle potential overflow in case of large input number. 🧔: Good. The answer is no problem. That’s all. Thanks for participating this interview. ### 初步檢討針對 interviewer 的檢討: * 待定針對 interviewee 的檢討: * 待定 ## 第二次作業 - 他評02 **interviewer** 優點 - 咬字清楚 - 有與面試者確認是否有看到畫面可改進處 - 建議不要直接使用 Leetcode 作為面試的畫面，容易讓面試者可以直接背誦題目。 - 建議可以增加與面試者的互動： - 討論是否存在更加解法。例如：[18:50](https://youtu.be/_MDo9wR-2hI?si=znoz-67JmarzFo2Y&t=1130) `long long` 是否有只使用 `int` 的可能 - 將題目做變形 **interviewee** 優點 - 明確的敘述思考邏輯，且在寫的過程中同時也有解釋程式。 - 清楚的與面試官溝通題意，確定雙方理解沒有落差。可改進處 - 建議舉例的時候可以將範例寫在螢幕上，方便雙方進行溝通。其他建議 - 建議把面試者與面試官兩者的音量調整至相同大小 ## 第二次作業-他評03 ### Interviewer - [ ] 優點 * 咬字清晰、說明得很清楚。 * 問題都詢問的蠻好的，可以讓 interviewee 更深入去思考問題，讓整個 interview 更能看到 interviewee 的程度。 * 對於要問的問題有很確定的認知，回覆 interveiwee 的問題能很確定的回答需求。 ### Interviewee - [ ] 優點 * 有邊實作邊說明程式邏輯，挺好的。 * 做之前先利用一些例子確認問題和邊緣條件。 - [ ] 可改進之處 * 建議使用共編文件進行面試，而非直接開leetcode ide。 ## 第二次作業 - 他評02 ### interviewer 優點 - 講話語氣很堅定 - 在test方面有直接給一個例子來驗正 - 和面試者互動蠻多的可改進處 - 建議不要直接使用 Leetcode 作為面試的畫面，容易讓面試者可以直接背誦題目。 - 建議可以增加與面試者的互動： - 討論是否存在更加解法。例如：[18:50](https://youtu.be/_MDo9wR-2hI?si=znoz-67JmarzFo2Y&t=1130) `long long` 是否有只使用 `int` 的可能 - 將題目做變形 ### interviewee 優點 - 明確的敘述思考邏輯，且在寫的過程中同時也有解釋程式。 - 清楚的與面試官溝通題意，確定雙方理解沒有落差。 - 在test方面有直接給一個例子來驗正 - 講話語氣很堅定可改進處 - 建議舉例的時候可以將範例寫在螢幕上，方便雙方進行溝通。其他建議 - 建議把面試者與面試官兩者的音量調整至相同大 ## 第二次作業 - 他評03 ### interviewer 優點 - 對問題的描述清晰 - 在討論題目的過程中與interviewee互動良好可改進處 - 可以用情境包裝題目避免直接使用leetcode原題（甚至是leetcode介面） ### interviewee 優點 - 對題目的提問很關鍵可改進處 - [0:40](https://youtu.be/e26UBgzbv3A?t=40)把「整理一下思緒」改成「確認一下題目」會顯得較專業其他建議 - 馬賽克有點跑掉 ## 第四次作業-他評04 ### Interviewer - [ ] 優點 * 慢慢引導面試者優化code，不會讓人有太大壓力。 - [ ] 可改進之處 * [0:50](https://youtu.be/e26UBgzbv3A?t=50): 在面試時，手機聲音應該要關掉。 * [20:00](https://youtu.be/e26UBgzbv3A?t=1200): 提問時盡量不要使用leetcode原題目問，也不要讓面試者開leetcode答題，容易有背答案的嫌疑。 * [0:02](https://youtu.be/_MDo9wR-2hI?t=2): 馬賽克沒有打好，直接看到你是誰了。 ### Interviewee - [ ] 優點 * [10:12](https://youtu.be/e26UBgzbv3A?t=612): 有邊講解邊打code，清晰易懂。 - [ ] 可改進之處 * [1:33](https://youtu.be/e26UBgzbv3A?t=93): 字幕有時會打錯字，加"總"。 * [2:12](https://youtu.be/e26UBgzbv3A?t=132): 打code時建議在另外的空白文件或文字編輯器上打比較合適，通常不會在leetcode上打。 * [5:52](https://youtu.be/e26UBgzbv3A?t=352): 用官網跑程式他會告訴你錯誤在哪裡，這步驟應該是要由面試官來告訴面試者。