# Grace
###### tags: `mock_interview`

# 2022/04/18

calendar1:
10 -> 20: True [start, end)
15 -> 25: False
20 -> 30: True

calendar2:
10 -> 20: True [start, end)
15 -> 25: True,
                [10, 15): 1
                [15, 20): 2
                [20, 25): 1
10 -> 18: False

#(10, 20, 1) (..)
[10, 15): 1
[15, 20): 2
[20, 25): 1

[1, 2)  :1
[3, 6)  :1
[8, 10) :1
[1, 20)
 
[22, 23]
time = [[10, 20], [25, 26]  [28, 30]] (n) , time[0]
                 ^         ^
(28, 30) -> binary search
       
0 -30 -> t
time = [0] * 31

class MyCalendar:

    def __init__(self):
        self.time  = []
        SortedList([]) # [1, 3, 7, 10]


    def book(self, start: int, end: int) -> bool:  #(n + logn) *n ->n * n
        x = [start, end]
        bisect.insort_left(self.time, x, key = x[0])
        idx = bisect.bisect_left()

        idx = self.time.indexof(x)
        status = True
        if idx == 0:
            if x[1] > self.time[idx + 1][0]:
                status = False
        elif idx == len(self.time) - 1:
            if x[0] < self.time[idx - 1][1]:
                status = False
        elif x[0] < self.time[idx - 1][1] or x[1] > self.time[idx + 1][0]:
            status = False
        
        if status == False:
            self.time.remove(idx)
        return status


class MyCalendarII:

    def __init__(self):
        self.time  = [] #(s, e, cnt)


    def book(self, start: int, end: int) -> bool:  #(n + logn) *n ->n * n
        x = [start, end]
        valid = True
        for i, (s, e) in enumerate(self.time):
            # split interval
            
        for i, (s, e) in enumerate(self.time):
            # update count
            
            if start in [s, e] and end in [s, e]:
                # [1, 30], [2, 5] -> [1, 2], [2, 5], [5, 30]
                self.time.remove(i)
                a = [s, start]
                b = [start, ]
                bisect.insort_left(self.time, x, key = x[0])
            elif:
            elif:

https://leetcode.com/problems/longest-path-with-different-adjacent-characters/

nums = [[2, 4, 8], [...]]
res = 78914

4(7)
2(8). 6(9)

1(1) 3(4)

https://leetcode.com/problems/cherry-pickup/
https://leetcode.com/problems/find-the-duplicate-number/

# 2022/04/11
house = [1,2,3,1] # >0
=> 1 + 3 = *4*
=> 2 + 1 = 3

dp = [0, 2, 0, 0] #i 可以拿到的val
1. 2 4
1 2
dp[i] = max(house[i] + dp[i - 2],
dp[i - 1])

def robber(house):

dp = [0] * len(house)
dp[0] = house[0]
res = dp[0]
for i in range(1, len(house)):
if i - 2 < 0:
dp[i] = max(house[i], dp[i - 1])
else:
dp[i] = max(house[i] + dp[i - 2], dp[i - 1])

res = max(res, dp[i])
return res

city = [
[4, 3, 4] => 2
[3, 4, 3] => 1
]

[0, 0, 10]
8. 9 10 => 17

[
[9, 9, 10], => 36
[10, 9, 9],
]

[
[9, 9, 10], =>
[10, 9, 9],
]

[
[9, 9, 10], => 45
[9, 9, 9],
]
[
[8, 9, 10], => 41
[7, 8, 9],
]
dirs = max() - 1, 0

return bricks (min)

source = (0, 0)
delta = 1
vis = defaultdict(int)

def buildCity(city):
m, n = len(city), len(city[0])
dirs = [0, -1, 0, 1, 0]
maxVal = 0
for i in range(m):
maxVal = max(maxVal, max(city[i]))

q = deque([]) #heap (val, (i, j))
vis = set()
for i in range(m):
for j in range(n):
if city[i][j] == maxVal:
q.append((i, j))
vis.add((i, j))
res = 0
while q:
cx, cy = q.popleft()
cur_val = city[cx][cy]
for k in range(4):
nx, ny = cx + dirs[i], cy + dirs[i + 1]
if nx < 0 or nx == m or ny < 0 or ny == n or (nx, ny) in vis:
continue
res += cur_val - 1 - city[nx][ny] if cur_val - 1 - city[nx][ny] > 0 else 0
city[nx][ny] = cur_val - 1
q.append((nx, ny))
vis.add((nx, ny))
return res

[9, 8, 8, 9 , 10, 11]

https://leetcode.com/problems/continuous-subarray-sum/
https://leetcode.com/problems/subarray-sum-equals-k/

class Encrypter:
def __init__(self, keys: List[str], values: List[str], D: List[str]):
self.en = {}
self.de = defaultdict(set)
for i in range(len(keys)):
self.en[keys[i]] = values[i]
self.de[values[i]].add(keys[i])

self.trie = {}
for word in D:
curr = self.trie
for w in word:
if w not in curr:
curr[w] = {}
curr = curr[w]
curr["#"] = {}

def encrypt(self, W: str) -> str:
ans = ""
for w in W:
ans += self.en[w]
return ans

def decrypt(self, W: str) -> int:
def dfs(idx, curr):
if idx == len(W):
if "#" in curr:
self.ans += 1
return

key = W[idx: idx + 2]
for c in self.de[key]:
if c in curr:
dfs(idx + 2, curr[c])

self.ans = 0
dfs(0, self.trie)
return self.ans