How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Roblox.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Roblox during technical interviews.

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.

Input: ('GL',)

Expected Output: [[0, 1], 'West', True]

Explanation: Move to (0,1), then turn left to face West. Displaced but facing changed, so over 4 cycles the displacement cancels => bounded.

Input: ('',)

Expected Output: [[0, 0], 'North', True]

Explanation: Empty command: robot never moves, stays at origin facing North => bounded.

Input: ('GLGLGLGL',)

Expected Output: [[0, 0], 'North', True]

Explanation: A square loop: returns to origin facing North after one pass => bounded.

Input: ('R',)

Expected Output: [[0, 0], 'East', True]

Explanation: Just a right turn: no movement, facing East. At origin => bounded.

Input: ('GRGRGRG',)

Expected Output: [[0, 0], 'West', True]

Explanation: Traces a unit square clockwise back to (0,0), ending facing West => bounded.

Input: ('GGGGGGGG',)

Expected Output: [[0, 8], 'North', False]

Explanation: Eight forward moves to (0,8) still facing North => unbounded.

Input: ('LLGG',)

Expected Output: [[0, -2], 'South', True]

Explanation: Two lefts flip to South, then move to (0,-2). Displaced but facing changed => bounded.

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.

Quick Overview

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.