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.

Simulate robot on grid with obstacles

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.

Hints

  1. Store obstacles in a hash set keyed by the (x, y) pair so you can test 'is this cell blocked?' in O(1).
  2. 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.
  3. 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.
  4. The origin contributes distance 0, so initialize the best answer to 0; that also handles the empty-command and never-moves cases.

Loading coding console...