Katkat
Back

Find robots matching obstacle-distance signature

UberSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests spatial reasoning, multi-source Breadth-First Search (BFS) for distance mapping, and pattern matching within 2D grids.

Problem Statement

You are given a 2D grid representing a factory floor where some cells contain obstacles (1) and others are empty (0). A robot's "signature" is defined as the sequence of distances from its position (r, c) to the nearest obstacle in the four cardinal directions (Up, Down, Left, Right). If no obstacle exists in a direction, the distance is considered infinity (or -1).

Given the grid and a target signature [d_up, d_down, d_left, d_right], return a list of all coordinates (r, c) in the grid where a robot placed in an empty cell would generate that exact signature.

Function Signature

def find_matching_robots(grid: List[List[int]], target: List[int]) -> List[List[int]]:

Constraints

  • grid dimensions: M x N where 1 <= M, N <= 500.
  • target is a list of 4 integers.
  • grid[r][c] is 0 (empty) or 1 (obstacle).

Example

Input:

grid = [
  [0, 0, 1],
  [0, 0, 0],
  [1, 0, 0]
]
target = [2, 1, 1, 0] # Up, Down, Left, Right

Explanation: For cell (1, 1): Up distance to obstacle is 2 (at (0, 2) if we define distance by columns or nearest obstacle row index, but here we mean Manhattan distance in cardinal lines). Let's define distance as the number of empty cells between the robot and the obstacle.

Output: [[1, 1]]

Edge Cases

  • Grid with no obstacles.
  • Grid completely filled with obstacles.
  • Target containing -1 (no obstacle reachable).

Hints

Hint 1

Precompute the distance to the nearest obstacle in all four directions for every cell using dynamic programming or four separate linear sweeps.

Hint 2

A single linear pass for each direction is sufficient to fill a distance matrix for that direction in O(M*N) time.

Hint 3

Once you have four 2D arrays representing distance-up, distance-down, distance-left, and distance-right, simply iterate through the grid once to compare each cell's signature with the target.

Follow-up questions

  • How would you optimize the memory usage if the grid dimensions were 10,000 x 10,000?
  • If the robots move and the obstacles are dynamic, how would you efficiently update the signature map?
  • What if the distance metric is changed to Euclidean distance to the nearest obstacle instead of cardinal lines?