You are building a **rover navigation simulator**. The exercise is incremental: you implement a single rover on a 2D grid, then extend the design to many rovers sharing one map, then generalize the model to a 3D map. This is a pair-programming/live-coding question — the interviewer cares as much about how cleanly your design absorbs each new requirement as about the final output, so prefer small, well-named abstractions over one large function. ### Constraints & Assumptions - Grid is rectangular, axis-aligned, with integer coordinates. Treat the map as $W \times H$ cells (and later $W \times H \times D$); a position is valid if $0 \le x < W$ and $0 \le y < H$. - 2D headings are exactly `N, E, S, W`. Conventionally, `N` is $+y$, `E` is $+x$, `S` is $-y$, `W` is $-x$ — but **state your convention** and keep it consistent. - Commands are a string over the alphabet `{L, R, M}` and are executed left to right. `L`/`R` are pure $90°$ rotations (position unchanged); `M` advances one cell in the current heading. - Out-of-bounds behavior must be explicit and consistent. Pick **either** "ignore the offending `M` and continue" **or** "raise an error" — and apply it everywhere. - Aim for $O(k)$ time in the number of commands $k$ per rover, with $O(1)$ extra state per rover. ### Clarifying Questions to Ask - What is the coordinate convention — does `N` mean $+y$, and is the origin at a corner or the center? - On an out-of-bounds `M`, do you want me to silently skip it, stop processing, or raise an error? - For multiple rovers, is execution sequential or simultaneous, and what exactly counts as a collision (same destination cell? swapping cells? a rover entering a cell another is leaving)? - Are starting positions guaranteed in-bounds and non-overlapping, or must I validate the initial configuration? - Is the grid large/sparse enough that I should track occupancy with a hash set rather than a dense 2D/3D array? - For 3D, am I free to define the command set, or must I keep `L/R/M` and only add new letters? ### Part 1: Single rover on a 2D map You are given a rover starting at `(x0, y0)` facing one of `N, E, S, W`, plus a command string over `{L, R, M}`. Implement a function that executes all commands and returns the rover's final position and direction. A move that would leave the grid must follow your chosen out-of-bounds policy. ```hint Model the heading as ordered, not as if/else Store the four headings in a fixed cyclic order (e.g. `[N, E, S, W]`) and track the current heading by index. If headings are arranged in turn order, then `R` and `L` each become a single step around the cycle (mind the wraparound) instead of a four-way branch — and adding directions later stays trivial. ``` ```hint Decouple "turn" from "move" Keep a `(dx, dy)` delta per heading. `M` becomes "compute the candidate cell, check bounds, commit or reject" — a single code path you'll reuse unchanged for multiple rovers and for 3D. ``` #### What This Part Should Cover - Heading modeled as a cyclic table (no `if/elif` ladder), with turns expressed as modular index math. - A single bounds-checked move path that returns whether the move was accepted — a signal the later parts reuse. - An explicit, consistently-applied out-of-bounds policy, stated *before* coding. - Correct edge cases: empty command string, a rover already at the boundary, an `M` that is a no-op due to bounds, and lowercase/invalid commands. ### Part 2: Multiple rovers on the same map Extend the design so several rovers, each with its own initial state and command string, share one 2D map. Two things must be decided and implemented: (a) the **execution model** — do rovers run sequentially (rover 1 finishes all its commands, then rover 2 starts) or simultaneously (all rovers execute step $t$ before any executes step $t+1$)? (b) a **collision policy** — e.g. no two rovers may occupy the same cell, so a move into an occupied cell is rejected (skipped) while the rover keeps processing later commands. Explain how the code structure and API change to support this cleanly and safely. ```hint Separate world state from per-rover logic Introduce a `Grid`/`World` that owns boundaries and the set of occupied cells, and a `Rover` that owns position/heading and asks the world to validate a move. The world becomes the single authority for "is this cell free?", so collision logic lives in exactly one place. ``` ```hint The execution model changes how you detect collisions Sequential execution can check occupancy against rovers' *final* cells only. Simultaneous execution needs a per-tick check — and you must decide what "collision" means when two rovers try to enter the same cell *on the same tick*, and whether swapping positions counts. Name the policy explicitly. ``` #### Clarifying Questions for this Part - When two rovers target the same empty cell on the same tick, should both be rejected, or is there a priority/tie-break order? - Are the rovers' command strings allowed to differ in length, and what happens to a rover that has finished while others are still moving? #### What This Part Should Cover - A `World`/`Grid` authority that owns occupancy *and* boundaries, so collision logic is centralized and the `Rover` API barely changes. - A clearly named execution model (sequential vs. simultaneous) and a precisely defined collision policy, including the same-tick contention and position-swap cases. - An invariant that occupancy always reflects every rover's current cell — including stationary rovers — so no rover can be silently driven through. - An atomic per-tick commit so iteration order can't let one rover unfairly "win" a contested cell. ### Part 3: Generalize to a 3D map The map is now 3D with coordinates `(x, y, z)`. Define a reasonable orientation model for 3D space. Specify how turning and moving work in 3D and which commands you add (e.g. commands to pitch up/down), then describe (and/or implement) how your Part 1–2 solution generalizes while staying maintainable. Pay careful attention to what happens at the orientational extremes — there are edge cases in 3D rotation that have no 2D analogue. ```hint Push dimensionality into the heading table, not the algorithm If the only place that "knows" the dimension is the heading→delta table and the bounds check, then 3D is mostly a data change: replace the 2D heading table with a 3D one and add a $z$ bound. The move/collision code can then be reused verbatim. ``` ```hint Turning in 3D is not a single cycle With more than 4 facings you can't model all rotations as one `% 4` cycle. Consider defining rotations relative to an axis (e.g. yaw turns within the horizontal plane, a new command pitches toward the vertical). Think carefully about what happens to orientation state when the rover reaches the "top" or "bottom" of its rotation range — and state your policy explicitly. ``` #### What This Part Should Cover - A 3D generalization that changes mostly *data* (the heading→delta and turn tables, plus one extra bound) rather than the core loop — demonstrating the Part 1 abstraction paid off. - A concrete orientation model (e.g. six axis-facings, or yaw + pitch) with the added commands stated explicitly. - An explicit, self-consistent policy for what happens to orientation at a rotational extreme (e.g. pointing straight up or down, where azimuth is undefined), plus a worked command trace through that case. ### What a Strong Answer Covers These dimensions span all three parts: - The same move/turn algorithm survives every extension; what changes is *data* (the tables) and *ownership* (`Grid`→`World`), not the core loop. - Time/space reasoning throughout: $O(k)$ time and $O(1)$ extra state per rover, with occupancy stored so memory scales with the number of rovers, not the map volume. - Testability: the turn and move logic is unit-testable in isolation, and the candidate names the invariants they would assert (rotation forms a group, bounds are respected, no two rovers share a cell). ### Follow-up Questions - Suppose obstacles (impassable cells) are added to the map. How does your design change, and does it touch the `Rover` or only the `World`? - For simultaneous execution with collisions, how do you resolve a deadlock where two rovers each block the other's next move — do you skip, retry, or fail the configuration? - How would you support a very large, sparse 3D space (e.g. $10^9$ per axis) where a dense grid is infeasible? - The interviewer notes "all the code is AI-generated." How would you review such code for correctness — what specific tests or invariants would you add before trusting it?