---
# System prepended metadata

title: 資訊科技產業專案設計(HW1)

---

# 資訊科技產業專案設計(HW1)


## **作業(一)**
##### ***Author : 瞧滷肉GIOGIO***


1. 進行課程協作
2. 練習**LeetCode**
3. 模擬面試的前期準備
4. 練習**中英文對話**
5. 學習影片錄製和剪輯，最終發佈於 YouTube 的「學員專區」
6. 學習 **HackMD** 的使用: **Markdown 語法**, **$\LaTeX%$排版**

## **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 
        🦁 : 好的，那還有沒有別的更好的解法，否則請你對目前最佳的算法進行實作一次

        ```

---

