Number of Spaces Cleaning Robot Cleaned

Number of Spaces Cleaning Robot Cleaned

What is this problem about?

The Number of Spaces Cleaning Robot Cleaned problem simulates a cleaning robot moving through a grid. The robot starts at the top-left corner facing right, moves forward until it hits a wall or obstacle, then turns right and continues. Count how many unique grid spaces the robot cleans. This is a simulation with direction tracking and visited set management.

Why is this asked in interviews?

Microsoft and Geico ask this to test simulation design and the ability to detect the termination condition (when the robot returns to a previously visited state — same position and direction). The array, matrix, and simulation interview pattern is the core.

Algorithmic pattern used

Simulation with state cycle detection. Simulate robot movement step by step. At each step, track (row, col, direction) as the state. If the robot attempts to move into a wall or obstacle, turn right instead. Add each cleaned cell to a visited set. Terminate when the robot re-enters a previously seen (position, direction) state (cycle detected). Return the visited cell count.

Example explanation

Grid with obstacles, robot starts at (0,0) facing right.

• Move right until obstacle or wall. Turn right (now facing down).
• Move down until obstacle or wall. Turn right (facing left).
• Continue until cycle detected. Count unique (row, col) pairs visited.

Common mistakes candidates make

• Not detecting the cycle (robot could run forever without it).
• Only tracking visited positions, not visited (position, direction) pairs (different).
• Incorrect turn direction (always turn right, not left).
• Off-by-one in checking grid boundaries before moving.

Interview preparation tip

Robot simulation problems need three components: (1) direction vectors [(0,1),(1,0),(0,-1),(-1,0)] for right/down/left/up, (2) a visited state set including direction, (3) clean cycle termination. The direction index (dir_idx % 4) handles turning elegantly. Practice grid robot simulation problems of increasing complexity — from simple movement to obstacle avoidance to cycle detection. These appear frequently in simulation-based interview rounds.