← Waymo Interview Insights

Waymo·Machine Learning Engineer·Technical Phone Screen·Senior

Senior
Jun 2026

Summary

Waymo ML Engineer interview, got a maze robot problem that looked like a graph question but turned out to be something weirder. Took me a while to even understand what was being asked.

Questions Asked (1)

Q1

Given a 2D maze grid where cells are walls, empty spaces, or a single exit, design an instruction sequence (using U/D/L/R moves) such that a robot with no knowledge of its starting position is guaranteed to reach the exit after executing the full sequence. The robot stays put if a move would hit a wall or go out of bounds.

Algorithms & Data StructuresSystem Design
Author's notes

Spent the first few minutes just re-reading the problem because I kept thinking it was a shortest-path thing.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a deterministic finite automaton where the robot's state is its unknown position, and the instruction sequence must synchronize all possible states to the exit. Use a BFS over the product of all possible positions to find a sequence that drives every position to the exit, leveraging the fact that moves are deterministic and walls cause the robot to stay put.

Pro tip: Emphasize that the sequence must be universal—it works regardless of the starting cell—and discuss how the 'stay put' rule on walls can be exploited to simplify the synchronization process, showing you understand the practical constraints of real-world robotics.

1. Clarify the problem and constraints

Restate the problem: find a fixed sequence of moves that guarantees the robot reaches the exit from any starting position. Confirm that the robot has no sensors and that moves into walls or out of bounds result in no movement.

2. Model as a synchronization problem

Represent the maze as a graph where each cell is a state. The instruction sequence must synchronize all states to the exit state. This is equivalent to finding a synchronizing word for a deterministic finite automaton where the exit is an absorbing state.

3. Design an algorithm to find the sequence

Use BFS on the set of possible positions (initially all non-wall cells) to find a sequence that reduces the set to just the exit. At each step, try all four moves and update the set of positions; if a move leads to a smaller set, continue. This is a shortest path in the power set automaton.

4. Analyze complexity and feasibility

Discuss the worst-case complexity: the state space is 2^(number of cells), which is exponential. For small mazes, it's feasible; for large ones, heuristics or approximations may be needed. Mention that the problem is PSPACE-hard in general.

5. Consider practical implications and extensions

Relate to real-world robotics: such sequences are useful for calibration or recovery when localization fails. Discuss potential optimizations like exploiting symmetry or using a precomputed policy.

Key Points to Mention

  • The problem is equivalent to finding a synchronizing word for a deterministic finite automaton.
  • The 'stay put' rule on walls makes the automaton deterministic and can be used to reduce the state space.
  • BFS over subsets of positions (power set) can find the shortest universal sequence.
  • The problem is PSPACE-hard, so exact solutions are only feasible for small mazes.
  • The sequence must be universal: it works for any starting position, not just a known one.
  • Practical applications include robot recovery, calibration, and exploration without sensors.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.