Katkat
Back

Simulate a rover fleet

ShopifyMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manage state in a 2D grid simulation, coordinate multiple entities with movement logic, and enforce collision-avoidance constraints.

Problem Statement

You are designing the navigation control for a fleet of autonomous warehouse rovers on a rectangular grid of size M x N. Rovers start at specific coordinates (x, y) and move according to a list of commands.

Implement a function simulate_rovers(grid_size, rovers, commands) that returns the final positions of all rovers after they process their respective command sequences.

Rules:

  1. Grid: The grid is 0-indexed. (0,0) is the top-left corner.
  2. Commands: Each rover has a list of moves: U (up), D (down), L (left), R (right).
  3. Obstacles: The grid contains static obstacles that cannot be traversed.
  4. Collision: A rover cannot move into a cell if it is currently occupied by another rover or contains an obstacle.
  5. Execution: Commands are processed one step at a time for all rovers simultaneously. If a move is invalid (out of bounds or blocked), the rover stays in its current position for that turn.

Interface

def simulate_rovers(grid_size, rovers, commands, obstacles):
    # grid_size: tuple (M, N)
    # rovers: list of tuples [(x1, y1), (x2, y2), ...]
    # commands: list of strings ["UDR", "LR", ...]
    # obstacles: set of tuples {(x, y), ...}
    # returns: list of tuples [(x_final, y_final), ...]

Example

Input: grid_size=(3, 3), rovers=[(0, 0)], commands=["DR"], obstacles={(1, 0)}

  • Turn 1 ('D'): Target (0, 1) is valid. Position: (0, 1).
  • Turn 2 ('R'): Target (1, 1) is valid. Position: (1, 1). Output: [(1, 1)]

Constraints

  • 1 <= M, N <= 100
  • Number of rovers <= 50
  • Command length per rover <= 100

Hints

Hint 1

Represent the state of the grid as a set of occupied coordinates that you update after each simultaneous time step.

Hint 2

Since commands are executed simultaneously, calculate the 'intended' next position for all rovers before committing any moves to the board.

Hint 3

Consider creating a helper function to validate whether a coordinate is within bounds and not currently occupied by an obstacle or another rover.

Follow-up questions

  • How would you modify the simulation if rovers have different priority levels, allowing a higher-priority rover to 'bump' a lower-priority one?
  • If the command sequences are of different lengths, how should the system behave when one rover finishes its sequence while others are still moving?
  • How would you optimize the collision check if the grid size increased to 10,000 x 10,000 but the number of rovers remained small?