[Interview] Google

Posted on | In , |

Topic: Bipartite Graph

Video: https://www.youtube.com/watch?v=HqlUbSA9cEY

Vertices in one group doesn’t have edges within the group members. For every edge, the vertices on two ends have to belong to the 2 groups.

The Hungarian Algorithm

Solves assignment problem -> find the most efficient way to assign jobs

Step:

  1. Find the minimum of each row
  2. Subtract from every element in the graph by the minimum of the current row
  3. Repeat same steps for columns
  4. Test for an optimial assignment: draw staight lines connecting all the 0s, if the minimum number of lines equals to the number of rows or columns, we can go to step 6 else if smaller go to step 5
  5. Shift zeros: (1) Subtract every element in the graph by the smallest element (2) Add the smallest element to the element in the intersection of very 2 lines. Go back to step 4.
  6. Making the final assignment: choose the 0 from each column and row
  • If not number of columns doesn’t equalt to the number of rows: simply create additional rows / columns filled with 0s.

Time complexity: O(n^3)

785. Is Graph Bipartite?

Leetcode: https://leetcode.com/problems/is-graph-bipartite/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def isBipartite(self, graph: List[List[int]]) -> bool:
    group = [0 for _ in range(len(graph))]
    
    def dfs(cur, prev):
        nonlocal group

        if group[cur] == 0:
            group[cur] = prev * -1
        else:
            if prev == group[cur]:
                return False
            else:
                return True

        for neib in graph[cur]:
            if not dfs(neib, prev * -1):
                return False
        return True
    
    for i in range(len(graph)):
        if group[i] == 0:
            if not dfs(i, -1):
                return False
    return True

886. Possible Bipartition

Leetcode: https://leetcode.com/problems/possible-bipartition/

1
2


Return subsequence

Given an string s and an array arr, return all subsequence of s in arr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# s: leetcodeishard
# arr: [l, eet, code, arc, beac, hard]
def getSubsequence(s, arr):
    pass

getSubsequence("", []) # []
getSubsequence("leetcodeishard", ["l", "eet", "code", "arc", "beac", "hard"]) # ["l", "eet", "code", "hard"]

import collections

class TrieNode:
  def __init__(self, val):
    self.val = val
    self.children = {} # {"a": TrieNode(a)}
    self.isEnd = False

def getSubsequence(s, words):
    # construct trie from arr 
    root = TrieNode("")
    for word in words:
      cur = root
      for i, ch in enumerate(word):
        if ch not in cur.children:
          cur.children[ch] = TrieNode(ch)
        cur = cur.children[ch]
      cur.isEnd = True

    stack = []
    res = []
    i = 0
    while i < len(s):
      curCh = s[i]
      if curCh in root.children:
        stack.append((root.children[curCh], curCh, i))
      i += 1
    while stack:
      curNode, curStr, curIndex = stack.pop(0)
      if curNode.isEnd:
        res.append(curStr)
      if curIndex < len(s) - 1:
        nextCh = s[curIndex + 1]
        if nextCh in curNode.children:
          stack.append((curNode.children[nextCh], curStr + nextCh, curIndex + 1))
    return res

LC 1244

https://leetcode.com/problems/design-a-leaderboard/

API includes arbitrary getRank(int rank)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import heapq

class Leaderboard:

    def __init__(self):
        self.players = collections.defaultdict(int) # {player: score}

    def addScore(self, playerId: int, score: int) -> None:
        self.players[playerId] += score

    def top(self, K: int) -> int:
        heap = []
        scores = 0
        for player, score in self.players.items():
            scores += score
            heapq.heappush(heap, (score, player))
            if len(heap) == K + 1:
                smallScore, _ = heapq.heappop(heap)
                scores -= smallScore

        return scores

    def reset(self, playerId: int) -> None:
        self.players[playerId] = 0

    def getRank(self, playerId: int) -> int:
        # what if 2 players shares score? 
        # sort (score: player) and find player's place
        heap = [] # max heap
        rank = 0
        prevScore = -1
        skippedNum = 0
        for player, score in self.players.items():
            heapq.heappush(heap, (-score, player))
        while heap:
            score, player = heapq.heappop(heap)
            if prevScore != score:
                rank += skippedNum
                skippedNum = 0
            else:
                skippedNum += 1
            if player == playerId:
                return rank
            prevScore = score
        return -1

Tree

LC 538

Leetcode: https://leetcode.com/problems/convert-bst-to-greater-tree/

Sum does not include itself

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def convertBST(self, root: TreeNode) -> TreeNode:
    curSum = 0
    if not root:
        return root
    def visit(node):
        nonlocal curSum
        if node.right:
            visit(node.right)
        curSum += node.val
        node.val = curSum
        
        if node.left:
            visit(node.left)
    visit(root)
    return root

Leetcode 652. Find Duplicate Subtrees

Leetcode: https://leetcode.com/problems/find-duplicate-subtrees/

  • Serialize the node as hash key
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
    visited = set()
    res = {}
    
    def serializeNode(node):
        nonlocal visited
        nonlocal res
        
        if not node:
            return "#"
        
        left = serializeNode(node.left)
        right = serializeNode(node.right)
        result = "(" + left + "," + right + "," + str(node.val) + ")"
        if result in visited:
            res[result] = node
        else:
            visited.add(result)
        return result
    
    serializeNode(root)
    return list(res.values())

Shortest path of two nodes in binary tree

Description: 需要print从一个node到另一个node的完整路径，比如向上走就是up，向下走就是left或者right，最后结果是个string array，比如[up, up, left, right, …]这样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def findPath(self, root: 'TreeNode', start: 'TreeNode', end: 'TreeNode') -> 'list':
    startToLCA = []
    LCAToEnd = collections.deque([])
    foundLCA = False
    # directions: up, left, right
    # find LCA
    # find direction from start to LCA
    # find direction from LCA to end
    # if leftStart or righStart: append("up")
    # if leftEnd: append("left"), if rightEnd: append("right")
    def visit(node):
        nonlocal res
        nonlocal foundLCA
        
        if not node:
            return (False, False) # (start, end)
        foundStart, foundEnd = False, False

        leftStart, leftEnd = visit(node.left)
        rightStart, rightEnd = visit(node.right)
        
        foundStart = node == start or leftStart or rightStart
        foundEnd = node == end or leftEnd or rightEnd
        if not foundLCA:
            if leftStart or rightStart:
                startToLCA.append("up")
            if rightEnd:
                LCAToEnd.appendleft("right")
            if leftEnd:
                LCAToEnd.appendleft("left")
        if foundStart and foundEnd:
            foundLCA = True
            
        return (foundStart, foundEnd)
    visit(root)
    res = startToLCA + list(LCAToEnd)
    return res

Leetcode: 394. Decode String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def decodeString(self, s: str) -> str:
    res = ""
    cnt = ""
    stack = [[1, ""]]
    for ch in s:
        if ch.isdigit():
            cnt += ch
        elif ch == "[":
            stack.append([int(cnt), ""])
            cnt = ""
        elif ch.isalpha():
            stack[-1][1] += ch
        elif ch == "]":
            count, curStr = stack.pop()
            stack[-1][1] += count * curStr
    while len(stack) > 1:
        count, curStr = stack.pop()
        stack[-1][1] += count * curStr
    return stack[0][1]

Variant: a(bc(de){2}){3}

Leetcode 202

Follow up: multiple visit optimize time, optimize space

Leetcode 843. Guess the Word

Leetcode 1499. Max Value of Equation

Leetcode: https://leetcode.com/problems/max-value-of-equation/

Solution 1: Priority Queue

  • yi + yj + |xi - xj| = yi + yj + xj - xi = (yj + xj) + yi - xi (i < j)
  • For any j, find i so that yi - xi is the maximum
1
2
3
4
5
6
7
8
9
10
11
12
def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
    heap = [] # (yi - xi, xi)
    res = -float('inf')
    for j in range(len(points)):
        curJ = points[j][1] + points[j][0]
        
        while heap and points[j][0] - heap[0][1] > k:
            heappop(heap)
        if heap:
            res = max(res, -heap[0][0] + curJ)
        heappush(heap, (points[j][0] - points[j][1], points[j][0]))
    return res

Optimize with monotonic queue
Same as LC 239: Sliding window max

path match

give a prefix and request string. return true if they can be matched. for example, prefix /a/b can match to /a/b/c. follow up: wildcard, /a/ can match to /a/b/c. follow up 2. return the best match give a list of prefixes. for example, /a/ /a//c both match /a/b/c, you will need to return /a//c.

gossip forward message

given a list of message events[(from, to, timestamp),(from, to, timestamp),..] and a start person. return all persons who will receive this message.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import collections

class Event:
  def __init__(self, start, end, time):
    self.start = start
    self.end = end
    self.time = time

input = []
input.append(Event('a', 'b', 8))
input.append(Event('b', 'c', 10))
input.append(Event('c', 'd', 12))
input.append(Event('b', 'e', 9))

start = 'b'
startTime = 9
def getReceivers(input, start, startTime):
  input.sort(key = lambda x: x.time)
  graph = collections.defaultdict(list) # {'a': [('b': 10), ('c': 12)]}
  # construct graph
  for event in input:
    if event.time >= startTime:
      graph[event.start].append((event.end, event.time))
  # bfs
  res = set()
  queue = [(start, startTime)]
  while queue:
    person, time = queue.pop(0)
    res.add(person)
    if person in graph:
      for neib in graph[person]:
        queue.append(neib)

  return res

Json parser

assume you have 2 functions which can be used to parse json string. Implement a function to query by path index. List parse(String json), implemented, return a list of string of that json. String parse(String json, String key), implemented, can only return top level key’s value in the json string. you need to implement List query(String q, String json) for example. json: {“a”:[{“b”:”1”,”c”:”3”},{“c”:”2”}]}. query: a.0.b ->1. query: a.1.c -> 2. follow up. support wildcard query. query: a.*.c ->[3,2].

Gmail’s Smart Compose feature

We want to build Gmail’s Smart Compose feature. Assume we have a service that returns top K most likely next words and their probabilities for a given word. We want to return Top 3 Smart Compose recommendations to the user.
List[Tuple[String, float]] get_candidates(String word); → implemented for you
List[String_Sequence] get_smart_compose_recommendations(String word); → need to implement

Top K element question

Mostly can be solved with heap

Leetcode 378. Kth Smallest Element in a Sorted Matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
    heap = []
    i, j = 0, 0
    for i in range(len(matrix)):
        heapq.heappush(heap, (matrix[i][0], i, 0))

    while heap:
        val = heappop(heap)
        row = val[1]
        col = val[2]
        k -= 1
        if k == 0:
            return val[0]
        if col + 1 < len(matrix[0]):
            heappush(heap, (matrix[row][col + 1], row, col + 1))
    return -1

String & Array

数字转英文

01字符串数组

01字符串数组 对任意一对字符串 从左到右第一个不相等的字符对开始 两个串剩余的串长度之和 求最大的和
Leetcode 543

Min-Max

Pile of Cards

Leetcode Discussion: https://leetcode.com/discuss/interview-question/537699/google-onsite-card-game

Leetcode: https://leetcode.com/problems/stone-game-iii/

Dynamic Programming

Jump game

一个0/1组成的list 0表示有障碍物 1表示没有 一个人往前可以跳1步 也可以跳3步 4步 问从起点能不能到终点. follow up 求最短步数

Leetcode 1696. Jump Game VI (https://leetcode.com/problems/jump-game-vi/)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def maxResult(self, nums: List[int], k: int) -> int:
    # store max steps within [i - k : i]
    # sliding window to store max value?
    if not nums:
        return 0
    dp = [0 for _ in range(len(nums))]
    pastMax = nums[0]
    left = 0
    heap = []
    heappush(heap, (-nums[0], 0))
    dp[0] = nums[0]
    for i in range(1, len(nums)):
        while heap[0][1] < i - k:
            # if largest num in heap is the leftest one
            heappop(heap)
        dp[i] = -heap[0][0] + nums[i]
        heappush(heap, (-dp[i], i))
        
    return dp[-1]

Leetcode 1871. Jump Game VII

  • It’s a bottom-up DP implementation. The boolean value represents whether this position is reachable from start. So the first step is to generate the table. Here the table was pre-labeled True or False, thus ‘1’s are already labeled False.
  • To determine the state of dp[i], one need to check the states in window dp[i-maxJ : i-minJ], because any one of them can reach i if it’s labeled True.
  • Then you need to check if there is a True in this window. Notice that this is a sliding window problem, so you don’t need to calculate it everytime. You only need to remove the effect from dp[i-maxJ-1] and add the dp[i-minJ]. This is done by these two lines of code pre += dp[i - minJ] and pre -= dp[i - maxJ - 1]
  • The if statements if i >= minJ: and if i > maxJ: are dealing with the initial boundary.
1
2
3
4
5
6
7
8
9
10
11
12
def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
    dp = [False for _ in range(len(s))]
    prevReach = 0
    dp[0] = True
    for i in range(1, len(s)):
        if i >= minJump and dp[i - minJump]:
            # sliding window problem, prevReach records the number of reachable steps in the window
            prevReach += 1
        if i > maxJump and dp[i - maxJump - 1]:
            prevReach -= 1
        dp[i] = prevReach > 0 and s[i] == "0"
    return dp[-1]

Leetcode 1727. Largest Submatrix With Rearrangements

Leetcode: https://leetcode.com/problems/largest-submatrix-with-rearrangements/

  • Count continuous 1s above current cell
  • Since we can move columns, we can sort each row
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def largestSubmatrix(self, matrix: List[List[int]]) -> int:
    dp = [[0 for _ in range(len(matrix[0]) + 1)] for _ in range(len(matrix) + 1)]
    for n in range(len(matrix)):
        for m in range(len(matrix[0])):
            i = n + 1
            j = m + 1
            if matrix[n][m] == 0:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i - 1][j] + matrix[n][m]
    res = 0
    for row in dp:
        row.sort()
        cnt = 0
        for i, height in enumerate(row):
            res = max(res, height * (len(row) - i))
    return res

Interval

Interval question

设计2个method 一个是insert_interval 比如把(30, 40)加到一个list里 另一个是给一个number判断是不是在现有的范围内。 可以认为所有interval都是不交叉的.
优化1：怎么优化list的insert操作
优化2：如果有billion级别的request 怎么处理

Meeting room

Merge Intervals with Price

Similar problem: Leetcode 218. The Skyline Problem

1
2
# input: [[1, 5, 5], [2, 10, 10], [4, 6, 2]]
# output: [[1, 4, 5], [4, 6, 2], [6, 10, 10]]

intervals 和 dots

像meeting room那种 intervals = [[1,5],[3,7],[9,15], [10,13] 表示数轴上的一段段区间
dots就是一系列点 比如[2,3,6,8,10,15]

问你每个点在几个区间里
比如输入的是[2,3,6,8,10,15] 就返回[1, 2, 6, 0, 2, 1]

两个follow up
一个是有有字母怎么处理 比如在intervals加上区间[‘b’, ‘g’] [‘k’,’p’] 然后输入里加上例如 [‘a’,’f’,’l’]
第二个是输入的点变为小数怎么处理

https://www.1point3acres.com/bbs/thread-789210-1-1.html

Geometry

Rectangle nodes

给一个类代表一个节点，里面有val 有它相邻的node。 这样的nodes 最后会组成一个长方体puzzle 的结构， 类似于：(我给的是正方形，但不一定是)
a-b-c
| | |
f-g-h
| | |
i-m-n
返回 长宽

经典给横线竖线数正方形的问题

输入是一堆线段，找所有可以形成的正方形的数量，自己设计数据结构和算法。clarify之后如下，平面无限大，线段都是水平或者竖直，不会cross，但端点可能在另一个线段上。解法大概是枚举对角线，然后check四条边，但是不能直接check每一条边是不是在input 的线段当中，因为可能正方形的一条边是由多个input线段组成的，或者完全被包含在某一个线段当中，所以需要对所有x和y值建segment tree，然后每一个查四条边是不是完全被当前坐标的segment tree cover

判断array中是否存在构成直角三角形

follow up: 1. 返回所有情况 2. 返回所有重复情况, 按不同组合打印

Cluster points

给你N (2D) points.
如果两pts的距离 <= k, 组合在一起

Design

设计数据结构to read stream of ints.

返回last k ints 平均值. (简单)
返回last k ints mode. (难)

设计消消乐

初始不能有3个连着的，但可以通过swap 开局且保证一定有解法能赢. follow up:设计API给予最优解法的提示； follow up2:开放式问题，如何设计分级难度，谈一下想法就行

Graph

Leetcode 1293. Shortest Path in a Grid with Obstacles Elimination

Leetcode https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

DFS + backtracking Solution: TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def shortestPath(self, grid: List[List[int]], k: int) -> int:
    dp = [[float('inf') for _ in range(len(grid[0]))] for _ in range(len(grid))]
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    def canVisit(i, j, k, totalSteps, visited):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or (i, j) in visited:
            return False
        if grid[i][j] == 1 and k == 0:
            return False
        return True
    def dfs(i, j, leftObs, minSteps, visited):
        nonlocal dp
        
        if not canVisit(i, j, leftObs, minSteps, visited):
            return
        dp[i][j] = min(dp[i][j], minSteps)
        
        if grid[i][j] == 1:
            leftObs -= 1
        visited.add((i, j))
        for d in directions:
            newi, newj = i + d[0], j + d[1]
            dfs(newi, newj, leftObs, minSteps + 1, visited)
        if grid[i][j] == 1:
            leftObs += 1
        visited.remove((i, j))
    dfs(0, 0, k, 0, set())
    if dp[-1][-1] == float('inf'):
        return -1
    return dp[-1][-1]

BFS Solution

Time Complexity: O(m n k)
Space: O(m n k)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def shortestPath(self, grid: List[List[int]], k: int) -> int:
    if len(grid) == 1 and len(grid[0]) == 1:
        return 0
    
    if k >= len(grid) + len(grid[0]) - 2:
        return len(grid) + len(grid[0]) - 2
    
    queue = deque([[0, 0, k, 0]])
    visited = set([(0, 0, k)])
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    def canVisit(i, j):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]):
            return False
        return True
    
    while queue:
        i, j, leftObs, steps = queue.popleft()
        
        
        for d in directions:
            newi, newj = i + d[0], j + d[1]
            
            if not canVisit(newi, newj):
                continue
                
            if grid[newi][newj] == 1 and leftObs > 0 and (newi, newj, leftObs - 1) not in visited:
                visited.add((newi, newj, leftObs - 1))
                queue.append([newi, newj, leftObs - 1, steps + 1])
            elif grid[newi][newj] == 0 and (newi, newj, leftObs) not in visited:
                if newi == len(grid) - 1 and newj == len(grid[0]) - 1:
                    return steps + 1
                visited.add((newi, newj, leftObs))
                queue.append([newi, newj, leftObs, steps + 1])
    return -1

undirected graph

假如有一个五香图，你只知道起始点，且你每次传递到下一个点时，（a ->b） b只有a的信息，不知道a以前的信息，问：怎么遍历全图。
其他题都是面经常见题

划分成4个部分

一个m行n列的整数矩阵，问可以有多少种方法将其划分成4个部分，使得每个部分的和相同 ？

n x m matrix of ints.

给你 n x m matrix of ints.
从第一排开始 (any column).
你能到最后一排吗?
从mat[i][j]，你只能移动到 mat[r][c] s.t. mat[r][c] = mat[i][j] OR mat[r][c] = -mat[i][j] OR mat[r][c] = mat[i][j]^2.
FU: 找到最小的 path cost. Path cost = sum(mat[i][j] over all (i, j) in path)

打印环

判断图中是否有环

Monotonic Stack

Leetcode 1504. Count Submatrices With All Ones

Leetcode: https://leetcode.com/problems/count-submatrices-with-all-ones/

Trie

Leetcode 792. Number of Matching Subsequences

API(string word) instead of list of word, return true/false

Leetcode 153. Find Minimum in Rotated Sorted Array

Leetcode: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

1
2
3
4
5
6
7
8
9
def findMin(self, nums: List[int]) -> int:
    l, r = 0, len(nums) - 1
    while l < r:
        mid = (l + r) // 2
        if nums[mid] > nums[-1]:
            l = mid + 1
        else:
            r = mid
    return nums[l]

Followup 154.

给一个list 包含很多问题，要从中随机抽k个问题生成试卷。

follow up: 如果问题是有easy medium hard 难度，保证生成的试卷问题难度要平均。

给一个正方形矩阵

给一个正方形矩阵，里面都是正数或0，正数代表金矿的数量，你可以选择任何一个整数作为起点，给出可以拿到的最多的金矿，不能往回走。行走只有四个方向，上下左右。
例子：下面例子可以选取 2 2 4 5 6 7 3 4，总和达到最大值。
0 1 0 3 4
2 2 0 7 0
0 4 5 6 2
0 0 0 0 0
0 2 0 0 2
输入中，正数不会形成cycle，比如见不到先面的case
2 3
1 4
开始忘记cycle这件事儿了，后来提示我没有cycle，典型的memory search。遗憾的是，第一题可能花时间比较久（或者是找会议室浪费了时间），没写完这个题，只写了一半，倒是给他解释清楚了该怎么做记忆化搜索。

Leetcode 133. Clone Graph

Leetcode: https://leetcode.com/problems/clone-graph/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def cloneGraph(self, node: 'Node') -> 'Node':
    # clone node: clone value, clone neighbs
    cloned = collections.defaultdict(Node)
    def cloneNode(node):
        nonlocal cloned
        if not node:
            return None
        if node.val in cloned:
            
            return cloned[node.val]
        # print(node.val)
        newNode = Node(node.val)
        cloned[node.val] = newNode
        for neib in node.neighbors:
            newNode.neighbors.append(cloneNode(neib))
        return newNode
    return cloneNode(node)

Leetcode 207

Leetcode: https://leetcode.com/problems/course-schedule/

Topic: Topological sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
    indegrees = [0 for _ in range(numCourses)]
    graph = collections.defaultdict(list)
    for cur, pre in prerequisites:
        indegrees[cur] += 1
        graph[pre].append(cur)
    
    queue = []
    for i in range(len(indegrees)):
        if indegrees[i] == 0:
            queue.append(i)
    visited = set()
    
    while queue:
        cur = queue.pop(0)
        visited.add(cur)
        for neib in graph[cur]:
            indegrees[neib] -= 1
            if indegrees[neib] == 0:
                queue.append(neib)
    
    # print(queue)
    if len(visited) != numCourses:
        return False
    return True

Leetcode 299. Bulls and Cows

Leetcode: https://leetcode.com/problems/bulls-and-cows/

digits in correct position / correct number but in wrong position
guess hint

Insertion Sort

题目先是一个数组 [1,5,-100, -99, 2, -1] 怎么样让正的都在左边，负的都在右边，类似刷题网起舞。然后follow up问怎么样O（1）空间复杂度sort，并且保证正数和负数的相对位置不变。

Leetcode 1428. Leftmost Column with at Least a One

Leetcode: https://leetcode.com/problems/leftmost-column-with-at-least-a-one/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
    n, m = binaryMatrix.dimensions()
    # maybe do binary search in each row to find the smallest index of 1
    def bsearch(row):
        # binary search in a row
        # return index of the leftmost 1
        if binaryMatrix.get(row, m - 1) == 0:
            # no 1 in current row
            return -1
        l, r = 0, m - 1
        while l < r:
            mid = (l + r) // 2
            if binaryMatrix.get(row, mid) == 0:
                l = mid + 1
            else:
                r = mid
        return l
    res = float('inf')
    for i in range(n):
        found = bsearch(i)
        # print(found)
        if found >= 0:
            res = min(res, found)
    if res == float('inf'):
        return -1
    return res

Leetcode 715. Range Module

Leetcode: https://leetcode.com/problems/range-module/

替换后最长的continuous non-decreasing subarray

给出一个int array, 可以将其中的一个int 替换成其它数组中已有的值。 return 替换后最长的continuous non-decreasing subarray
例子
[1, 7, 7, 2, 5, 4] 可以将7 换成2 得到的subarray 是[1, 2, 2, 2, 5] 最长

Leetcode 1110

Leetcode: https://leetcode.com/problems/delete-nodes-and-return-forest/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
    # [root]
    # deleting leaf: parent.child = None
    # deleting non-leaf: append left and right child
    # deleting nodes on the same tree: replace parent with 2 children
    res = set()
    res.add(root)
    
    def delete(parent, node, direction):
        nonlocal res
        
        # reset parent's pointers
        if direction == 'left':
            parent.left = None
        elif direction == 'right':
            parent.right = None
        
        # append child to result
        if node in res:
            res.remove(node)
        if node.left:
            res.add(node.left)
        if node.right:
            res.add(node.right)
    
    idToNode = collections.defaultdict(TreeNode)
    
    stack = [(None, root, '')]
    while stack:
        par, cur, direction = stack.pop()
        idToNode[cur.val] = (cur, par, direction)
        if cur.left:
            stack.append((cur, cur.left, 'left'))
        if cur.right:
            stack.append((cur, cur.right, 'right'))
    # print(idToNode)
    for index in to_delete:
        delete(idToNode[index][1], idToNode[index][0], idToNode[index][2])
        
    return list(res)

875. Koko Eating Bananas

Leetcode: https://leetcode.com/problems/koko-eating-bananas/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def minEatingSpeed(self, piles: List[int], h: int) -> int:
    # max of k: max(piles)
    # min of k: 1
    # hours = piles[i] // k, if piles[i] % k > 0: hours += 1
    # binary search
    # if sum(hours) > h: k++; elif sum(hours) < h: k--
    def getHour(bite):
        res = 0
        for pile in piles:
            hour = pile // bite
            if pile % bite > 0:
                hour += 1
            res += hour
        return res
    l, r = 1, max(piles)
    while l < r:
        mid = (l + r) // 2
        if getHour(mid) > h:
            # increase bite size
            l = mid + 1
        else:
            r = mid
    return l

759. Employee Free Time

Leetcode: https://leetcode.com/problems/employee-free-time/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
    # construct a long list with all the intervals sorted by start
    # since it's sorted, we can use pointers to each schedule lists
    # use prioirty queue to sort
    pointers = [0 for _ in range(len(schedule))]
    fullList = []
    heap = []
    # initialize heap
    for i, p in enumerate(pointers):
            heapq.heappush(heap, (schedule[i][p].start, schedule[i][p].end, i, p))
    while heap:
        start, end, person, pointer = heappop(heap)
        if pointers[person] + 1 < len(schedule[person]):
            
            pointers[person] += 1
            # print(pointers, person)
            curPtr = pointers[person]
            heapq.heappush(heap, (schedule[person][curPtr].start, schedule[person][curPtr].end, person, curPtr))
        
        # merge into fullList
        if not fullList or fullList[-1][1] < start:
            fullList.append([start, end])
        else:
            fullList[-1][1] = max(end, fullList[-1][1])

    # go through the list and find out the gaps
    res = [Interval(-float('inf'), float('inf'))]
    for interval in fullList:
        res[-1].end = interval[0]
        res.append(Interval(interval[1], float('inf')))
    res.pop()
    return res[1:]

1673. Find the Most Competitive Subsequence

Leetcode: https://leetcode.com/problems/find-the-most-competitive-subsequence/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
    # base case: k = 0: [], k = 1: smallest
    # k = 2: firstNum: smallest: a, secondNum: smallest after a
    # k = 3: firstNum: smallest: a, s
    # duplicate numbers: always use the leftmost one: maximize potential pool of candidates

    heap = []
    res = []
    for i in range(len(nums) - k + 1):
        heapq.heappush(heap, (nums[i], i))
    lastPtr = len(nums) - k + 1
    smallIndex = -1  
    while k > 0:
        # only count numbers to the right of the current smallestInHeap
        smallestInHeap, index = heappop(heap)
        while heap and index <= smallIndex:
            smallestInHeap, index = heappop(heap)
            
        smallIndex = index
        res.append(smallestInHeap)
        if lastPtr < len(nums):
            
            heappush(heap, (nums[lastPtr], lastPtr))
            lastPtr += 1
        k -= 1
    return res

284. Peeking Iterator

Leetcode: https://leetcode.com/problems/peeking-iterator/

Note: peek doesn’t mean we cannot call iterator.next()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class PeekingIterator:
    def __init__(self, iterator):
        """
        Initialize your data structure here.
        :type iterator: Iterator
        """
        self.iterator = iterator
        self.prev = None

    def peek(self):
        """
        Returns the next element in the iteration without advancing the iterator.
        :rtype: int
        """
        if not self.iterator.hasNext():
            raise Exception("Iterator has reached to the end")
            
        if self.prev == None:
            num = self.iterator.next()
            self.prev = num
            return num
        return self.prev

    def next(self):
        """
        :rtype: int
        """
        if not self.hasNext():
            raise Exception("Iterator has reached to the end")
            
        if self.prev != None:
            res = self.prev
            self.prev = None
            return res
        
        return self.iterator.next()

    def hasNext(self):
        """
        :rtype: bool
        """
        return self.iterator.hasNext()

Iterator

假设给你一个字符串的iterator，如何实现一个iterator，通过调用hasNext和next可以返回字符串的统计信息。
例子：
逐个string iterator返回的内容为：”a”, “a”, “a”, “b”, “a”
你实现的iterator每个next应该返回：, ,

无向图， 要求找一条路径， 不重复edge地走过所有顶点， 如果不存在返回一个空array

给一个string，只包含数字， 比如：“1573829”， 返回所有index i， 要求满足 input[i] = i 。 比如例子里的 3 在 input[3] 上，就是需要返回的。 对于index超过9 的， 比如index = 10， 则需要满足 input[10] = ’1‘， input[11] = ‘0’, 则算满足条件。

给一个初始数字和一个mod， 然后每次 求出这个数字每一位的和然后对mod求余得到一个新的数字， 重复这个过程直到出现环。 给定一个range [min, max] 对每个range中的数字都做一遍上述操作，求每个数字做这种变化的workflow中有多少个unique number， 输出一个map 对应的是（unique number 的个数，list of original number in [min, max]）