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.
Overview: 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
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.