Design a robot movement command system
Company: Shopify
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
## Robot Movement (Pair Programming)
You are given an empty starter repository (only a README). Implement a small, testable robot movement module that can:
- Represent a robot on a 2D grid.
- Receive a sequence of user commands.
- Execute those commands to update the robot’s position and direction.
- Be easily extensible as new valid commands are added over time.
### Requirements
1. **Robot state**
- The robot has a position `(x, y)` on an integer grid.
- The robot has a facing direction: one of `{N, E, S, W}`.
2. **Commands (initial set)**
Support at least these commands:
- `L`: rotate 90° left (N→W→S→E→N)
- `R`: rotate 90° right (N→E→S→W→N)
- `F`: move forward by 1 step in the direction it is currently facing
3. **Input / Output**
- Input: initial state `(x0, y0, dir0)` and a command string like `"FFLFFR"` (or an equivalent list/array of commands).
- Output: final state `(x, y, dir)` after executing all commands.
4. **Invalid command handling**
- Define and implement a clear policy for unknown commands (e.g., throw an error, ignore, or collect errors). State your choice.
5. **Extensibility constraint (core design requirement)**
- Assume **valid commands will keep expanding** (e.g., `B` for backward, `J` for jump, `U` for undo, etc.).
- Design the command system so adding a new command does **not** require rewriting large parts of the robot execution logic.
- Discuss/implement a command abstraction (e.g., command objects, a registry/dispatcher, etc.).
6. **Testing**
- Write small, incremental tests as you implement.
- After finishing, explain:
- What else you would optimize.
- How you would do **systematic testing** (unit tests, property-based tests, edge cases).
### Example
- Initial: `(0, 0, N)`
- Commands: `"FFRFF"`
- Expected final: `(2, 2, E)`
### Constraints (you may assume)
- Command string length: up to ~10^5.
- Grid is unbounded (no walls/obstacles) unless you explicitly choose to add bounds as an extension.
Implement the core classes/functions (e.g., `Robot`, command execution/dispatcher) and demonstrate with tests.
Quick Answer: This question evaluates design and implementation skills for an extensible, command-driven robot movement system, covering state representation on a 2D integer grid, directional updates, command dispatching, input/output semantics, and explicit handling policies for invalid commands.
Solution
### What this problem is really testing
The core grid logic (`L`/`R`/`F`) is trivial. The interview signal is in the **design**: how you receive commands, how you make the command set extensible without rewriting the executor, your invalid-command policy, and how you reason about testing. Treat this as a small but real codebase, not a LeetCode one-liner. Below I build it up the way you'd do it live in a pair-programming session: state model first, then a registry-based command dispatcher, then policy, then tests.
---
### 1. Model the state cleanly
Two ideas to nail up front:
- **Directions are a 4-cycle.** Order them clockwise `N, E, S, W`. Then "turn right" is `+1 mod 4`, "turn left" is `-1 mod 4`. No `if/elif` ladder, no bugs in the rotation table.
- **Each direction maps to a unit `(dx, dy)` step.** Forward is just `pos += step[dir]`. Backward (a future command) is `pos -= step[dir]`, for free.
```python
from enum import IntEnum
from dataclasses import dataclass
class Direction(IntEnum):
# Ordered clockwise so +1 mod 4 == turn right, -1 mod 4 == turn left.
# This ordering is load-bearing: the rotation logic depends on it.
N = 0
E = 1
S = 2
W = 3
def turn_right(self) -> "Direction":
return Direction((self + 1) % 4)
def turn_left(self) -> "Direction":
return Direction((self - 1) % 4)
# Unit step per direction. Using the standard math convention:
# N increases y, E increases x. (Pick a convention and document it.)
_STEP = {
Direction.N: (0, 1),
Direction.E: (1, 0),
Direction.S: (0, -1),
Direction.W: (-1, 0),
}
@dataclass
class Robot:
x: int = 0
y: int = 0
facing: Direction = Direction.N
def turn_left(self) -> None:
self.facing = self.facing.turn_left()
def turn_right(self) -> None:
self.facing = self.facing.turn_right()
def step(self, n: int = 1) -> None:
"""Move n units along the current facing (n can be negative)."""
dx, dy = _STEP[self.facing]
self.x += dx * n
self.y += dy * n
def state(self) -> tuple[int, int, str]:
return (self.x, self.y, self.facing.name)
```
`Robot` exposes a small **vocabulary of physical mutations** (`turn_left`, `turn_right`, `step`). Commands are written against this vocabulary — they never touch `self.facing` arithmetic directly. That separation is what keeps the executor stable as commands grow.
> **Convention call-out (say this aloud in the interview):** I'm treating left/right as the robot's own perspective and `N→W→S→E→N` for left, matching the prompt. I'm using the math convention where `N` increases `y`. If the interviewer wants screen coordinates (`N` decreases `y`) it's a one-line change in `_STEP`. Stating the convention is half the point — silent assumptions here are the classic bug source.
---
### 2. The extensible command system (the heart of the question)
The requirement: *"adding a new command must not require rewriting the execution logic."* This is the Open/Closed Principle and the **Command pattern + a registry**. Each command is a small object that knows how to mutate a `Robot`. The executor just looks the command up and applies it — it has **no knowledge** of which commands exist.
```python
from typing import Protocol, Callable
class Command(Protocol):
def execute(self, robot: "Robot") -> None: ...
class CommandRegistry:
"""Maps a command token (e.g. 'F') to a Command. Open for extension."""
def __init__(self) -> None:
self._commands: dict[str, Command] = {}
def register(self, token: str, command: Command) -> None:
if token in self._commands:
raise ValueError(f"Command {token!r} already registered")
self._commands[token] = command
def command(self, token: str):
"""Decorator sugar for registering a function as a command."""
def deco(fn: Callable[["Robot"], None]):
self.register(token, _FuncCommand(fn))
return fn
return deco
def get(self, token: str) -> Command | None:
return self._commands.get(token)
@dataclass
class _FuncCommand:
fn: Callable[["Robot"], None]
def execute(self, robot: "Robot") -> None:
self.fn(robot)
```
Now the **initial command set** is just registration — no `switch`/`if` on the token anywhere:
```python
registry = CommandRegistry()
@registry.command("L")
def _left(robot: Robot): robot.turn_left()
@registry.command("R")
def _right(robot: Robot): robot.turn_right()
@registry.command("F")
def _forward(robot: Robot): robot.step(1)
```
**Adding `B` (backward) and `J` (jump-2) later is a pure addition — zero changes to the executor or `Robot`:**
```python
@registry.command("B")
def _back(robot: Robot): robot.step(-1)
@registry.command("J")
def _jump(robot: Robot): robot.step(2)
```
That is the answer to requirement #5: new commands are new objects in a lookup table. The execution loop below never changes.
> Why a registry over a giant `match token:`? A `match`/`if-elif` block in the executor means every new command edits the executor — you reopen, re-test, and risk regressing existing commands. The registry inverts this: commands register *themselves*, the executor stays closed. It also lets you build commands at runtime, swap command sets per robot, and (below) support stateful commands like `undo` without special-casing.
---
### 3. The executor + invalid-command policy
```python
class RobotController:
def __init__(self, robot: Robot, registry: CommandRegistry):
self.robot = robot
self.registry = registry
def run(self, program: str, *, on_unknown: str = "raise") -> Robot:
"""
on_unknown:
'raise' -> stop and raise on first unknown token (default, fail-fast)
'ignore' -> skip unknown tokens silently
'collect' -> skip but return the list of (index, token) errors
"""
errors: list[tuple[int, str]] = []
for i, token in enumerate(program):
if token.isspace(): # tolerate whitespace formatting
continue
cmd = self.registry.get(token)
if cmd is None:
if on_unknown == "raise":
raise ValueError(f"Unknown command {token!r} at index {i}")
if on_unknown == "collect":
errors.append((i, token))
continue # 'ignore' and 'collect' both skip
cmd.execute(self.robot)
if on_unknown == "collect":
self.last_errors = errors
return self.robot
```
**Invalid-command policy — state the choice explicitly (requirement #4):**
I default to **fail-fast `raise`**, because a robot acting on a corrupted/typo'd command stream is a safety issue — you'd rather stop than silently drift to the wrong place. But I make it a parameter rather than hard-coding it, because the right policy is context-dependent: a batch tool ingesting noisy logs may prefer `collect` (validate the whole program, report all bad tokens at once), and an interactive REPL may prefer `ignore`. Reporting the **index** of the bad token matters for debuggability — "unknown command at index 4203" is actionable; "invalid input" is not.
**End-to-end usage matching the prompt's example:**
```python
robot = Robot(0, 0, Direction.N)
RobotController(robot, registry).run("FFRFF")
assert robot.state() == (2, 2, "E") # matches the spec's expected output
```
---
### 4. Worked trace of the example
Start `(0, 0, N)`, program `"FFRFF"`:
| step | cmd | facing before | action | state after |
|------|-----|---------------|--------|-------------|
| 1 | F | N | y += 1 | (0, 1, N) |
| 2 | F | N | y += 1 | (0, 2, N) |
| 3 | R | N | turn right | (0, 2, E) |
| 4 | F | E | x += 1 | (1, 2, E) |
| 5 | F | E | x += 1 | (2, 2, E) |
Final `(2, 2, E)` ✔ — matches the spec.
---
### 5. Complexity
- `run` is $O(n)$ in the program length $n$, with $O(1)$ work per command (dict lookup + a couple of integer ops). At $n = 10^5$ that's trivially fast.
- State is $O(1)$. The registry is $O(k)$ for $k$ distinct commands ($k$ is tiny).
- One micro-optimization if a program is dominated by long forward runs: **run-length collapse** consecutive identical commands (`FFFF…` → one `step(count)`) and apply rotations mod 4. This turns a degenerate $10^5$-`F` string into a single arithmetic update. I'd only add this if profiling showed a hot loop — it's a nice thing to mention, not to over-engineer first.
---
### 6. Handling stateful commands (`U` = undo)
The interviewer's list includes `U` (undo), which doesn't fit a pure "mutate the robot" command — it needs history. The clean way to support it **without** breaking the abstraction: make the executor own an **undo stack of inverse operations**, and let commands optionally provide an inverse.
```python
class ReversibleCommand(Protocol):
def execute(self, robot: "Robot") -> None: ...
def undo(self, robot: "Robot") -> None: ...
```
Turns and steps are trivially invertible (`turn_left`↔`turn_right`, `step(n)`↔`step(-n)`). The controller pushes each *reversible* executed command onto a stack; `U` pops and calls `undo`. Two things to call out so the design is actually correct, not just sketched:
- **`U` itself must not be pushed onto the stack** — otherwise a second `U` would pop and "undo the undo" (or try to undo `U`, which has no inverse). Concretely, the controller pushes a command only if it's reversible *and* it isn't the undo command, so the stack holds only the real mutations.
- A bare `U` on an empty stack is a no-op (or a defined error) — decide and state the policy, same as for unknown commands.
This stays open/closed — `U` is just another registered command that happens to read the controller's stack. Bring this up to show you've thought past the happy path; implement it only if asked, to respect the 75-minute clock.
---
### 7. What I'd optimize / harden next
- **Parse vs. execute separation.** Right now tokens are single chars. If commands grow to multi-char (`MOVE 3`, `TURN 90`), add a tiny **tokenizer** in front of the registry so the executor stays per-token. Designing the registry around a *token* (not a *char*) already anticipates this.
- **Bounded grid extension.** The prompt says unbounded "unless you add bounds." If walls/obstacles appear, the natural home is inside `Robot.step` (clamp or raise on collision) or a `World` object the robot queries — the command objects don't change. Keeping movement policy out of the commands is what makes this drop-in.
- **Command parameters & validation** (e.g. `step(n)` with `n` from input) — validate at registration/parse time, not deep in the loop.
- **Immutability option.** For concurrency or replay/debugging, make `Robot` immutable and have commands *return* a new `Robot`. Slower but trivially testable and thread-safe; a reasonable trade to discuss.
---
### 8. Systematic testing strategy (requirement #6)
I write tests **incrementally** alongside each piece (red/green), not all at the end. Concretely:
**Unit tests — direction algebra (the bug-prone part):**
```python
def test_rotation_cycles():
assert Direction.N.turn_right() == Direction.E
assert Direction.N.turn_left() == Direction.W
# four turns return to start, both ways
for d in Direction:
cur = d
for _ in range(4): cur = cur.turn_right()
assert cur == d
```
**Unit tests — single commands & the example:**
```python
def test_forward_in_each_direction():
for d, (dx, dy) in _STEP.items():
r = Robot(0, 0, d); r.step()
assert (r.x, r.y) == (dx, dy)
def test_spec_example():
r = Robot(0, 0, Direction.N)
RobotController(r, registry).run("FFRFF")
assert r.state() == (2, 2, "E")
```
**Edge cases — enumerate deliberately:**
- Empty program `""` → state unchanged.
- Whitespace / formatting in the program → tolerated.
- Unknown command under each policy: `raise` throws with the right index; `ignore` skips; `collect` returns exactly the bad `(index, token)` pairs.
- Net-zero programs: `"LR"`, `"FB"`, `"RRRR"` → robot returns to start.
- Large input: $10^5$ `F`s runs fast and lands at the expected coordinate.
**Property-based tests (e.g. Hypothesis)** — these catch the bugs hand-written cases miss:
- *Round-trip / inverse:* for any program, executing it then its reverse-inverse (`F`↔`B`, `L`↔`R`) returns to the start state. Great for catching off-by-one and sign errors.
- *Rotation invariance:* the final position is independent of how many full `4×L`/`4×R` cycles are sprinkled in.
- *Translation invariance:* running program `P` from `(x0,y0)` lands at `start + delta(P)`, where `delta` is independent of the start position — verifies movement is a pure offset.
- *Manhattan bound:* final distance from origin ≤ number of `F`/`B` commands.
**Extensibility regression test** — encodes the actual design goal:
```python
def test_new_command_needs_no_executor_change():
reg = CommandRegistry()
reg.register("L", _FuncCommand(lambda r: r.turn_left()))
reg.register("Z", _FuncCommand(lambda r: r.step(5))) # brand-new command
r = Robot(0, 0, Direction.N)
RobotController(r, reg).run("Z")
assert r.state() == (0, 5, "N") # works without touching RobotController
```
This last test is the one I'd point to when asked "how do you know the design is extensible?" — it *proves* a new command needs zero changes to the executor.
---
### Summary of design decisions (the talking points that score)
- **Directions as a mod-4 enum** + per-direction unit step → rotation and movement are arithmetic, not branchy tables.
- **Command pattern + registry/dispatcher** → Open/Closed: new commands are new registered objects; the executor never changes. This is the explicit answer to the extensibility requirement.
- **Invalid-command policy is an explicit, swappable parameter** (default fail-fast `raise`), reporting the offending index.
- **Forward/backward/jump fall out for free** because they're all `step(n)`; **undo** is handled by an optional inverse + controller stack without breaking the abstraction.
- **Testing is incremental and layered**: unit (direction algebra is the hot spot), edge cases, property-based invariants (round-trip, translation invariance, Manhattan bound), and an extensibility regression test that encodes the design goal itself.
