Design robot path boundedness with repeats

Q: Design robot path boundedness with repeats

This is a Coding & Algorithms interview question from Roblox for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Design robot path boundedness with repeats

Comments (0)