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

# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1 > 貢獻者: 瑪奇朵 - Macchiato > 🧔：interviewer > 👶：interviewee > > [模擬面試錄影(漢)](https://www.youtube.com/watch?v=SnUV5E7X9_w) > [模擬面試錄影(英)](https://www.youtube.com/watch?v=Rftyh8WdJ_I) ## [112. Path Sum](https://leetcode.com/problems/path-sum/) ### 題目 Given the root of a binary tree and an integer `targetSum`, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals `targetSum`. A leaf is a node with no children. Example 1: ![](https://hackmd.io/_uploads/Sk4VFCq1T.png) > Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 > Output: true ### 問答概要 🧔：你好，歡迎來到這場面試。我們蒐集了不同工作情境中會用到的演算法，整理成以下問題，麻煩你依據這些題目描述自己的想法並實作出來。 🧔：第一個問題準備了數狀結構的搜尋問題，探討在一個樹狀的資料結構中，我們要如何找到符合條件的搜尋路徑並獲取路徑上的資料。以這個情境來說，我們想要在給定的樹狀資料中尋找是否存在符合目標總和的路徑。 👶：(重複題目並舉例說明) ``` 1 2 3 targetSum = 5 false [] targetSum false ``` ### Path Sum with recurrsion 👶：初步的想法是用遞迴的方式去做。當我碰到一個節點的時候，我會判斷他是不是葉節點，如果已經是的話，我會去判斷路徑加上當前節點的值是否等於`targetSum`。如果不是的話，我會用遞迴的方式去計算他的左右子樹，是否有存在相加後符合`targetSum`的路徑。 🧔：好的。想請問樹狀的搜尋除了DFS還有其他的嗎?為甚麼會選用DFS的方式呢? 👶：除了深度優先搜尋之外還有廣度優先搜尋(BFS)，BFS會從根節點逐步往外找距離較近的節點。但這裡要計算的是從根節點到葉節點的路徑，所以如果使用BFS會需要存取許多走到一半的路徑總和。DFS的優點就是不用存取這些數值，不須花費額外的記憶體空間。 🧔：好的。可以開始你的實作，樹狀結構可以參考以下的程式碼。 ```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) {} * }; */ bool hasPathSum(TreeNode *root, int targetSum){ if(root == NULL) return false; if(!root->left && !root->right){ if(root->val == targetSum) return true; else return false; }else{ targetSum -= root->val; return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum); } } ``` 🧔：能不能解釋你的解法是怎麼實現DFS的呢? 👶：我的解法是先判斷左子樹再判斷右子樹，每次會不停的找左子樹，再回到上一層做右子樹的判斷，因此是DFS的實現方式。 🧔：請問上述作法時間複雜度是什麼等級呢? 👶：每個點都會遍歷過一次，因此時間複雜度是 O(n)。 ## [34. Find First and Last Position of Element in Sorted Array](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/) ### 題目 Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity. ### 問答概要 🧔：好的，接下來這題是一個關於已排序數列的搜尋問題。在一個非嚴格遞增的數列中，希望找到目標元素的位置。接下來要麻煩你思考這個問題。 👶：（重複題目並舉例說明） ``` [1,2,2,4,5,6] target = 2 return = [1,2] - [] target return = [-1, -1] ``` 👶：最直接的想法是用一個 for 去遍歷這個非嚴格遞增序列的所有數值，直到找到數值為止。但題目要求是在時間複雜度 O(log n) 之內，所以並不符合題目的要求。 🧔：是的，那你能不能提出其他更好的作法呢？ ### Binary Search 👶：我再來有想到的方法是使用二分搜尋法的方式，可以讓時間複雜度保持在O(log n) 之內。方法上會先取出中間的索引值，再來會去判斷 target 是否大於索引值，大於的話就會將搜尋範圍集中在索引值之後，反之集中在索引值之前，每次可以減少一半的可能性，所以可以讓時間複雜度保持在 O(log n) 之內。 🧔：沒有其他問題的話，可以請你開始實現這段程式碼 ```cpp vector<int> BinarySearchPos(vector<int>& nums, int target){ if(nums.size() == 0) return {-1, -1}; if(target < nums[0] || target > nums[nums.size()-1]) return {-1, -1}; int left = 0, right = nums.size(), mid; // [left, right) while(left < right){ mid = left + (right - left) / 2; if(target > nums[mid]) left = mid + 1; else if(target < nums[mid]) right = mid; else{ int l_pos = mid, r_pos = mid; while(l_pos >= 0 && target == nums[l_pos]) l_pos -= 1; while(r_pos < nums.size()-1 && target == nums[r_pos]) r_pos +=1; return {l_pos + 1, r_pos - 1}; } } return {-1, -1}; } ``` 👶：(舉例說明程式碼的運作) ``` [1,2,2,4,5,6] target = 2 return = [1,2] 0, 5 mid=2 (2) l_pos = 0, r_pos = 3 [1, 2] ``` 🧔：請描述一下數字重複會如何影響時間複雜度呢? 👶：最差的狀況是當整個數列都等於 target 值的時候，他就必須從中間的索引值往左往右找，時間複雜度會是 O(n)。最佳狀況是每個數值都出現一次，且在 binary search 的第一個搜尋到的位置，也就是中間位置(口誤為midtern)，時間複雜度會是 O(1)。對 binary search 來說，最差的狀況是數值出現在，舉例來說最左右兩邊時是最糟，必須要找 log n 次。 ### 題目調整：Find the Position to Insert the Element in Sorted Array 🧔：基於你剛才的做法，將題目稍稍修改一下。如果將這段程式碼改成插入目標值的話並回傳應插入的索引值的話，應該怎麼修改呢?(已經出現在裡面的元素，就插入在已有元素的最後面) 👶：(邊修改邊解釋) ```cpp vector<int> BinarySearchPos(vector<int>& nums, int target){ if(nums.size() == 0) return {-1, -1}; if(target < nums[0] || target > nums[nums.size()-1]) return {-1, -1}; int left = 0, right = nums.size(), mid; // [left, right) while(left < right){ mid = left + (right - left) / 2; if(target > nums[mid]) left = mid + 1; else if(target < nums[mid]) right = mid; else{ int l_pos = mid, r_pos = mid; while(l_pos >= 0 && target == nums[l_pos]) l_pos -= 1; while(r_pos < nums.size()-1 && target == nums[r_pos]) r_pos +=1; return {l_pos + 1, r_pos - 1}; } } return {-1, -1}; } ``` 👶：(舉例說明程式碼的運作) ``` [1,2,2,4,5,6] target = 3 return = 3 0, 5 mid = 2 (2) 3, 5 mid = 4 (5) 3, 4 mid = 3 (4) 3, 3 ``` ## [70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/) ### 題目 Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity. ### 問答概要 🧔：There is a final question for you. You have to climb n-step stairs and you can only take one or two steps at a time. How many combinations of steps can you take to get to the top of the stairs? 👶：So, I can only take one or two steps for a time to climb up n-step stairs. (舉例說明) ``` 0:1 1:1 2:2 1+1 = 2 ``` 👶：Obviously, there is an easy approach using a recursive method. $$ f(n) = f(n-1) + f(n-2)$$However, the time complexity of the recursive method is O(2 to the power of n) that may result in a runtime error. 🧔：And any other approach? 👶：Sure. The drawback of the recursive method is that it takes so much time to calculate the same question. I would like to use a vector to record the number of distinct ways to climb the stairs from one-step to n-step. ### iterative method with vector ```cpp int ClimbingStair(int n){ vector<int> vec; vec.push_back(1); vec.push_back(1); for(int i=2 ; i <= n ; i++){ vec.push_back(vec[i-1] + vec[i-2]); } return vec[n]; } ``` 🧔：I see. And what is the time complexity of this approach? How about space complexity? 👶：The time complexity is O(n) and the space complexity is O(n). 🧔：Is there anything you can do to improve your answer? ### iterative method with only variables 👶：Ok. Because I only have to get the number of way to climp up n-step stiars, so I can replace it with 3 integers to get the final answer. ```cpp int ClimbingStair(int n){ int first = 1, second = 2, method; for(int i=3 ; i <= n ; i++){ method = first + second; fist = second; second = method; } return method; } ``` 🧔：Ok. Thanks for joining the interview. I will contact you when the results are available. Bye. ## 初步檢討 ### interviewee - 沒有做到包裝題目的使用情境 - 只問時間複雜度的問法不夠好（像是為了問而問） ### interviewer - 解釋常常很繞、不夠精簡，需要再多練習表達。為了盡量避免中英交雜的狀況，會為了想中文停頓較久，需要對中文用語再更熟悉。 - 實作的時候講述不夠通暢，要習慣一心二用，一邊打字一邊講想法。講話的時候不要太像在自言自語，說話的目的是為了跟面試者溝通。 - 英文口說待加強。 --- ## 作業二-他評01 - [ ] 優點 * 有舉例說明 * 舉出邊界條件 * 第一題interviewer引導interviewee說出為什麼選用DFS以及其他相關知識。 * 邊打程式碼邊解說 - [ ] 可改進的地方 * 可以使用情境來包裝題目，避免直接說出leetcode題目。 * [18:12](https://youtu.be/SnUV5E7X9_w?si=Q5kW5aeGvl9RY8As&t=1092): 聲音變弱，讓人感覺沒什麼信心。 ## 作業二-他評02 ### 針對interviewer: - [ ] 優點 * 說話平穩 * 咬字清晰 - [ ] 可改進之處 * [5:11](https://youtu.be/Rftyh8WdJ_I?si=hlANkQIzhJ9OtWUy&t=311): 單純只問時間以及空間複雜度略顯單薄，可以在問題上多加一些包裝並結合後面提問改善方法的地方成為一個問題來問面試人。 ### 針對interviewee: - [ ] 優點 * 咬字清晰 * 程式講解清楚到位 - [ ] 可改進之處: * [1:58](https://youtu.be/Rftyh8WdJ_I?si=39f2qZss7DOG2u8x&t=118): 這裡可能要說明一下時間複雜度為何會是如此。 ## 作業二-他評03 ### 針對interviewer: - [ ] 優點 * 語速正常，題意說明清楚 * 與受試者互動良好 * 英文口說流利 - [ ] 可改進之處 * 針對第二題可以引導是否有worst case time complexity也是 $O(\log{n})$ 的解 ### 針對interviewee: - [ ] 優點 * 遵循REACTO，適當repeat題目意思與提出test case * 程式撰寫時有搭配解說 - [ ] 可改進之處 * [15:21](https://youtu.be/SnUV5E7X9_w?t=921): 可以舉例說明為甚麼會產生overflow * 第二題的worst case time complexity並沒有達到題目要求的 $O(\log{n})$ * 英文有點卡詞 ## 作業二-他評04 ### 針對interviewer: - [ ] 優點 * 會進一步詢問面試者的想法、為什麼要用這個方法 * 會問面試者題目不同情況下，會如何影響時間複雜度等 - [ ] 可改進之處 * 在第三題，問面試者「Is there another approach?」，也許可以改成問「How would you improve the time complexity?」或是其他比較明確的提問 ### 針對interviewee: - [ ] 優點 * 有使用 test case 手動跟著程式碼推出結果、驗證正確性 - [ ] 可改進之處 * 可以多問一些問題輸入相關的條件，例如第二題的陣列長度會從多少到多少。像第二題原題的 leetcode 原題中，陣列最大長度是$10^5$，`left+right` 不會造成 overflow（$10^5+10^5<2^{31}-1$），所以 [15:24](https://youtu.be/SnUV5E7X9_w?si=v7Mvb1zuZsmfjRYu&t=924) 的地方其實也可以寫 `left+right` 就好。