Simulate robot path and detect boundedness
Company: Roblox
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A robot starts at (0,
0) facing north on an infinite 2D plane. It executes a command string s consisting of 'G' (move forward one unit), 'L' (turn left 90°), and 'R' (turn right 90°). After finishing s once, the robot repeats the same string k times, where k can be as large as 10^9. Implement an algorithm that
(a) returns the robot’s final position and facing direction after one execution of s, and
(b) determines whether the trajectory remains within a bounded region if s is repeated indefinitely. Provide time and space complexity and avoid simulating all k repetitions.
Quick Answer: This question evaluates the ability to simulate iterative movement and reason about repeated state transformations, testing competencies in algorithm design, cycle detection, and geometric reasoning; it falls under the Coding & Algorithms category.
A robot starts at (0, 0) facing **north** on an infinite 2D plane. It executes a command string `s` made of:
- `'G'` — move forward one unit in the current facing direction
- `'L'` — turn left 90°
- `'R'` — turn right 90°
After finishing `s` once, the robot repeats the same string `k` times, where `k` can be as large as 10^9.
Implement a function that returns three things in a list `[position, direction, bounded]`:
1. **`position`** — the robot's `[x, y]` coordinates after **one** execution of `s`.
2. **`direction`** — the robot's facing direction after one execution, one of `'North'`, `'East'`, `'South'`, `'West'`.
3. **`bounded`** — a boolean: `True` if the trajectory stays within a bounded region when `s` is repeated indefinitely, otherwise `False`.
**You must not simulate all `k` repetitions.** Determine boundedness from the result of a single pass.
**Key insight:** Track the net displacement and net heading change of one pass. The trajectory is bounded if and only if, after one pass, either the robot is back at the origin, **or** its facing direction is no longer north. (If it's displaced but still facing north, each repetition adds the same vector forever — unbounded. Otherwise the rotation guarantees the net displacement cancels out within at most 4 cycles, keeping it bounded.)
Directions are indexed N=0, E=1, S=2, W=3; a left turn decrements the index mod 4 and a right turn increments it mod 4.
Constraints
- 1 <= len(s) <= 10^5 (s may also be empty in edge cases)
- s consists only of the characters 'G', 'L', and 'R'
- k (number of repetitions) can be up to 10^9 — do NOT simulate it
- The robot starts at (0, 0) facing North
Examples
Input: ('GGLLGG',)
Expected Output: [[0, 0], 'South', True]
Explanation: Move up to (0,2) facing North, two lefts flip to South, move back down to (0,0). Returns to origin, so bounded; final facing South.
Input: ('GG',)
Expected Output: [[0, 2], 'North', False]
Explanation: Two forward moves end at (0,2) still facing North. Displaced and still North => each repetition pushes further north forever => unbounded.
Hints
- Represent the four headings as vectors in clockwise order: North=(0,1), East=(1,0), South=(0,-1), West=(-1,0). A right turn is +1 mod 4, a left turn is -1 mod 4 on the heading index.
- Simulate exactly one pass of s to get the final (x, y) and final heading. That single pass tells you everything.
- The path is bounded iff after one pass the robot is back at the origin, OR it is not facing North. If it ended displaced but still facing North, every repetition adds the same displacement vector forever, so it escapes to infinity.
- When the heading changed, the net effect of 4 passes is a full rotation that cancels the displacement, guaranteeing the robot stays within a bounded region — no need to test k beyond a single pass.