---
# System prepended metadata

title: 20220211 Tien Hsin mock Leo

---

# 20220211 Tien Hsin mock Leo

# 1
employee id -> id of subordinates
employee id -> importancy 

1 -> [2,3]
2 -> [4]

1 -> 5 
2 -> 1
3 -> 1
4 -> 1

importancy of employee 1 and it's subordinates is 8 

```python

"""
info
-------

input:

employee_id_to_subordinates

employee_id_to_importancy

target_id

output:
    
    importancy of self & subordinates
    

Test case:

#1

employee_id_to_subordinates: {}
employee_id_to_importancy: {}
target_id: k

-> 0

#2
employee_id_to_subordinates:
{
    1: [2, 3],
    2: [4]
}
employee_id_to_importancy:
{
    1: 1,
    2: 2,
    3: 3
}
target: 1

-> 6?

employee: n
time complexity: O(n)
space complexity: O(n)

"""

def find_importancy_of_target_id(
    e_id_to_s: dict,
    e_id_to_i: dict,
    t_id: int,
) -> int:
    if t_id not in e_id_to_i:
        return 0
    
    ans = 0
    q = collections.deque([t_id])
    visted = set()
    while q:
        n_id = q.popleft()
        visted.add(n_id)
        ans += e_id_to_i[n_id]
        for s_id in e_id_to_s.get(n_id, []):
            if s_id in visited:
                q.append(s_id)
            
    return ans

```
## 2



[0,3,1,6,2,2,7]
length of longest increasing subsequence -> 4 
[0,1,2,7]


```python


"""
info
--

input: list of integer

output: longest strictly increasing length

test case:

[1, 2, 3, 4] -> 4

[1, 1, 1, 1] -> 1

[4, 3, 2, 1] -> 1

[] -> 0


list: [1, 2, 4]

[3, 1, 2, 4]
          ^
          
total elements: n

Time complexity: O(n * logn)
Space complexity: O(n)

result: [3]

t: 1
"""

def find_lic_len(nums: List[int]) -> int:
    def bs(nums: List[in]m t: int) -> int:
        l, r = 0, len(nums)
        while l < r:
            m = l + (l - r) // 2
            if nums[m] < t:
                l = m + 1
            else:
                r = m
        return l
    
    result = []
    for num in nums:
        idx = bs(result, num)
        if len(result) == idx:
            result.append(num)
        else:
            resutl[idx] = num
            
    return len(result)
```

