Google High Frequency Summary

Catalogue
  1. 1. DP
    1. 1.1. Matrix Path
  2. 2. Graph -> Tree
    1. 2.1. 684. Redundant Connection
    2. 2.2. 685. Redundant Connection II
  3. 3. Other
    1. 3.1. 843. Guess the Word
  4. 4. DFS
    1. 4.1. Remove Marble

DP

Matrix Path

from (0, 0) to (0, n-1), traverse to right, right bottom and right top!

  • Follow Up1 : Must go through some points
  • Follow Up2 : Must go through a certain height

Graph -> Tree

Redundant Connection

684. Redundant Connection

Undirected Graph!

  1. Union Find
  • when the inputs are edges, you do not need to construct the graph
  • path compression, but how about the balanced part?
  1. DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def findRedundantConnection(self, edges):
        root = range(1001)

        def find(x):
            if root[x] == x:
                return x
            root[x] = find(root[x])
            return root[x]

        for i, j in edges:
            rooti = find(i)
            rootj = find(j)
            if rooti == rootj:
                return [i, j]
            root[rooti] = rootj

685. Redundant Connection II

Directed Graph

  1. Case1: There is a loop in the graph, and no vertex has more than 1 parent.
  • => Union Find
  1. Case2: A vertex has more than 1 parent, but there isn’t a loop in the graph.
  • => last node (indegree > 1)
  1. Case3: A vertex has more than 1 parent, and is part of a loop.
  • Delete the second edge!
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
class Solution(object):
    def findRedundantDirectedConnection(self, edges):
        n = len(edges)
        parent = [0] * (n+1)
        ans = None
        # Step1 : find the node with indegree > 1
        for i in xrange(n):
            u, v  = edges[i]
            if parent[v] == 0:
                parent[v] = u
            else:
                ans = [[parent[v], v], [u, v]]
                # !!! Delete the second Edge
                edges[i][1] = 0

        # Step2 : Union Find detect cycle
        root = range(n+1)
        def find(x):
            if root[x] == x:
                return x
            return find(root[x])

        for u, v in edges:
            rootu = find(u)
            rootv = find(v)
            if rootu == rootv: # Detect Cycle
                if not ans:
                    return [u, v]
                else:
                    return ans[0]
            root[rootu] = rootv
        return ans[1]

Other

843. Guess the Word

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def match(self, s1, s2):
        matches = 0
        for i in range(len(s1)):
            if s1[i] == s2[i]:
                matches += 1
        return matches

    def findSecretWord(self, wordlist, master):
        cnt = 10
        while cnt:
            guessWord = random.choice(wordlist)
            matches = master.guess(guessWord)
            newList = []
            for word in wordlist:
                if self.match(guessWord, word) == matches:
                    newList.append(word)
            wordlist = newList
            cnt -= 1

DFS

Remove Marble

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
def dfs(board, x, y, row_visited, col_visited):
    m, n = len(board), len(board[0])
    if x in row_visited and y in col_visited:
        return False

    if x not in row_visited:
        row_visited.add(x)
        for j in range(n):
            if board[x][j] == 1:
                dfs(board, x, j, row_visited, col_visited)

    if y not in col_visited:
        col_visited.add(y)
        for i in range(m):
            if board[i][y] == 1:
                dfs(board, i, y, row_visited, col_visited)
    return True

def remove_number(board):

	cnt = 0 # Count the number of marble
	m, n = len(board), len(board[0])

	# Count the number of cluster
	row_visited = set()
	col_visited = set()
	cluster = 0
	for i in range(m):
		for j in range(n):
			if board[i][j] == 1:
				cnt += 1
				if dfs(board, i, j, row_visited, col_visited):
				    cluster += 1
	return cnt - cluster



board = [[1, 0, 0, 0],
        [0, 1, 0, 1],
        [0, 0, 0, 1],
        [0, 0, 1, 0]]
print(remove_number(board))
Share