Graph Search, Connectivity, And State-Space Algorithms
Asked of: Machine Learning Engineer
Last updated
What's being tested
These problems test practical graph traversal and state-space search skills: reachability, shortest-path in unweighted graphs, and exploring implicit graphs where nodes are positions or states. Interviewers probe ability to choose BFS/DFS/Union-Find, encode state efficiently, and control complexity for spatial or implicit-edge graphs.
Patterns & templates
- BFS for unweighted shortest path and reachability — enqueue on discovery,
O(V+E)time,O(V)space; avoid revisiting. - DFS for reachability or full-exploration — recursion or explicit stack; watch recursion depth and mark visited on push.
- Union-Find (DSU) for offline connectivity queries — near
O(α(N))per op; use path compression + union by rank. - Squared-distance check to avoid
sqrtcost and floating errors: comparedx*dx + dy*dy <= r*r. - Implicit graph generation: avoid building O(N^2) edges by spatial bucketing or KD-tree to find neighbors within threshold.
- State encoding as tuple/bitmask for multi-variable state (pos, cleaned-set) — use bitmask when dirty-count ≤ 20 for
2^kcompactness. - Visited set semantics: store full state when searching state-space (not just position) to prevent exponential re-exploration.
Common pitfalls
Pitfall: Building full adjacency for N ~10k causes O(N^2) time/memory; use spatial indexing or neighbor pruning.
Pitfall: Marking visited only on pop (instead of on push) creates duplicate queue entries and slows BFS substantially.
Pitfall: Comparing Euclidean distances with
sqrtcauses unnecessary floating error and CPU cost; use squared comparisons instead.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Practice questions
- Can you reach target with distance-threshold edges?Google · Machine Learning Engineer · Technical Screen · hard
- Implement a Web Crawler with BFS and DFSGoogle · Machine Learning Engineer · Technical Screen · medium
- Solve meeting scheduling and robot cleaning tasksGoogle · Machine Learning Engineer · Technical Screen · medium
Related concepts
- Graph Search, State Space, And Path OptimizationCoding & Algorithms
- Graph Search, Pathfinding, And ConnectivityCoding & Algorithms
- Graph Algorithms, Dependency Resolution And ConnectivityCoding & Algorithms
- Graph Search And Weighted PathsCoding & Algorithms
- Graph, Grid, And Connectivity AlgorithmsCoding & Algorithms
- Graph, Grid, BFS/DFS, And Union-FindCoding & Algorithms