Walking Robot Simulation II is a more advanced version of the robot navigation problem. In this variant, the robot moves along the perimeter of a rectangle of defined width and height. Unlike the first version which was an open grid, this is a Design problem where you must implement a class that tracks the robot's position and direction as it moves num steps. The robot always moves counter-clockwise along the edge. If it reaches a corner, it turns 90 degrees and continues.
Google and Square often ask this to see how a candidate handles Design and Simulation under constraints. This problem isn't just about moving the robot; it's about optimizing the movement. Since the robot moves in a cycle (the perimeter), if the number of steps is very large, you shouldn't simulate every single step. Instead, you should use the modulo operator to find the effective number of steps within one full loop. This tests your ability to recognize cyclical patterns in systems.
The primary pattern is the Design interview pattern. You need to maintain the state of the robot (x, y, and direction). The most efficient way to solve this is to realize that the total perimeter length is 2 * (width + height - 2). Any movement num can be reduced using num % perimeter. However, there's a tricky edge case: when num is a multiple of the perimeter, the robot ends up at its starting position but its direction might change.
Assume a 6x3 rectangle. The perimeter coordinates are: (0,0) -> (5,0) [Width-1] (5,0) -> (5,2) [Height-1] (5,2) -> (0,2) [Width-1] (0,2) -> (0,0) [Height-1] If the robot is at (0,0) and needs to move 20 steps, and the perimeter is 14:
The biggest mistake is simulating every single step when num is large (e.g., 10^9). This will cause a timeout. Another mistake is incorrectly calculating the perimeter or the turning logic at the corners. Specifically, the direction change that happens exactly when the robot completes a lap is a common source of bugs. Candidates also often forget that the robot starts facing "East" but its direction can change even if it "moves" 0 steps after the first lap.
When designing a class that simulates a process, always look for cycles. If the state repeats after a certain interval, use mathematics to skip redundant work. Also, clarify the boundary conditions—does "width 6" mean indices 0 to 5 or 0 to 6? These details are critical for a correct implementation.
| Title | Difficulty | Topics | LeetCode |
|---|---|---|---|
| Design Parking System | Easy | Solve | |
| Simple Bank System | Medium | Solve | |
| Design Memory Allocator | Medium | Solve | |
| Design Snake Game | Medium | Solve | |
| Design Tic-Tac-Toe | Medium | Solve |
