Graph Search, Pathfinding, And Connectivity
Asked of: Software Engineer
Last updated

What's being tested
Databricks is testing graph traversal, shortest-path reasoning, and state-space search under constraints. You need to recognize when to use BFS, Dijkstra, Union-Find, randomized sampling, or dynamic programming over graph-like states, then justify complexity and edge-case behavior.
Patterns & templates
-
BFS on unweighted graphs/grids —
O(V + E)time; usedeque, visited set, parent tracking; handle blocked cells and unreachable targets. -
Dijkstra for weighted paths —
O((V + E) log V)withheapq; required when edge weights represent time, cost, or transfer penalties. -
Multi-criteria optimization — compute feasible paths per mode, compare lexicographically by
(time, cost)or declared priority; avoid mixing metrics prematurely. -
State-space BFS — encode game boards or decisions as immutable tuples/strings; hash visited states; prune terminal wins/losses early.
-
Union-Find connectivity —
find,union, path compression, union by rank; ideal for connecting components or validating minimal connecting edges. -
Grid-to-graph modeling — map
(r, c)cells to neighbors lazily; avoid materializing all edges unless repeated queries justify preprocessing. -
Random spanning connectivity — connect
kcomponents with exactlyk-1edges; sample uniformly only if every valid construction has equal probability.
Common pitfalls
Pitfall: Using DFS when shortest path in an unweighted graph is required; BFS is the correctness argument, not just an implementation choice.
Pitfall: Treating “best path” as a single scalar without clarifying whether time, cost, transfers, or mode restrictions dominate.
Pitfall: Forgetting that game-tree BFS can explode exponentially; discuss hashing, symmetry reduction, terminal-state pruning, and worst-case bounds.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Find the Best Commute ModeDatabricks · Software Engineer · Technical Screen · medium
- Implement Random Connectivity and Grid RoutingDatabricks · Software Engineer · Technical Screen · none
- Find optimal commute mode in a city graphDatabricks · Software Engineer · Technical Screen · medium
- Design BFS to detect forced win in Tic-Tac-ToeDatabricks · Software Engineer · Technical Screen · Medium
- Solve graph path, interval deletion, and robberyDatabricks · Software Engineer · HR Screen · Medium
Related concepts
- Graph Search, State Space, And Path OptimizationCoding & Algorithms
- DFS/BFS Tree, Graph, And Grid TraversalCoding & Algorithms
- Graph, Grid, BFS/DFS, And Union-FindCoding & Algorithms
- BFS, DFS, Graph, And Grid TraversalCoding & Algorithms
- Graph Search And Weighted PathsCoding & Algorithms
- Graph Traversal And Shortest PathsCoding & Algorithms