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 Technical Screen rounds at Shopify.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Shopify during technical interviews.

Simulate a rover fleet | Shopify Coding Question

Simulate a rover fleet

Company: Shopify

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a simulator for autonomous rovers moving on a rectangular grid. You are given: - The grid size `width x height` - A set of blocked cells representing obstacles - A list of rovers, where each rover has: - an initial position `(x, y)` - an initial facing direction: `N`, `E`, `S`, or `W` - a command string consisting of: - `M`: move forward by one cell in the current direction - `L`: turn left 90 degrees - `R`: turn right 90 degrees Rules: 1. A rover may not move outside the grid. 2. A rover may not move into an obstacle. 3. Process rovers sequentially. Once a rover finishes, its final cell becomes occupied, and later rovers may not move into that cell. 4. If a move is invalid, stop executing further `M` commands for that rover and report that it was blocked. Return the final position, final direction, and blocked status for every rover. Discuss how you would structure the code, test edge cases, and explain trade-offs in your implementation.

Quick Answer: This question evaluates skills in simulation design, state management, grid-based movement logic, and handling constraints such as obstacles, boundaries, and sequential occupancy.

Implement a simulator for autonomous rovers moving on a rectangular grid. The grid has coordinates from (0, 0) to (width - 1, height - 1). You are given a list of obstacle cells and a list of rovers. Each rover is described by (x, y, direction, commands), where direction is one of 'N', 'E', 'S', or 'W', and commands is a string containing only 'M', 'L', and 'R'. Process the rovers in the given order. For each rover: - 'L' turns the rover left 90 degrees. - 'R' turns the rover right 90 degrees. - 'M' attempts to move the rover forward by one cell in its current direction. A move is invalid if it would: 1. Leave the grid, 2. Enter an obstacle cell, or 3. Enter a cell occupied by a previously finished rover. If a move is invalid, the rover stops immediately, its remaining commands are ignored, and its blocked status becomes True. After a rover finishes, its final cell becomes permanently occupied for all later rovers. Return the final state of every rover as a list of tuples: (final_x, final_y, final_direction, blocked). In an interview, a strong solution cleanly separates direction handling, move validation, and sequential occupancy tracking. You should also be ready to discuss edge cases such as an empty rover list, boundary collisions, obstacle collisions, and later rovers being blocked by earlier final positions, as well as the trade-off between using sets for sparse grids versus a full 2D matrix.

Constraints

1 <= width, height <= 10^5
0 <= number of obstacles <= 2 * 10^5
0 <= number of rovers <= 10^5
The total length of all command strings is at most 2 * 10^5
Obstacle cells are unique and lie inside the grid
Each rover starts inside the grid and not on an obstacle cell
Commands contain only 'M', 'L', and 'R'

Examples

Input: (4, 4, [(1, 1)], [(0, 0, 'N', 'MMR'), (0, 1, 'N', 'M'), (2, 2, 'W', 'LM')])

Expected Output: [(0, 2, 'E', False), (0, 1, 'N', True), (2, 1, 'S', False)]

Explanation: The first rover finishes at (0, 2) facing east, so that cell becomes occupied. The second rover tries to move into (0, 2) and is blocked. The third rover turns left from west to south, then moves to (2, 1).

Input: (3, 3, [], [(0, 0, 'S', 'MML'), (2, 2, 'E', 'M')])

Expected Output: [(0, 0, 'S', True), (2, 2, 'E', True)]

Explanation: Both rovers attempt to move outside the grid on their first move, so each one stops immediately and remains in place.

Input: (5, 5, [(2, 3), (3, 1)], [(1, 1, 'N', 'MRMLM'), (2, 1, 'N', 'M')])

Expected Output: [(2, 2, 'N', True), (2, 1, 'N', True)]

Explanation: The first rover reaches (2, 2) and then tries to move into obstacle (2, 3), so it is blocked there. That final cell becomes occupied, and the second rover is then blocked when trying to move into (2, 2).

Input: (2, 2, [(1, 1)], [])

Expected Output: []

Explanation: There are no rovers to simulate, so the result is an empty list.

Input: (1, 1, [], [(0, 0, 'N', 'LRM')])

Expected Output: [(0, 0, 'N', True)]

Explanation: On a 1x1 grid, the rover can turn left and right in place, but any move goes out of bounds, so it ends blocked at its starting cell.

Hints

Use sets for obstacle cells and occupied final cells so you can check whether a move is valid in O(1) average time.
Represent directions in a fixed circular order like ['N', 'E', 'S', 'W'] so turning left or right is just index arithmetic.

Quick Overview

This question evaluates skills in simulation design, state management, grid-based movement logic, and handling constraints such as obstacles, boundaries, and sequential occupancy.