Implement BFS to Find Shortest Path in Graph
Company: Amazon
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Scenario
Social network needs to compute the shortest friend-distance between two users in an undirected graph containing millions of nodes.
##### Question
Implement an iterative BFS that returns the minimum number of hops between a source and target user. Extend the function to also return one of the actual shortest paths.
##### Hints
Use a queue, visited set, and early exit when target is found.
Quick Answer: This question evaluates understanding of graph traversal algorithms, particularly breadth-first search, and competency in computing shortest paths and reconstructing an example shortest route in large undirected graphs.
Given an undirected, unweighted graph with n nodes labeled 0..n-1 and a list of edges edges where each edge is [u, v], implement an iterative BFS that returns the minimum number of hops (edges) between source and target and one corresponding shortest path. Return a dictionary: {"distance": d, "path": p}. If target is unreachable, return {"distance": -1, "path": []}. The path must start at source and end at target. If source == target, return {"distance": 0, "path": [source]}.
Constraints
- 1 <= n <= 200000
- 0 <= len(edges) <= 400000
- 0 <= u, v < n for every edge [u, v]
- 0 <= source, target < n
- Graph is undirected and may be disconnected
- Implement iterative BFS using a queue (no recursion)
- Return one shortest path; if none exists, return distance -1 and empty path
Solution
from collections import deque
def shortest_friend_path(n, edges, source, target):
# Trivial case
if source == target:
return {"distance": 0, "path": [source]}
# Build adjacency list
adj = [[] for _ in range(n)]
for e in edges:
if not isinstance(e, (list, tuple)) or len(e) != 2:
continue
u, v = e
if not isinstance(u, int) or not isinstance(v, int):
continue
if not (0 <= u < n and 0 <= v < n):
continue
adj[u].append(v)
if u != v: # avoid duplicating self-loop
adj[v].append(u)
visited = [False] * n
parent = [-1] * n
dq = deque([source])
visited[source] = True
while dq:
u = dq.popleft()
for v in adj[u]:
if not visited[v]:
visited[v] = True
parent[v] = u
if v == target: # early exit upon discovery
# Reconstruct path from target to source via parents
path = [v]
while path[-1] != source:
path.append(parent[path[-1]])
path.reverse()
return {"distance": len(path) - 1, "path": path}
dq.append(v)
return {"distance": -1, "path": []}Explanation
Breadth-first search (BFS) explores the graph layer by layer, guaranteeing that the first time we discover the target we have found a shortest path in an unweighted graph. We maintain a predecessor array to reconstruct the path by backtracking from the target to the source. We also keep a visited array to avoid revisiting nodes. We exit early as soon as the target is discovered to minimize work.
Time complexity: O(n + m), where n is the number of nodes and m is the number of edges. Space complexity: O(n + m) for adjacency list, visited, and parent arrays.
Hints
- Use a queue and a visited structure to explore nodes level by level.
- Track each node's predecessor to reconstruct the path once the target is found.
- You can stop the BFS as soon as the target is discovered; distance is path length minus one.