Coding interviews
Reveal answer and reasoning
The question shortest path is incomplete until the objective is specified. BFS minimizes edge count when each traversed edge contributes the same unit cost. In this counterexample a direct edge has one hop but cost ten, while a two-edge path costs one plus one. The program demonstrates the disagreement rather than presenting another full weighted shortest-path implementation. Ask whether every edge represents the same unit, whether costs may be negative and whether the caller wants a distance or an actual path.
Those answers determine both the algorithm and the return contract. A route with fewer transitions is not necessarily cheaper, faster or safer unless the chosen metric says so.
BFS uses O(V+E) time and O(V) discovered-state storage for the reachable graph, assuming ordinary set operations. Nonnegative weighted costs require an appropriate weighted algorithm such as Dijkstra; negative edges require different assumptions. No priority queue can repair a missing definition of the path objective. The V-plus-E bound describes the reachable adjacency representation, not arbitrary network exploration. Storing predecessor links would add another O(V) structure but allow reconstruction of a path.
Weighted accumulated costs also need a numeric bound and overflow policy beyond the integer hop count of this tiny graph.
What a strong answer covers
- The question shortest path is incomplete until the objective is specified.
- Marking a node seen when it is enqueued avoids repeated BFS expansion and preserves the first-discovered minimum hop count for unit edges.
- BFS uses O(V+E) time and O(V) discovered-state storage for the reachable graph, assuming ordinary set operations.
Common pitfall
Adding weights to an input record while retaining first-discovery BFS distances does not preserve minimum-total-cost correctness. Reusing the word shortest for both outputs conceals that contract change. The example also does not validate dangling adjacency names or handle an unbounded externally supplied graph.
Follow-up questions
- Change the direct cost to two and explain the remaining tie between one-hop and two-hop routes. Hint: equal total cost still leaves an output tie policy if the API returns a path rather than only a distance.
- How would negative edge weights or a reachable negative cycle change the route contract?
Self-review
Choose what to revisit. These marks are your own assessment and are separate from lesson completion.