Shortest Path And Graph Traversal
Asked of: Software Engineer
Last updated

What's being tested
These problems test graph modeling, shortest-path selection, and traversal correctness under different input shapes: grids, directed trees, weighted graphs, and path-reconstruction strings. Interviewers are checking whether you choose the right traversal primitive—BFS, Dijkstra, DFS/Union-Find, or topological-style reconstruction—and can justify complexity and edge cases.
Patterns & templates
-
Multi-source BFS for nearest-distance grids — initialize
queuewith all gates, expand level by level;O(mn)time,O(mn)space. -
Dijkstra’s algorithm for non-negative weighted graphs — adjacency list plus min-heap
priority_queue;O((V+E) log V)time. -
Directed tree validation — track
parent[node], detect two-parent violations, then run cycle detection with DFS or Union-Find. -
Path reconstruction from labeled edges — build
start_tag -> fragment, identify unique source, walk links; detect missing links, branches, and cycles. -
Preprocessing for repeated queries — sort/prefix arrays for budget queries, then binary search via
bisect_left/upper_bound; avoid per-query scans. -
Graph representation choice — use adjacency lists for sparse graphs, matrices only for dense or tiny graphs; clarify directed vs undirected edges.
-
Shortest-path gotchas — BFS only works for unit weights; use Dijkstra for positive weights and Bellman-Ford only if negative edges are possible.
Common pitfalls
Pitfall: Using DFS to compute shortest distance in an unweighted grid; BFS is the correct tool because it explores by distance layers.
Pitfall: Marking nodes visited too early in Dijkstra; skip stale heap entries by checking
if dist > best[node]: continue.
Pitfall: Solving the “extra directed edge” as only cycle detection; a valid rooted tree also requires exactly one parent per non-root node.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Implement SQL Table and DNA OrderingMicrosoft · Software Engineer · Onsite · medium
- Fill rooms with nearest-gate distanceMicrosoft · Software Engineer · Onsite · medium
- Identify the Extra Directed EdgeMicrosoft · Software Engineer · Onsite · medium
- Assemble DNA payload strings from tagged fragmentsMicrosoft · Software Engineer · Technical Screen · medium
- Implement tree traversals, BFS, and subsets generationMicrosoft · Software Engineer · Onsite · Medium
- Solve binary-search knapsack & graph shortest pathMicrosoft · Software Engineer · Take-home Project · Medium
- Solve budget queries and shortest pathMicrosoft · Software Engineer · Take-home Project · Medium
Related concepts
- Graph Traversal And Shortest PathsCoding & Algorithms
- BFS, DFS, Graph, And Grid TraversalCoding & Algorithms
- DFS/BFS Tree, Graph, And Grid TraversalCoding & Algorithms
- Graph Search And Weighted PathsCoding & Algorithms
- Graph, Grid, BFS/DFS, And Union-FindCoding & Algorithms
- Graph Search, Pathfinding, And ConnectivityCoding & Algorithms