Coding interviews
Reveal answer and reasoning
A route API can declare metric kind, reject unsupported negative weights and return a named unreachable outcome rather than a magic numeric distance. For actual path results, retain predecessors and specify tie ordering. Dijkstra can serve nonnegative weighted distance under its usual assumptions; selecting it does not excuse missing validation or overflow handling.
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. 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.
The interview value is recognizing an underspecified objective before implementing another familiar algorithm. The sample reuses BFS mechanics only to construct a concrete disagreement: one hop costs ten, while two hops cost two. A correct explanation labels both quantities and never attributes the weighted result to BFS. A senior answer then asks about negative edges, unreachable nodes, cost accumulation and path ties.
Those contract choices are prerequisites to a useful implementation. Existing weighted-algorithm lessons provide mechanics once the problem has actually selected the metric they solve.
What a strong answer covers
- A route API can declare metric kind, reject unsupported negative weights and return a named unreachable outcome rather than a magic numeric distance.
- BFS uses O(V+E) time and O(V) discovered-state storage for the reachable graph, assuming ordinary set operations.
- Adding weights to an input record while retaining first-discovery BFS distances does not preserve minimum-total-cost correctness.
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.