Graph Search And Weighted Paths
Asked of: Software Engineer
Last updated

What's being tested
Tests graph modeling, weighted path optimization, and choosing the right search strategy under constraints. You should recognize when to use BFS, Dijkstra-style priority queues, greedy heaps, or multiplicative-to-additive transforms for paths like currency exchange.
Patterns & templates
-
BFS on grids —
O(R*C)time for unweighted moves; track(row, col, time/state)when obstacles or timing constraints change reachability. -
Dijkstra with
heapq— use for nonnegative weighted shortest paths;O((V+E) log V)and skip stale heap entries withif cost > dist[node]. -
Maximum product path — for exchange rates, maximize using a max-heap, or transform to shortest path with edge weight .
-
Bellman-Ford for arbitrage — detects negative cycles after
-log(rate)conversion; use when cycles can improve value indefinitely. -
Greedy capital selection — sort projects by required capital, push affordable profits into a max-heap, repeat
ktimes;O(n log n + k log n). -
Visited-state design — include all variables that affect future options: position, time parity, remaining resources, current capital, or chosen count.
-
Early exit carefully — valid for BFS first target and Dijkstra popped target, not for arbitrary DFS or when later cycles can improve value.
Common pitfalls
Pitfall: Treating currency exchange as normal shortest path without handling multiplication; use max-product logic or
-log(rate).
Pitfall: Marking a grid cell visited only by
(r, c)when time or resource state changes whether it is reachable.
Pitfall: Using DFS for weighted paths; it may find a path, but not the optimal path without exhaustive search or dynamic programming.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
Related concepts
- Graph Search, State Space, And Path OptimizationCoding & Algorithms
- Graph Search, Pathfinding, And ConnectivityCoding & Algorithms
- Graph Traversal And Shortest PathsCoding & Algorithms
- Shortest Path And Graph TraversalCoding & Algorithms
- DFS/BFS Tree, Graph, And Grid TraversalCoding & Algorithms
- Graph Algorithms, Dependency Resolution And ConnectivityCoding & Algorithms