Shortest Distance After Road Addition Queries I

Shortest Distance After Road Addition Queries I

What is this problem about?

The Shortest Distance After Road Addition Queries I interview question gives you n cities numbered 0 to n-1, initially connected in a chain (0→1→2→...→n-1). You receive a series of road-addition queries, each adding a directed shortcut edge (u, v). After each query, compute the shortest path from city 0 to city n-1 using BFS (since all edges have unit weight). Return an array of shortest distances, one per query.

Why is this asked in interviews?

Microsoft and Google ask this problem because it tests incremental graph construction with BFS re-evaluation — a pattern common in dynamic network analysis, routing algorithm updates, and transportation planning. It evaluates whether candidates can efficiently maintain and re-query a shortest path after structural changes, and whether they understand that BFS (not Dijkstra) is optimal for unweighted graphs.

Algorithmic pattern used

The pattern is incremental BFS after each graph modification. Maintain an adjacency list initialized with the chain edges (i → i+1 for all i). For each query (u, v), add the edge u → v to the adjacency list. Then run BFS from node 0 to find the shortest path to node n-1. Append the BFS result to the answer array. Since each BFS is O(n + m) and there are q queries, total time is O(q × (n + m)).

Example explanation

n = 5. Initial edges: 0→1, 1→2, 2→3, 3→4. Initial shortest path: 4.

Query [2,4]: add edge 2→4. BFS from 0: 0→1→2→4. Distance = 3. Query [0,2]: add edge 0→2. BFS from 0: 0→2→4. Distance = 2.

Result: [3, 2].

Common mistakes candidates make

• Using Dijkstra for an unweighted graph — BFS is simpler and equally correct for unit-weight edges.
• Not persisting added edges between queries — each new edge is cumulative; don't reset the graph between queries.
• Reinitializing the adjacency list on every query — only add the new edge, keeping all previously added edges.
• Not checking if the destination n-1 is reachable (though for this problem structure it always is from 0).

Interview preparation tip

For the Shortest Distance After Road Addition Queries I coding problem, the BFS graph interview pattern with incremental graph updates is the approach. The simplest implementation: use an adjacency list, add one edge per query, and re-run BFS. Microsoft and Google interviewers may ask about optimization for Part II (many queries) — know that for large query sets, more advanced techniques like LCT (link-cut trees) or Dijkstra with priority queues can improve performance. For this variant, clean BFS implementation is sufficient and expected.