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 Uber.

What role is this question designed for?

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

Simulate robot on grid with obstacles

Quick Overview

Simulate robot on grid with obstacles evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

A robot starts at (0, 0) on an unbounded integer grid. You are given a sequence of commands consisting of characters U, D, L, and R, and a set of blocked cells (obstacles). For each command, the robot attempts to move one cell in the indicated direction; if the destination cell is blocked, it does not move for that command and proceeds to the next. Return the maximum squared Euclidean distance from the origin reached at any time during the simulation. Design an algorithm that handles up to 1e5 commands and 1e5 obstacles efficiently; describe data structures (e.g., hash set for obstacles), complexity, and edge cases.

Quick Answer: Simulate robot on grid with obstacles evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

A robot starts at (0, 0) on an unbounded integer grid. You are given a string `commands` of characters from {U, D, L, R} and a list `obstacles` of blocked cells, each given as `[x, y]`. For each command, the robot attempts to move one cell in the indicated direction: - `U` -> (x, y+1) - `D` -> (x, y-1) - `L` -> (x-1, y) - `R` -> (x+1, y) If the destination cell is blocked (an obstacle), the robot does NOT move for that command and proceeds to the next command. Otherwise it moves into the destination cell. Return the maximum squared Euclidean distance from the origin (`x*x + y*y`) reached at ANY point during the simulation, including intermediate positions. If the robot never leaves the origin, return 0. The algorithm must handle up to 1e5 commands and 1e5 obstacles efficiently. Store obstacles in a hash set for O(1) lookup; the simulation is then a single O(number_of_commands) pass.

Constraints

0 <= len(commands) <= 1e5
commands contains only the characters 'U', 'D', 'L', 'R'
0 <= len(obstacles) <= 1e5
Each obstacle is a pair [x, y] of integers; the origin (0, 0) is never an obstacle
Coordinates fit comfortably in a 64-bit integer; the squared distance can exceed 2^31, so use a 64-bit return type in Java/C++ if commands push far in one direction

Examples

Input: ("RRUU", [])

Expected Output: 8

Explanation: No obstacles. Path: (1,0)->(2,0)->(2,1)->(2,2). Final (2,2) gives 2^2+2^2 = 8, the maximum.

Input: ("RRUU", [[2, 0]])

Expected Output: 5

Explanation: Cell (2,0) is blocked. First R reaches (1,0); second R targets (2,0) -> blocked, stay at (1,0). Then U->(1,1), U->(1,2). Max is at (1,2): 1+4 = 5.

Input: ("RRRR", [[2, 0]])

Expected Output: 1

Explanation: After R->(1,0) the next R targets blocked (2,0); the robot is stuck at (1,0) for all remaining R commands. Max distance is 1.

Input: ("", [])

Expected Output: 0

Explanation: Empty command string; the robot never leaves the origin, so the maximum squared distance is 0.

Input: ("UDUDUD", [])

Expected Output: 1

Explanation: Oscillation between (0,1) and (0,0). The peak distance is 1, reached at the intermediate (0,1) positions even though the final position is (0,0).

Input: ("LLDD", [])

Expected Output: 8

Explanation: Negative directions: (-1,0)->(-2,0)->(-2,-1)->(-2,-2). Squared distance at (-2,-2) is 4+4 = 8.

Input: ("R", [[1, 0]])

Expected Output: 0

Explanation: The only reachable destination (1,0) is blocked, so the robot never moves and the answer stays 0.

Input: ("URDL", [])

Expected Output: 2

Explanation: Path (0,1)->(1,1)->(1,0)->(0,0). The farthest point is (1,1) with squared distance 2, even though the robot returns to the origin.

Input: ("RRURR", [[1, 0], [3, 1]])

Expected Output: 5

Explanation: First two R commands target blocked (1,0) -> stay at origin. U->(0,1). R->(1,1). R->(2,1) (note (3,1) is blocked but never targeted). Max at (2,1): 4+1 = 5.

Hints

Store obstacles in a hash set keyed by the (x, y) pair so you can test 'is this cell blocked?' in O(1).
Walk the commands one at a time, keeping the current (x, y). Compute the destination; if it is in the blocked set, skip the move entirely and keep the old position.
Track the maximum of x*x + y*y after every successful move (not just at the end) — the farthest point can be an intermediate position the robot later moves away from.
The origin contributes distance 0, so initialize the best answer to 0; that also handles the empty-command and never-moves cases.

Quick Overview