Design Graph With Shortest Path Calculator

Design Graph With Shortest Path Calculator

1. What is this problem about?

The Design Graph With Shortest Path Calculator interview question involves building a class that manages a directed, weighted graph. You need to support adding new edges dynamically and querying the shortest path between any two nodes. This Design Graph With Shortest Path coding problem is a test of pathfinding algorithm implementation and system efficiency under mixed read/write loads.

2. Why is this asked in interviews?

Samsung and Nike ask this to evaluate your mastery of Graph interview patterns, specifically Dijkstra’s Algorithm or Floyd-Warshall. It tests whether you can choose the right algorithm based on how often edges are added versus how often shortest paths are queried. It evaluates your knowledge of Heap (Priority Queue) interview patterns for optimization.

3. Algorithmic pattern used

• Adjacency List: To store the graph structure.
• Query Shortest Path: Use Dijkstra’s Algorithm starting from the source node. Since weights are non-negative, Dijkstra with a Min-Priority Queue is the standard $O(E \log V)$ choice.
• Update Edge: Just add the edge to the adjacency list ($O(1)$).
• Alternative (Floyd-Warshall): If shortest path queries are extremely frequent and the graph is small, you could maintain a 2D matrix of all-pairs shortest paths and update it in $O(V^2)$ when an edge is added.

4. Example explanation

1. addEdge(0, 1, 5), addEdge(1, 2, 10), addEdge(0, 2, 20).
2. shortestPath(0, 2):
   • Path A: 0 -> 2 (weight 20).
   • Path B: 0 -> 1 -> 2 (weight 15).
   • Dijkstra returns 15.
3. addEdge(0, 2, 2):
4. shortestPath(0, 2): Dijkstra now returns 2.

5. Common mistakes candidates make

• Using BFS for weights: Forgetting that Breadth-First Search only works for unweighted graphs.
• Inefficient Dijkstra: Using a simple list instead of a Priority Queue, making the query $O(V^2)$.
• State Management: Not resetting the "visited" or "distance" arrays between different queries.

6. Interview preparation tip

Always discuss the tradeoffs! If the interviewer says edges are added rarely, suggest Floyd-Warshall for $O(1)$ queries. If edges are added often, Dijkstra is much better. Being able to analyze these scenarios shows senior-level architectural thinking.