Graph Search, Pathfinding, And Connectivity

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; use deque, visited set, parent tracking; handle blocked cells and unreachable targets.

• Dijkstra for weighted paths — O((V + E) log V) with heapq; 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 k components with exactly k-1 edges; 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.