# Online Assesement 2021-06-23 (Facebook)
###### tags: `leetcode` `facebook` `assesement`

* 三題題目，一個半小時，三題都有寫過，兩題 medium 一題 easy

## :memo: 第一題

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.

Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Example 2:

Input: nums = [0]
Output: [0]
 

Constraints:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

## :memo: 題意
* :medal: 給你一個 list 要將裡面的 0 都移到最後面，不能新增 list，inplace 的處理方式

## :memo: My solution
* :medal: **思考一**: inplace，所以你只能 swap 裡面的數字。
* :medal: **思考二**: 用雙指針，要思考雙指針在同一個位置上要做什麼事情或是當指針在什麼狀況下要做 swap，swap 完後指針是否還要動作。

## :memo: Code

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        r = 0
        l = 0 
        
        while r < len(nums):
            # 當雙指針在同個位置時，且這個位置上的值不是零，l r 都要向前一步
            if l == r and nums[l] != 0:
                l += 1
                r += 1
                continue  
            
            # 需要 swap 的狀況
            if nums[r] != 0 and nums[l] == 0:
                nums[r], nums[l] = nums[l], nums[r]     
                l += 1
            
            r += 1

## :memo: BigO
* 時間複雜度: O(len(num))。
* 空間複雜度: O(1)

## :memo: 第二題

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2
 

Constraints:

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

## :memo: 題意
* :medal: 給你一個由數字組成的 list 和一個 target，請你找出裡面有幾個連續的 list 的值加起來等於 target。

## :memo: My solution
* :medal: **思考一**: 那我可不可以用一個 for loop 去算每個位置加到目前的值，然後就可以用這些值去算 index 1 => index 3 這段的值，然後將這些值都存在 dictionary 中。

[1,2,3]

=> {0:-1, 1:0, 3:1, 6:2} ({加總的值: index}， 0:-1 這個要自己塞，都還沒走之前位置是在-1，總值是 0)


但上述這樣寫還是會有個問題，用下面的例子來說明：

[1,-1, 1, -1] 如果我們的 target = 0

{0:-1, 1:0, 0:1, 1:2, 0:3} => {0:3, 1:2} 

dictionary 的 value 應該是要換成 這個 key 出現的次數，而不是 index 的值

# 有點複雜，可以用 debug 模式，跑程式來理解一下

## :memo: Code

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        
        dic = {0:1}
        sum_value = 0
        ans = 0
        
        for i in range(len(nums)):
        
            sum_value += nums[i]
            
            if sum_value - k in dic:
                ans += dic[sum_value-k]
            if sum_value not in dic:
                dic[sum_value] = 1
            else:
                dic[sum_value] += 1
                
        return ans

## :memo: BigO
* 時間複雜度: O(len(nums))
* 空間複雜度: O(len(nums))

## :memo: 第三題
### Binary Tree Vertical Order Traversal

## :memo: Code

class Solution:
    def verticalOrder(self, root: TreeNode) -> List[List[int]]:
        import collections
        dic = {}
        
        queue = collections.deque([[root, 0]])
        
        while queue:
            node, level = queue.popleft()
            if node:
                if level not in dic:
                    dic[level] = [node.val]
                else:
                    dic[level].append(node.val)        
                queue.append([node.left, level - 1])
                queue.append([node.right, level + 1])
                
        return [v for k,v in sorted(dic.items(), key = lambda x: x[0])]

## :memo: BigO
* 時間複雜度: O(n + m * log(m))，n = root number，m = key number
* 空間複雜度: O(2n)

## :memo: 真正操作的時間
* 總共 51 分鐘。