# Jean
###### tags: `mock_interview`

### Conveyor

words = ["", "a", "ab", "ba", "ba", "ba", "baaa", "bag", "bb", "cat"]
prefix = "ba"
=> 5

words = [
    ["I", "am", "Sam"],
    ["I", "am", "Andy"],
    ["I", "like", "apple"],
    ["a", "b", "c"],
    ["b", "a", "c"],
]

predict("I") // "am"


const dict = {
    "I": {
        max: "am"
        next: {
            "am": 2,
            "like": 1
        }
    },
}

nums = [1, 6, 4, 2, 5, 3], K = 4
stack = [1]
stack = [1, 6]
stack = [1, 4]     r = [6]
stack = [1, 2]     r = [6, 4]
stack = [1, 2, 5]  r = [6, 4]
stack = [1, 2, 3]  r = [6, 4, 5]
r.sort() => [4, 5, 6] 
merge

def solve(G):
    M, N = len(G), len(G[0])

    def next_dir(x, y, d):
        if d == 0:
            return x, y + 1
        elif d == 1:
            return x + 1, y
        elif d == 2:
            return x, y - 1
        else:
            return x - 1, y

    vis = {}
    def dfs(x, y, curr_vis, cost):

        key = (x, y)
        if key in curr_vis:
            return float('inf')

        if key in vis and cost >= vis[key]:
            return vis[key]

        if x == M - 1 and y == N - 1:
            return cost

        curr_vis.add(key)

        res = float('inf')
        (G[x][y] + 2) % 4
        for d in range(4):
            next_x, next_y = next_dir(x, y, d)
            if 0 <= next_x < M and 0 <= next_y < N:
                next_cost = int(d != G[x][y])
                res = min(
                    res,
                    dfs(next_x, next_y, curr_vis, cost + next_cost)
                )

        curr_vis.remove(key)
        vis[key] = res
        return res

    ans = dfs(0, 0, set(), 0)
    return ans


# 0: right
# 1: down
# 2: left
# 3: up
G = [
    [0, 0, 0, 1],
    [1, 2, 2, 2],
    [0, 0, 0, 1],
    [1, 2, 2, 2],
    [0, 0, 3, 0],
]

print(solve(G))

// 2022/04/14

target = 12
position = [10,8,0,5,3]
speed =    [2, 4,1,1,3]

[0, 1]
[2]
[3, 4]
=> 3
car1 car2
(target - s1)/ v1 < (target - s2) / v2

s1 + v1*t = s2 + v2*t
t = (s2 - s1) / (v1 - v2)

new car (v2)
starting at : s2 + v2 * ((s2 - s1) / (v1 - v2))

a, b => b
a, b, c, d, e, f
a, b => ab
ab, c => abc
abc, d, e => abc, de
abc, de, f => 


function carCollision(target, position, speed){
    const cars = [] // car speed sorted by position
    let result = cars.length;
    const carSets = [cars[0]]
    
    for(let i = 1; i < cars.length; i++){
        
        p, s = speed[i], position[i]
        stack = [[speed, position]]
        while stack and abs(p - stack[-1][1]) / abs(s - stack[-1][0]) <= (target - p) / s:
          stack.pop()
        stack.append((s, p))
        => [slowest, ... , fastest]
        
        if(cars[i] collide with carSets[carSets.length - 1]){
            carSets[carSets.length - 1] = cars[i]
            while(carSets.length > 1 && carSets[carSets.length - 1] collide carSets[carSets.length - 2]){
                // merge carSets[carSets.length - 1] & carSets[carSets.length - 2
                [2, 1] => [1]
                const lastV = carSets.pop()
                carSets[carSets.length - 1] = lastV
                c[1] = 1
            }
        }else{
            carSets.push(cars[i])
        }
    }
    return carSets.length
}












// 2022/04/07

books = [1, 2, 3, 4, 5]
int search(book_page):

void swap(a_idx, b_idx):

cache = [{2: 3}, {1: 2}]
put(1, 3)
search(2) // 3

Total = 4 + 6 = 10

// a = new Deque([1, 2, 3])
// a.shift()
arr[i] // O(1)
dq[i]  // O(N)

// pizza = [6,1,2,3,4,5]
// pizza[i] + dp(pizza)
// dp(pizza){
// for(let piece of pizza)
// const newPizza = pizza.splice(i-1, 3)
// }
function maxPizzaValue(pizza){
    const memo = {}
    
    function helper(pizza){
        // [1, 2, 3, 4, 5, 6], [3, 4, 5]
        if(pizza.length === 0) return 0
        
        const key = pizza.join('-')
        if(key in memo) return memo[key]
        
        let max = 0;
        for(let i = 0; i < pizza.length; i++){
            // i = 0, 0
            const newPizza = [...pizza]
            if(i === 0 || i === pizza.length - 1){
                newPizza.splice(i, 1)
                newPizza.pop()
                newPizza.shift()
            }else{
                newPizza.splice(i-1, 3)
            }
            
            // newPizze = [3, 4, 5], []
            const value = pizza[i] + helper(newPizza);
            
            // value = 3 + 0
            max = Math.max(max, value)
        }
        memo[key] = max
        return max
    }
    
    return helper(pizza)
}


[9, 10, 9, 1, 1, 1]



















// 2022/03/31
//G = [[[1,2], [1, 16], [2, 8]],[[]]]
// queries = [
//     [src, tgt, max_weight], ... 
// ]
// [true, false, true, ...]

// 5 -> 7, 10 # True
// 5 -> 7, 15 # True

function hasPathWithinWeight(G, n, source, target, maximumWeight){
    const queue = [source];
    const visited = new Array(n).fill(false)
    
    while(queue.length){ // N
        const node = queue.shift() // N
        if(node === target) return true
        visited[node] = true
        
        for(let [adjNode, weight] of G[node]){ // one node edge number => E
            if(weight <= maximumWeight && !visited[adjNode]){
                queue.push(adjNode)
            }
        }
    }
    
    return false
}

sort Queries by max weigth
sort Edge by weigth
edge_idx = 0
u = Union(N)

for src, tgt, max_w in Query:
  while edge_idx < len(Edge) and Edge[edge_idx][2] <= max_w:
    u.union(Edge[edge_idx][0], Edge[edge_idx][1])

  p_src = u.find(src)
  p_tgt = u.find(tgt)
  ans.append(p_src == p_tgt)