Robot Room Cleaner

Robot Room Cleaner

What is this problem about?

The Robot Room Cleaner interview question is an interactive problem where you control a robot in a room represented as a grid. You can call API methods: move() (move forward), turnLeft(), turnRight(), and clean(). The robot starts at an unknown position and cannot see the grid directly. You must write an algorithm that ensures every reachable cell is cleaned using only these four API calls.

Why is this asked in interviews?

This HARD problem is asked at Uber, Citadel, Microsoft, Meta, Two Sigma, DRW, Amazon, LinkedIn, TikTok, and Google because it tests advanced backtracking with state tracking under API constraints. It is an "interactive" problem where you cannot read the grid directly — you must infer your position from the robot's movements. This models real robotic navigation: Roomba-style vacuum cleaners, warehouse robots, and autonomous vehicles that must explore unknown spaces.

Algorithmic pattern used

The pattern is backtracking with direction state and visited set. Maintain a set of visited cells (represented as relative coordinates from the start). Maintain the robot's current direction (0=up, 1=right, 2=down, 3=left). Use DFS: at each cell, try all 4 directions. For each direction: if the neighbor is not visited and move() succeeds, recurse into the neighbor, then return to the current cell (turn 180°, move, turn 180° — this is the "go back" step). Track direction as a state variable, updating it when turning.

Example explanation

Start at (0,0) facing up. Try all 4 directions:

• Attempt up: move() succeeds → clean (0,1), DFS from there.
• Return to (0,0): turn 180°, move, turn 180°.
• Attempt right: move() fails (wall) → skip.
• Attempt down: move() succeeds → clean (0,-1), DFS from there. ...

The key is the "go back" sequence: turnRight(), turnRight(), move(), turnRight(), turnRight() — rotate 180°, move back, rotate 180° to face original direction.

Common mistakes candidates make

• Not implementing the "go back" step correctly, leaving the robot at the wrong position after backtracking.
• Using absolute coordinates instead of relative ones — the starting position is unknown, so relative tracking is necessary.
• Forgetting to clean the current cell before exploring neighbors.
• Infinite recursion by not tracking visited cells — always add a cell to visited before recursing.

Interview preparation tip

For the Robot Room Cleaner coding problem, the backtracking interview pattern with interactive API usage is the core. The "go back" maneuver (two right turns, move, two right turns) is the most critical piece — practice it separately. Google and Two Sigma interviewers test whether you handle all four directions symmetrically using a direction array [(−1,0),(0,1),(1,0),(0,−1)]. State the go-back logic explicitly before coding to show you understand the movement model.