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

# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1 > 貢獻者: 鋒美食-Tastii > 🗿：interviewer > 🤓：interviewee > > [錄影: 漢](https://www.youtube.com/watch?v=xFwtjJACvY8) > [錄影: 英](https://www.youtube.com/watch?v=NFMn4lkJpes) ## [268. Missing Number](https://leetcode.com/problems/missing-number/) (剛開始面試的各種介紹) 🗿：接下來請你在Link中的Google Docs幫我解答以下問題 🗿：題目會給你一個陣列nums，陣列中會有n個不同的整數，範圍為0到n，找出這陣列中由0到n唯一缺失的整數 🤓：所以根據我對題目的理解，陣列的大小為n，陣列中的元素不重複，陣列中元素範圍是0到n，要找出缺失的整數。 🤓：舉例來說，假設陣列為nums = [0,3,2]，陣列大小為3,陣列元素範圍為0到3，所以唯一遺失的整數為1，這樣理解應該是正確的。 🗿：沒錯，如果可以請你直接在Google Docs上coding出你的解決方法。 (thinking...) 🤓：首先想到最直覺的方法是先找出陣列大小n為多少 🤓：接下來把陣列排序，使用quick sort 🤓：最後用一個for loop找出缺失值 ```cpp int missingNumber(vector<int>& nums) { int n = nums.size(); sort(nums.begin(), nums.end()); for(int i = 0 ; i < n ; i++){ if(i != nums.at(i)){ return i; } } return nums.size(); } ``` 🗿：了解，做的不錯，這方法非常直覺也正確，但請問能不能想一個更降低時間複雜度的方法 🤓：直覺的解法最花時間的是在sort上，會有O(nlogn)的時間複雜度 🤓：如果可以避開sort那就有機會提升到O(n) (thinking...) 🤓：我想到了，可以用很簡單的數學，因為題目要找出0到n的整數中唯一缺失的整數，只需用數列級數找出0~n的總和減去題目nums內的數字總和，就可找出缺失值 ```cpp int missingNumber(vector<int>& nums) { int sum = 0; int n = nums.size(); int total = (n*(n+1))/2; for (int i = 0, number = nums[0]; i < n ; ++i) { sum += nums[i]; } return total - sum; ``` 🤓：這樣的時間複雜度即可達到O(n) 🗿：好 ## [94. Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/) 🗿：好的，那接下來我們進行到第二個問題，我會發下一個Link給你，作答形式和上一個問題相同 (processing...) 🗿：題目意思很簡單，tree的問題，題目給你一棵二元樹的root，請你用inorder traversal中續走訪將整個樹給print出來 🤓：根據我的了解，inorder traversal是先從最左子點先印出，之後是此子點的root，最後在印出此root的右子點 🤓：之後recursively往上面做 🤓：舉例來說(畫出例圖) ![](https://hackmd.io/_uploads/SyKgxOKyp.png) 🤓：走訪順並印出序為 [4,2,5,1,3] 🗿：OK，你的理解沒有問題，接下來一樣幫我在document上code出來 🤓：最開始想到的方法是用Recursion的方法 🤓：首先我先宣告一個簡單binary tree結構 **TreeNode** struct ```cpp struct TreeNode{ int val; struct tree *left; struct tree *right; } ``` 🤓：先設定終止條件，當無法在繼續往下走訪時return; 🤓：接下來是遞迴式，先inorder遞迴走訪左子樹，之後印出(此為存入ans vector)value，然後再inorder遞迴走訪右子樹 ```cpp void inorder(TreeNode* root, vector<int> &ans){ if(root == NULL){ return; } inorder(root -> left,ans); ans.push_back(root -> val); inorder(root -> right,ans); } vector<int> inorderTraversal(TreeNode* root) { vector<int> ans; inorder(root,ans); return ans; } ``` 🤓：此方法的Time complexity是O(n)，因為會走訪每一個node後它放入array中 🗿：很好，沒什麼問題，那請問還有沒有除了Recursive之外的方法呢？ 🤓：大部分遞迴都可以轉換帶迭代的形式，而這裡也不例外 🤓：所以想到可以用iterative的方法進行，需要搭配一個stack使用 🤓：先從root開始不斷的往左子樹走下去，然後要將經過的node都存入stack中 🤓：直到不能在繼續往下後代表抵達leftmost node，將此node pop 🤓：接著是pop此node的parent，並以此作為root，往右子樹走訪，後由不斷的往左子樹走下去這邊開始重複做 ```cpp vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> usage; vector<int> ans; while(root != NULL || !usage.empty()){ while(root != NULL){ usage.push(root); root = root -> left; } root = usage.top(); usage.pop(); ans.push_back(root->val); root = root -> right; } return ans; } } ``` 🤓：當還能繼續往下走訪且stack不為空的時候，代表還沒全部的node都走過，所以不斷的loop。而當root = NULL)時候代表往左以樹的走訪到極限了，所以開始要印出node的value，印完後換成走訪該node的右sibling樹，然後就一路重複放上述動作直到走訪完全部node ### 初步檢討/改進 #### interviewer side * 如老師所說，不應該一開始就說第幾題，就像在考試一樣 * 沒有包裝題目，直接把leetcode的題目複製貼上 > 要把題目包裝起來，例如inorder traversal的那題，題目可以給出一顆expression tree，請interviewer解釋此expression tree，以及要如何透過這顆expression tree計算出結果。 #### interviewer side * 打字速度有待提升 * 雖然我都用C++ 做，但我應該要先說那我用C++ 來撰寫，並且會使用到C++ STL的物件 * 16:51: 這種寫法太明顯就是為了leetcode做的，與其在inorder這個function中把node value存入ans vector，不如我直接cout出結果就好 ## [378. Kth Smallest Element in a Sorted Matrix](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/) (剛開始面試的各種介紹恭喜你來到面試第二階段) 🗿：In this quesstion,you are given an ```n x n``` matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix. 🤓：All right, acording to my understanding, each rows and columns are in ascending order, for example, the given matrix is ``` [[1,3,6], [2,8,10], [4,12,15]] ``` 🤓：Oh, I found a problem, is it possible that the elements of this matrix are not all distinct? 🤓：Like, ``` [[1,2,6], [2,8,10], [4,12,15]] ``` 🤓：row 1 and row 2 have the same element 2 🗿：That great, I am glad that you ask this question. 🗿：Yes, it's possible. And also your example is fine. (Start coding...) 🤓：Can I assume that all the element in the matrix are positive integer? 🗿：Ok, I accept that. 🤓：First, I store all the elements in the given matrix into a array. 🤓：After I can sort this array and find the kth smallest number. ```cpp int kthSmallest(vector<vector<int>>& matrix, int k) { int n = matrix.size(); vector<int> store; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ store.push_back(matrix[i][j]); } } sort(store.begin(),store.end()); return store[k-1]; } ``` 🤓：Time complexity is O(nlogn) due to the quick sort. 🤓：Space complexity is O(n^2). 🗿：OK, this approach is fine, but could you find a solution that make the Sapce complexity strickly smaller than O(n^2)? 🤓：(Thinking...) 🤓：I think I can use priority queue as a Maxheap, I would push the element in martix one by one into the Maxheap, and whenever the number of element in Maxheap exceeds the given number k, the Maxheap pop, and in the end, I can just simply return the top of this Maxheap as the answer. ```cpp int kthSmallest(vector<vector<int>>& matrix, int k) { int n = matrix.size(); priority_queue<int> maxHeap; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ maxHeap.push(matrix[i][j]); if(maxHeap.size() > k){ maxHeap.pop(); } } } return maxHeap.top(); } ``` 🤓：Using this method I can make the Space Complexity into O(k). 🗿：This is also a good answer, but I think this method is quite similer to the previoud one. 🗿：We still got some time, I can give you some tips. 🗿：Can you solve this question with binary search approach? > 這之後是我不太會的解法，按照interviewer的要求用binary search，所以我開始從binary search的定義與做法嘗試下手，一步一步嘗試 🤓：The binary search approach, for example there a one dimentional arry [1,2,3,4,5,6,7,8,9] if we want to find "a", we first need to assign a left and a right to find the middle of this array, take this for example, left = 1 and right = 9, and the middle = left + right = 5, and then check if a is larger, smaller or equal the middle, if a > middle then the new left number should revise to middle +1, if a < middle then the new right number should revise to middle - 1, if a = middle we find the number we want. While not found the number and left still <= right, we iteratively do the same thing. 🤓：As a result, I can first write down the binary search code. ```cpp int Ksmallest(vector<vector<int>>& matrix, int k){ int n = matrix.size(); int left = matrix[0][0], right = matrix[n-1][n-1], ans, mid; while(left <= right){ mid = (left+right)/2; if( "condition" <= k){ ans = mid; right = mid - 1; } else{ left= mid + 1; } } return ans; } ``` 🤓：If "condition" >= k, we keep current ans = mid and try to find smaller value by searching in the left side. Otherwise, we search in the right side. Since ans is the smallest value which "condition" >= k, so it's the k th smallest element in the matrix. 🤓：The we need to find how to count the position of mid in the nxn matrix. ```cpp int counting(vector<vector<int>>& matrix, int mid) { int n = matrix.size(); int count = 0, c = n - 1; for (int r = 0; r < n; r++) { while (c >= 0 && matrix[r][c] > mid){ c--; } count += (c + 1); } return count; } ``` 🤓：Use two pointers, one points to the rightmost column c = n-1, and one points to the lowest row r = 0. 🤓：If matrix[r][c] <= mid then the number of elements in row r less or equal to mid is (c+1) (Because row[r] is sorted in ascending order, so if matrix[r][c] <= mid then matrix[r][c-1] is also <= mid). Then we go to next row to continue counting. 🤓：Else if matrix[r][c] > mid, we decrease column c until matrix[r][c] <= mid (Because column is sorted in ascending order, so if matrix[r][c] > mid then matrix[r+1][c] is also > mid). ### 初步檢討/改進 #### interviewer side * 29:50: You pass the test，不太好，應該說you solve the question #### interviewer side * 我不太清楚有時候遇到重複使用的code例如 `for(int i = 0 ;i <ｎ; ++i)` 是不是可以複製剛剛已經打過的貼上 * 加強英文解能力，尤其是作答卡住時 * 11:30: 從這裡開始是我在解題時完全沒有想法的作法，所以我開始一邊舉例子，一邊嘗試binary search，但是這樣好像有點太拖延時間了 * 13:43: 講解例子到一半突然提到time complexity有點奇怪 * 13:54: 舉例不太好，因為這個martix不一定是這麼整齊的，有可能`matrix[1][0] ＜　matrix[0][0]` * 16:31: 這邊我已經不太清處怎麼解釋了，所以我就胡亂帶過直接說要開始coding * 19:45: 這裡解釋有點奇怪，只有<=和>，但正常binary serach要check <,>,=的情況，有點跳tone，像是早已經知道解答一樣 * 21:35: 卡了很久 --- ## 第二次作業 - 他評 01 - [ ] 優點 * Interviewee 說明清楚流暢、兩個中文面試聽下來沒什麼停頓感 * Interviewee 在撰寫程式碼時，有一同說明 * (第二題) [21:00](https://www.youtube.com/watch?v=xFwtjJACvY8): Interviewee 有特別解釋為何判斷式為 `root != NULL || usage.empty()` * (第三題) 到後面有假設 Interviewer 給出自己不熟的題目情境，這樣訓練自己挺好的 :+1: - [ ] 可以改進的地方 * (第一題) [4:52](https://www.youtube.com/watch?v=xFwtjJACvY8): Interviewer 提出「這樣速度有點慢」這段，可以放在 Interviewee 提到 Time Complexity 為 $O(n \log{n})$ 之後再提出 * (第一題) [10:45](https://www.youtube.com/watch?v=xFwtjJACvY8): 正式面試時可能不會有可以現場繪圖的工具，所以可以練習一下直接用文字來表示二元樹的方式 (可以參考[模擬面試範例的第二題](https://hackmd.io/@sysprog/BkeIYF8-j)) ## 第二次作業 - 他評 02 ### 關於 interviewer - [ ] 優點 - 適當引導interviewee進行優化 - 英文版的語速順暢，沒什麼卡詞的情況出現 - [ ] 可改進的地方 - (第一題)題目可以包裝一下，例如「租車公司現在有一輛車不見了，每輛車子都有獨立編號，請寫一個程式快速找到不見的那輛車」，後面也可以延伸到k輛車不見的情況。 ### 關於 interviewee - [ ] 優點 * 用Google Docs打code蠻流暢的 * (第一題)在優化的時候有先分析原本作法的瓶頸再思考如何優化 * [ ] 可改進的地方 * Google Docs的字有點模糊，不確定是畫面太小還是google * (第一題)REACTO的T沒有做，雖然題目本身很簡單，不過還是可以演示一下code如何運作 ## 第二次作業-他評 03 ### interviewer - [ ] 優點 * 面具很有趣！ * 講話語速是中，蠻清楚的 * 有引導interviewee思考不同的解法 - [ ] 可改進之處 * 題目應該包裝一下 ### interviewee - [ ] 優點 * 邊coding邊講解得蠻順的 * 有講解到降低時間複雜度的關鍵點在何處 - [ ] 可改進之處 * 畫面有點糊，看不太到內容 ## 第二次作業-他評 04 ### interviewer - [ ] 可改進之處 * [10:40](https://youtu.be/xFwtjJACvY8?t=640): 解釋題目時，如果當場畫圖可能有點浪費時間，實際面試時面試官應該也會先準備好圖片或是範例 ### interviewee - [ ] 優點 * 有做到同時coding和講解 - [ ] 可改進之處 * coding完之後缺少optimize及延伸問題 ## 他評 05 ### interviewer - [ ] 優點 * 表達清楚，語速適中 - [ ] 可改進之處 * [18:10](https://www.youtube.com/watch?v=xFwtjJACvY8=1090) 說出"幫我用其他的方法來進行這一題"，有點缺乏引導的過程 ### interviewee - [ ] 優點 * [3:35](https://www.youtube.com/watch?v=xFwtjJACvY8=215) 有解釋程式碼，且coding過程不會很乾 * [5:00](https://www.youtube.com/watch?v=xFwtjJACvY8=300) 有解釋程式碼，且coding過程不會很乾 * [5:50](https://www.youtube.com/watch?v=xFwtjJACvY8=350) 適當停頓思考，再說出方案 - [ ] 可改進之處 * [10:45](https://www.youtube.com/watch?v=xFwtjJACvY8=645) 面試時間是有限的，畫圖來解釋雖然可以讓人更清楚表達的意思，但會浪費太多時間