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.

Design robot path boundedness with repeats

Company: Roblox

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

You are given a 2D grid with a set of blocked cells (obstacles) and a robot starting at (0, 0) facing north. The robot executes a finite instruction string S consisting of commands: G (move forward 1 if the next cell is not blocked, otherwise stay in place), L (turn left 90°), R (turn right 90°), and digits 2–9 meaning “repeat the immediately preceding command that many additional times” (e.g., G3 means move forward a total of 3 steps, R2 means turn right twice). After one execution of S, report the robot’s final (x, y) and heading. Then determine whether the path is bounded if S is repeated infinitely; i.e., whether there exists a fixed square of side length B that contains all visited positions under infinite repetitions. Return true if bounded, otherwise false. Design an algorithm that avoids simulating an unbounded number of steps and analyze its time and space complexity.

Quick Answer: This question evaluates algorithmic skills in parsing compressed instruction strings, finite-state simulation, and spatial reasoning to determine path boundedness, and it belongs to the Coding & Algorithms domain.

You are given a 2D grid with a set of blocked cells (obstacles) and a robot starting at (0, 0) facing north. The robot executes a finite instruction string `s` consisting of commands: - `G` — move forward 1 cell if the next cell is not blocked, otherwise stay in place - `L` — turn left 90 degrees - `R` — turn right 90 degrees - a digit `2`-`9` — repeat the immediately preceding command that many *additional* times (e.g. `G3` means move forward a total of 3 steps, `R2` means turn right twice). Headings are encoded as integers: `0`=North, `1`=East, `2`=South, `3`=West. North is +y, East is +x. After exactly one execution of `s`, report the robot's final position and heading. Then determine whether the path is **bounded** when `s` is repeated infinitely — i.e. whether there exists a fixed square that contains every visited position under infinite repetitions. Return a tuple `(x, y, heading, bounded)` where `(x, y)` and `heading` are the state after one execution of `s`, and `bounded` is `True` if the infinitely-repeated path stays inside some fixed square, else `False`. Key insight (avoids simulating unbounded steps): with no obstacles, the path is bounded iff after one cycle the robot is back at the origin OR it is no longer facing north — in either case it returns to a closed loop within at most 4 cycles. Obstacles can additionally trap a north-facing displaced robot (it stops drifting once it hits a wall), so detect boundedness by checking whether the `(x, y, heading)` state repeats within a bounded number of cycles.

Constraints

1 <= len(s) <= 10^4 (s may be empty in degenerate cases)
s contains only the characters G, L, R and digits 2-9
A digit always immediately follows a G/L/R command
0 <= number of obstacles <= 10^4
Obstacle and visited coordinates fit in 64-bit integers
The origin (0, 0) is never blocked

Examples

Input: ('GG', [])

Expected Output: (0, 2, 0, False)

Explanation: Two forward moves, no obstacles, still facing north and displaced to (0,2). Each cycle adds +2 to y forever -> unbounded.

Input: ('GL', [])

Expected Output: (0, 1, 3, True)

Explanation: Move to (0,1) then turn left to face West (3). Heading is not north, so the infinitely repeated path closes into a bounded loop.

Input: ('GLGLGLGL', [])

Expected Output: (0, 0, 0, True)

Explanation: Four move-then-left quarter turns trace a unit square and return to the origin facing north -> bounded.

Input: ('G2', [])

Expected Output: (0, 2, 0, False)

Explanation: G2 means move forward a total of 2 steps to (0,2), still north. Same as 'GG' -> unbounded.

Input: ('R2', [])

Expected Output: (0, 0, 2, True)

Explanation: R2 turns right twice, ending at the origin facing South (2). No displacement -> bounded.

Input: ('GG', [[0, 1]])

Expected Output: (0, 0, 0, True)

Explanation: The cell (0,1) directly ahead is blocked, so both G commands are no-ops. The robot stays at the origin facing north -> bounded.

Input: ('', [])

Expected Output: (0, 0, 0, True)

Explanation: Empty instruction: the robot never moves -> trivially bounded.

Input: ('G', [[0, 1]])

Expected Output: (0, 0, 0, True)

Explanation: Single G blocked by the obstacle at (0,1); robot stays at origin -> bounded.

Input: ('GR', [])

Expected Output: (0, 1, 1, True)

Explanation: Move to (0,1) then turn right to face East (1). Non-north heading -> bounded loop.

Input: ('GG', [[0, 2]])

Expected Output: (0, 1, 0, True)

Explanation: First G reaches (0,1); the second G is blocked by the obstacle at (0,2), so the robot stops at (0,1) facing north. On every subsequent cycle it again stops at (0,1), so its position stabilizes -> bounded despite still facing north.

Hints

First expand the digit-repeats: a digit d (2-9) after a command c means c is executed a total of d times, i.e. d-1 additional times. Flatten s into a plain list of G/L/R commands.
Simulate exactly one execution of s from (0,0) facing north, treating G as a no-op when the target cell is blocked. This gives the final (x, y, heading).
For boundedness without obstacles: the path is bounded iff the robot returns to the origin after one cycle OR it no longer faces north (a non-north heading forces it back into a closed loop within at most 4 cycles).
Obstacles can trap an otherwise-escaping north-facing robot — once it bumps a wall it stops drifting. Detect this by simulating cycle-by-cycle and checking whether the (x, y, heading) state ever repeats within a bounded number of cycles; if it does, the path is bounded.

Quick Overview

This question evaluates algorithmic skills in parsing compressed instruction strings, finite-state simulation, and spatial reasoning to determine path boundedness, and it belongs to the Coding & Algorithms domain.