Google Interview Question
SDE1sCountry: United States
1. Identify special nodes in matrix ("2", "3", "a", "A" ...)
2. Build graph for these special node (BFS for node edges)
3. Find shortest path from "2" to "3" in the graph
Simple BFS shortest path algorithm does not work since path has dependency
Use DFS to find shortest path, easy to check key->door dependency
4. Reconstruct path
import sys
"""
'0' : water
'1' : land (can walk)
'a' : key of 'A'
'A' : door require key 'a'
"""
def get_path(prev, i, j):
path = []
path.append((i, j))
while prev[i][j] != (-1, -1):
i, j = prev[i][j]
path.append((i, j))
path.pop() # pop src idx
return path[::-1]
def get_edges(matrix, s_node, src, t_node):
bfs = collections.deque([src, (None, None)])
parent = [[None]*len(matrix[0]) for _ in xrange(len(matrix))]
parent[src[0]][src[1]] = (-1, -1)
d = 1
edge = {}
while bfs:
i, j = bfs.popleft()
if i == None:
d += 1
if bfs:
bfs.append((None, None))
else:
for n_i, n_j in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
if (0 <= n_i < len(matrix) and 0 <= n_j < len(matrix[0]) and
parent[n_i][n_j] == None):
parent[n_i][n_j] = (i, j)
if matrix[n_i][n_j] in t_node:
edge[matrix[n_i][n_j]] = get_path(parent, n_i, n_j)
if len(edge) == len(t_node) - 1:
break
elif matrix[n_i][n_j] == "1":
bfs.append((n_i, n_j))
return edge
def shortest_path(path, cost, node, dst, result):
if path[-1] == dst:
print(path, cost)
if cost < result[0]:
result[0] = cost
result[1] = path[:]
return
cur = path[-1]
for ne in node[cur].keys():
if ne not in path:
if (ord("A") <= ord(ne) <= ord("Z") and
chr(ord(ne) - ord("A") + ord("a")) not in path):
continue
next_cost = cost + len(node[cur][ne])
if next_cost >= result[0]:
continue
path.append(ne)
shortest_path(path, cost + len(node[cur][ne]), node, dst, result)
path.pop()
def key_path(matrix):
# 1. find all special node
# 2. Build graph of all special node (search shortest path between nodes)
# 3. Find shortest path of the graph (DFS)
# 1. find all nodes
node = {}
node_pos = {}
for i in xrange(len(matrix)):
for j in xrange(len(matrix[0])):
if matrix[i][j] not in ['0', '1']:
node[matrix[i][j]] = {}
node_pos[matrix[i][j]] = (i,j)
# 2. find edge of nodes
for n in node.keys():
node[n] = get_edges(matrix, n, node_pos[n], node.keys())
# 3. do shortest path from src to dst
#path = shortest_path(node, "2", "3")
result = [sys.maxint, []]
shortest_path(["2"], 0, node, "3", result)
path = result[1]
print(path)
# combine path
total_path = [node_pos["2"]]
for i in xrange(1, len(path)):
total_path += node[path[i-1]][path[i]]
print(total_path)
return total_path
matrix = [["0", "2", "1", "1", "1"],
["0", "1", "a", "C", "0"],
["0", "1", "b", "B", "1"],
["1", "1", "c", "0", "3"],
["0", "A", "1", "1", "1"]]
key_path(matrix)
1. Identify special nodes in matrix ("2", "3", "a", "A" ...)
2. Build graph for these special node (BFS for node edges)
3. Find shortest path from "2" to "3" in the graph
Simple BFS shortest path algorithm does not work since path has dependency
Use DFS to find shortest path, easy to check key->door dependency
4. Reconstruct path
import sys
"""
'0' : water
'1' : land (can walk)
'a' : key of 'A'
'A' : door require key 'a'
"""
def get_path(prev, i, j):
path = []
path.append((i, j))
while prev[i][j] != (-1, -1):
i, j = prev[i][j]
path.append((i, j))
path.pop() # pop src idx
return path[::-1]
def get_edges(matrix, s_node, src, t_node):
bfs = collections.deque([src, (None, None)])
parent = [[None]*len(matrix[0]) for _ in xrange(len(matrix))]
parent[src[0]][src[1]] = (-1, -1)
d = 1
edge = {}
while bfs:
i, j = bfs.popleft()
if i == None:
d += 1
if bfs:
bfs.append((None, None))
else:
for n_i, n_j in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
if (0 <= n_i < len(matrix) and 0 <= n_j < len(matrix[0]) and
parent[n_i][n_j] == None):
parent[n_i][n_j] = (i, j)
if matrix[n_i][n_j] in t_node:
edge[matrix[n_i][n_j]] = get_path(parent, n_i, n_j)
if len(edge) == len(t_node) - 1:
break
elif matrix[n_i][n_j] == "1":
bfs.append((n_i, n_j))
return edge
def shortest_path(path, cost, node, dst, result):
if path[-1] == dst:
print(path, cost)
if cost < result[0]:
result[0] = cost
result[1] = path[:]
return
cur = path[-1]
for ne in node[cur].keys():
if ne not in path:
if (ord("A") <= ord(ne) <= ord("Z") and
chr(ord(ne) - ord("A") + ord("a")) not in path):
continue
next_cost = cost + len(node[cur][ne])
if next_cost >= result[0]:
continue
path.append(ne)
shortest_path(path, cost + len(node[cur][ne]), node, dst, result)
path.pop()
def key_path(matrix):
# 1. find all special node
# 2. Build graph of all special node (search shortest path between nodes)
# 3. Find shortest path of the graph (DFS)
# 1. find all nodes
node = {}
node_pos = {}
for i in xrange(len(matrix)):
for j in xrange(len(matrix[0])):
if matrix[i][j] not in ['0', '1']:
node[matrix[i][j]] = {}
node_pos[matrix[i][j]] = (i,j)
# 2. find edge of nodes
for n in node.keys():
node[n] = get_edges(matrix, n, node_pos[n], node.keys())
# 3. do shortest path from src to dst
#path = shortest_path(node, "2", "3")
result = [sys.maxint, []]
shortest_path(["2"], 0, node, "3", result)
path = result[1]
print(path)
# combine path
total_path = [node_pos["2"]]
for i in xrange(1, len(path)):
total_path += node[path[i-1]][path[i]]
print(total_path)
return total_path
matrix = [["0", "2", "1", "1", "1"],
["0", "1", "a", "C", "0"],
["0", "1", "b", "B", "1"],
["1", "1", "c", "0", "3"],
["0", "A", "1", "1", "1"]]
key_path(matrix)
- Dhruva.Bharadwaj May 16, 2017