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

# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1 > 貢獻者: 瞧滷肉GIOGIO > [模擬面試影片-1(漢)](https://www.youtube.com/watch?v=PnLzfA89Bu8) > [模擬面試影片 (英)](https://www.youtube.com/watch?v=zdfKiC64hJs) > [模擬面試影片-2(漢)](https://www.youtube.com/watch?v=SmPKBypc4vs) ## **572. Subtree of Another Tree** - **Ref** - https://www.youtube.com/watch?v=E36O5SWp-LE * **Description** : 給定一個Tree_A，跟另一個比較小Tree_B，給定一個算法判斷B是否為A之subtree - ***DFS*** * **Solution** 利用DFS走訪Tree_A，比較**每個node.value是否跟Tree_B的root具備相同value** 1. ***若無***，則往下以DFS走訪Tree_A - **A還沒走完** : 繼續找 - **A已經找完** : 不存在跟Tree_B相同子樹， $return false$ 結束程式 2. ***若相等***，則呼叫比對函數(isSame)以DFS走法同步進行比對(遞迴呼叫)，此時主函數會得到以下兩種返回值 - **false** : 回到 $step(1)$ 持續走訪Tree_A - **true** : 確認 Tree-B 為 Tree_A 子樹，直接結束程式 ```python # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool: def isSame(node,sub): if not node and not sub: return True elif not node or not sub: return False if node.val != sub.val: return False return isSame(node.left,sub.left) and isSame(node.right,sub.right) def preorder(node): if node == None : return False if node.val == subRoot.val: if isSame(node,subRoot) : return True return (preorder(node.left) or preorder(node.right)) return preorder(root) ``` * **Complexity Analysis** - 設A樹 $n$ 個 $node$ , B樹 $m$ 個 $node$ - DFS走訪A子樹需要的複雜度$O(n)$，每次都有可能呼叫比對函數(isSame)，複雜度$O(m)$ - 時間複雜度 : 為$O(n \cdot m)$ - 空間複雜度 : A樹的最大樹高$n$ $+$ B樹的最大樹高 $m$ $\implies$ $O(n+m)$ - ***Hash*** * **Solution** 1. 先做出一個hash function 2. 利用DFS 走訪Atree, 當檢查該節點之子節點後紀錄其hash funciton的值計算完後, 先比對Btree的hash值 if true 結束, else 在return hash值回上一層繼續算 * **Complexity Analysis** * 時間複雜度：$O(n)$ * 空間複雜： $O(1)$ ``` 對答草稿 🦁 : interviewer Leo 🐵 : interviewee Sam 🦁 : 嗨，你好，我是擔任這場面試的考官，我的名字叫XXX，首先很高興跟你進行這場面談，那如果沒有問題，我們就開始第一道問答 🐵 : 好 🦁 : 第一道問題是難度簡單的題目，內容是關於tree，根據螢幕中的資料，給定一個treeA，跟另外一個較小的treeB，請給出一個算法，判斷TreeB是否為treeA的子樹。另外 1.注意treeA的節點數落在1~2000，treeB則是落在1~1000之間。 2.節點中的值都是落在-10^4 ~ 10^4之間 3.這裡的tree都是二元樹 🐵 : 第一個想請問，這裡給定的樹是否有規定是二元搜索樹，或是Balance-tree，或是有其他如紅黑樹左偏樹的性質嗎? 🦁 : 沒有就是單純的二元樹，沒有其他特殊的性質 🐵 : 恩好的，那目前最直覺的做法，先利用DFS的走法，先查找A中的每個節點的值，那當找到與treeB root.val相同的值時，在呼叫一個比對函數進行比對如果return值是true，代表找到從該節點下方就是像treeB一樣的tree，false就代表從這個節點的下方並不是treeB，接著再繼續找，直到DFS搜索完整個treeA 🦁 : 好的，那是否可以分析一下這個算法的時間與空間複雜度 🐵 : 因為整個treeA 有 n 個節點，而treeB有 m 個節點，故時間複雜度是 O(nm)，而因為實作方式是利用遞迴，因此呼叫程式所需要之stack複雜度為 O(n+m) ，而不需要額外的空間儲存資訊O(1) 🦁 : 恩!這是一個很直覺的算法，但今天想改進時間複雜度，是否能再提出更好的做法 🐵 : 請問這裡能允許使用額外的記憶體空間作紀錄嗎? 🦁 : 可以 🐵 : 恩... 這裡或許可以利用一個hash進行記錄，因為當給定一個tree的前+中序資訊就可以確定是否為同樣內容的樹。因此可以從treeA 的葉節點進行資訊的建立，把每次要回傳的資料整理成一個前+中的序列跟treeB進行比較，改善後就不需要每次都去遞迴呼叫比對函數，直接對陣列進行比較這樣時間複雜度可以改善到O(n) 🦁 : 恩恩好的那可否請你分別實作剛剛那兩種算法 🐵 : coding... ``` ## **219. Contains Duplicate II** - ***Ref*** - https://www.youtube.com/watch?v=ypn0aZ0nrL4 * **Description** : 給定一個陣列 $arr$ 及一個整數 $k$，檢查是否存在一組 $\begin{equation*}arr[i] = arr[j]\end{equation*}$，且滿足 $\lvert{i-j}\rvert \le k$ 。 - ***Hash map*** * **Solution** 利用 **hashmap** 做輔助，檢查$arr$，從$i=0...n-1$ 依序 1. $arr[i]$ 不在 **hashmap** 中，存入鍵值對 $(key, value) = (arr[i], i)$ 2. 如果$arr[i]$ 曾經存在於 **hashmap**，就比對 $i$ 跟 $j=hashmap[arr[i]]$，$\lvert{i-j}\rvert \le {k}$ 是否成立 - 成立，即結束程式 true - 否則，更新hashmap中$hashmap[arr[i]]$ 的 $value$，回到$step(1)$ ```python class Solution: def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: hashmap = dict() for i in range(0,len(nums)): if nums[i] not in hashmap : hashmap[nums[i]] = i continue if i - hashmap[nums[i]] <=k: return True hashmap[nums[i]] = i return False ``` * **Complexity Analysis** * 時間複雜度 : 每個$arr$中的 $element$ 都看過一次 $\implies O(n)$ * 空間複雜度 : **worst case** 有可能出現每個元素都不一樣，**hashmap**中需要存入全部$element \implies O(n)$ - ***Sliding window*** * **Solution** 從hashmap引入sliding window概念改進，只需要利用一個集合($W$)就可以達成，透過限制集合大小 $\lvert{W}\rvert \le k$，每次檢查 $arr[i] \in W$ 是否成立。具體作法如以下步驟 : - 先初始化 $left$ = 0，利用 $right$ 每次遞增檢查 1. 先檢查right - left 是否有超出$k$ (限制$\lvert{W}\rvert \le k$) * 若超出，就先移除最左邊的$arr[left]$，$left + 1$ 將 window 左方縮減 2. 檢查 $nums[right]$ 是否在 window 中 * 若有，就結束程式 * 若無，$right+1$ 往後檢查，回到 $step(1)$ ```python class Solution: def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: window = set() left = 0 for right in range(0,len(nums)) : if right - left > k : window.remove(nums[left]) left += 1 if nums[right] in window : return True else : window.add(nums[right]) return False ``` * **Complexity Analysis** * 時間複雜度 : $O(n)$ * 空間複雜度 : $O(k)$ ``` 對答草稿 🦁 : interviewer 🐵 : interviewee //revised by Iris 🦁 : Hey monkey ,I'm tiger and I'm senior software engineer at MATASpace, In this interview you're going to use a whiteboard to show your idea and implement it by notepad or writing down ur code in IDE but don't compile& run it. 🐵 : ok, i got it 🦁 : Are u ready? Let's start with the first question! Here is the problem, you're given an integer array and integer, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i-j) less than or equal k. Just a reminder, First, the length of the array is between 1 to 10 to the power of 5. Second, the value in array is between negative 10 to power of 9 to positive 10 to power of 9. Third, k is between 1 to 10 to power of 5. Do you get it ? Feel free to ask any questions, if u don’t understand the problem. 🐵 : mmm... if a number in this array, the number would appear more than 2 times or not? or an arbitrarily just shows up? 🦁 : there's no limitation for times of number appearance 🐵 : OK! I just came up with a solution by using the hashmap method, here is the detail below. By implementing a hashmap to check whether the num appeared before and also record the number with the index. First, check the array from index equals to 0 to n-1, * if arr[i] is not in hashmap means it didn't appear before : we just saved the (num, index) as (key, value) to hashmap * else arr[i] is existed in hashmap : checking index = j for the arr[i] saved in hashmap , if abs(i - j) is less than equal to k which means we found a matching pair for the problem. if we search the whole arr but didn't find any matching pair, then return to false. the time complexity of this approach is big O of n and space complexity is also big O of n 🦁 : ok, the approach is feasible. but could you improve the space complexity for this approach? 🐵 : yeah, we can imporve this approach by introducing "sliding window" concept. By using a set(W) to save the arr[i] , and left and right pointer to check the window size wouldn't exceed the k. Every time before we check the number[right] , we calculate the right minus left less than or equal to k, if not, we remove the arr[left] from set(W) and shift the left pointer to right by 1, and checking whether or not the arr[right] in the set(W), if there's an arr[right] in set, which means we found a pair matching the problem. the space complexity can downsize to k, and time complexity remains the same. 🦁 : Great! Could you implement the approach by using the IDE and giving some test samples to validate your idea ? 🐵 : yes, i try it now, (coding ...) ``` ## **55. Jump Game** - **Ref** - https://www.youtube.com/watch?v=Yan0cv2cLy8&t=325s * **Description** : 給定一串陣列$arr$，長度為$n$。首位置索引為 $0$，每個$arr[i]$代表從當前位置所能前進的步數，請給定一個算法判斷一個陣列是否能從 $i=0$ $\overset{走到}{\implies}$ $i = n-1$ - ***Brutal force*** * **Solution** 根據以下圖片範例，利用DFS的方式搜索全部可能的結果 1. 過程中，有**任一個結果可到達** $i = n-1{\implies} True$ 2. 搜完全部可能性後仍**沒辦法**到達 $i = n - 1 {\implies} False$ ![](https://hackmd.io/_uploads/HyA6BTIC2.png) * **Complexity Analysis** * 時間複雜度 : $O(n^{n})$ * 空間複雜度 : $O(n)$ * **Improvement** * 利用額外一維陣列，資料類型為布林值，進行cache。紀錄不可能到達終點的index為false，每次都去hashmap確認，改善重覆巡訪的overhead * 時間複雜度 : 可縮減到$O(n^2)$ * 空間複雜度 : $O(n)$ - ***Dynamic Programming*** * **Solution** 從 $i = 0$ 開始， 1. 如果發現 $i > arrival$ 代表從 $i - 1$ 以前的位置都不可能跳到 $i \implies false$ 2. 維護 $arrival$ 最大值 $arrival = max(arrival, i + nums[i])$ 3. 整個過程中如果 $arrival>n-1 \implies true$ ```python class Solution: def canJump(self, nums: List[int]) -> bool: n = len(nums) arrival = 0 i = 0 while i < n : if i > arrival : return False arrival = max(arrival,i+nums[i]) if arrival >= n-1 : return True else: i += 1 ``` * **Complexity Analysis** - 時間複雜度為 $O(n)$ - 空間複雜度 : 每次維護最遠能走到的距離(arrival)$\implies$ $O(1)$ - ***Greedy*** * **Solution** $goal$ 先初始化為 $n-1$ 1. 從倒數第二位$i = n-2$開始往前看 * 如果$i + arr[i] \ge goal$ 成立，$goal = i$ ，將$i = i-1$重複$step(1)$ 2. 當全部看完後檢查$goal$ * $\begin{equation}goal = 0\end{equation} \implies true$ * $\begin{equation}goal \ne 0\end{equation} \implies false$ ```python class Solution: def canJump(self, nums: List[int]) -> bool: goal = len(nums)-1 for i in range(len(nums)-2, -1, -1): if i + nums[i] >= goal : goal = i if (not goal) : return True else : return False ``` * **Complexity Analysis** * 時間複雜度 : $O(n)$ * 空間複雜度 : $O(1)$ * $greedy$ 法在 $best$ $case$ 會略輸給$DP$解法 ``` 對答草稿 🦁 : interviewer 🐵 : interviewee 🦁 : 接下來是一題難度中等的題目，內容是關於陣列，請你看一下這個陣列，給定一個陣列，陣列中每個數目代表從目前索引所能往前走的最遠距離。請給定一個算法判斷當起始點在索引為0時，是否能成功從0->n-1。另外注意 1. 陣列的長度落在1~10^4 之間 2. 陣列中的值落在0~10^5 那題目就如上述，你有別的問題嗎? 🐵 : 陣列中的值有規定每次跳躍都要用完嗎，舉例來說 nums[5] = 3 ，是否代表當在index=5，一定要跳三個，還是可以任意從1~3選擇一個進行跳躍? 🦁 : 以你舉例來說，當值落在1~3之間，跳躍的距離可以從1~3之間任意選擇 🐵 : 好的，第一個想法是利用dfs做搜索，設想以下範例，nums[0] 可以跳三個，所以就有 1~ 三條路分別走到 index = 1 ,2 ,3 的可能，以此類推，當有一條路可以走到 n-1 就return true，否則就是false。此方法的時間複雜度為 O(n^n) 空間複雜度 O(n) 去對arr 做pop&push。 🦁 : 好的，但這樣的時間複雜度似乎有點高，是否能提出改善的想法或是別的方案呢? 🐵 : 如果是根據上面的想法，可以先利用cache，把不可能到達終點的index紀錄下來這樣後續走到此index時就不用在往下搜索。因為每個index最多就是看後面的index 1+2+3+...+n-1 時間複雜度可以減少到 O(n^2)，空間仍維持相同的O(n) 🦁 : 好的，這個改善方案是可行的，但有沒有更好的算法可以減少複雜度到線性時間內呢? 🐵 : 恩... 這題應該還可以利用動態規劃，可以維護一個arrival代表目前所能到達的最遠距離，每次往下一個索引，先檢查前一次更新的arrival是否能到達這裡，如果有，就可以進行arrival更新，否則就代表不可能跳到這個位置，return false。一直持續更新下去到n-1 都成立結束迴圈，就代表可以成功走完整個陣列 => true 🦁 : 好的，那還有沒有別的更好的解法，否則請你對目前最佳的算法進行實作一次 ``` --- ## 第二次作業-他評 01 ### interviewer - [ ] 優點 * 直接畫圖給面試者看，好心的面試官 * 面試氛圍輕鬆，用畫的給人一種自由發揮的感覺 - [ ] 可改進的地方 * 可用實例來包裝問題，讓問題往實際層面延伸，測試面試者在面對實際情況時如何將其化為簡單的演算法問題 ### interviewee - [ ] 優點 * 口齒清晰，且流程簡潔俐落，可以編寫程式碼邊講解，帶領面試官了解其思考 * 即使REACTO的流程順序不太對但解說連貫不突兀所以無傷大雅 - [ ] 可改進的地方 * leetcode解題記錄不要露出來，因為面試一定不會想考你已經做過的題目，就算你做過也要假裝沒做過 ## 第二次作業-他評 02 ### interviewer * 用畫圖的方式讓人更好理解題目要求 * 講解清晰易懂 ### interviewee * 講解清晰 * 在和interviewer溝通時間複雜度考慮較全面，有討論worst case - [ ] 可改進之處 * 語速有時會偏快，稍微聽不清楚 ## 第二次作業-他評 03 ### interviewer - [ ] 優點 * 利用圖來講解題目，使面試過程更為順暢 - [ ] 可改進之處 * 語速有些快 * 可以先讓 interviewee 實作第一個方法的程式碼在詢問改進方案，讓 interviewee 能先透過 coding 找出當前方法的不足之處，可以更全面的對方法做改進。 ### interviewee - [ ] 優點 * 邏輯清晰，在講解方法的實作與時間複雜度分析能用繪圖來清楚說明 - [ ] 可改進之處 * 在作答前有先將疑問提出，確認條件。 * 講話清楚，與 interviewer 有良好的互動 ## 第二次作業-他評 04 ### interviewer - [ ] 優點 * 特別畫圖出來給面試者，這肯定是個好人 - [ ] 可改進之處 * 有看到面試官都提邊界範圍了，那就可以針對該部分發問多一些問題 * 面試官可以問，如果嘗試更改邊界範圍，那麼該程式有需要更動嗎？以此測驗出面試者的反應程度。 ### interviewee - [ ] 優點 * 過程相當流暢，邊打程式碼，邊講解 - [ ] 可改進之處 * [2:35](https://youtu.be/PnLzfA89Bu8?si=lA3PF5jwXT75VB9j&t=537): 面試官說明了題目邊界範圍後，然後在面試者後面的方法說明中，並沒有說到對於該邊界範圍你的方法是否能有效應對，可以將該處補上 * 在你用手寫說明時，你的手寫文字看了很痛苦，可以慢慢寫好看一點，相信這對面試有幫助 ## 第二次作業-他評 06 ### interviewer - [ ] 優點 * 使用畫圖的方式輔助tree的介紹，讓人很容易就聽懂問題是什麼 * 有模擬出遠端面試那種在等待對方講完話的時間差 - [ ] 可改進之處 * 因為滑鼠作圖較困難，所以多少會比較潦草一點 * 語速有時候會過快 ### interviewee - [ ] 優點 * 思考的很全面，在回答前會先將題目問清楚 - [ ] 可改進之處 * 如果是文字的話，或許可以考慮用打字的，會比較快速且清楚 ## 第二次作業-他評 07 - [ ] 優點 * 有畫圖解釋，讓人容易理解題目在幹嘛 * 過程相當流暢 - [ ] 可改進之處 * 用滑鼠寫國字的地方改成用打字的會比較好。