Google | Onsite interview | Find princess
Anonymous User
813
Graph TheoryGoogleInterview

Given a undirected graph with V nodes and E edges. All nodes numbered from 1...N
Node have 3 parameters:

  1. Value of node
  2. Key to unlock path between u and v
  3. Children

The struct of Node looks like that:

class Node:
	def __init__(self, value:int, key:int, child:list):
		self.value = value
		self.key = key
		self.child = child

The question is, some edges (aka path) locked with some key. Try to start from node 1 and try to reach node N using keys which you can have traversing by neighbors.

Return True if it possible to reach Nth node in the graph, otherwise return False.

Example 1:

1/(1) means 1 value of node, (1) key in the node

  /
(1)
/  means, you should unlock edge between 1 and 2 via key (1)

				  [1/(1)]
				/         \
			  (1)          (2)
			   /             \
			[2/(2)]         [3/(5)]
								\
								(5)
									\
									[4/(3)]
			
return True

Example 2:

				[4/(2)]
				/(4)
			[1/(3)] <- starting node
			/(2)    \(3)
		[3/(4)]    [2/(1)]

return False  # it could be because there is no key to unclock path from  node1 to node3

Expected time complexity: O(E + V)

My solution O(V * E) in the worst case, I guess. 
class Node:
	def __init__(self, data, key, children):
		self.data = data
		self.key = key
		self.children = children
 
 
def find_princess(N, graph, start_node):
	queue = collections.deque([start_node])
	keys, visited = set([start_node.key]), set([start_node])
 
	while queue:
		new_node_added = False
		for node in queue:
			if node.val == N:
				return True
 
			for neighbor in graph[node].children:
				if neighbor.key in keys and neighbor not in visited:
					queue.append(neighbor)
					keys.add(neighbor.key)
					visited.add(neighbor)
					new_node_added = True
 
		if not new_node_added:
			break
 
	return False
Comments (5)