Find robots in a grid whose four-direction distances to blockers match a query
Company: Uber
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A rectangular grid contains robots, blockers and empty cells. For each robot, measure how far it is from the nearest blocker in each of the four directions (up, down, left and right), where the edge of the grid also counts as a blocker. Given the four distances you are looking for, return the positions of all robots whose distances match exactly.
### Function Signature
```python
def find_robots(grid: list[str], query: list[int]) -> list[list[int]]:
```
`grid[i][j]` is `'R'` for a robot, `'#'` for a blocker and `'.'` for an empty cell. `query` is `[up, down, left, right]`.
### Rules
- Row `0` is the top row and column `0` is the leftmost column. The grid has `m` rows and `n` columns.
- Only `'#'` cells block. Robots and empty cells never block, so a robot's distance is measured past any other robots in the way.
- For a robot at `(r, c)`:
- `up = r - i`, where `i` is the largest row index with `i < r` and `grid[i][c] == '#'`, or `i = -1` if there is none.
- `down = i - r`, where `i` is the smallest row index with `i > r` and `grid[i][c] == '#'`, or `i = m` if there is none.
- `left = c - j`, where `j` is the largest column index with `j < c` and `grid[r][j] == '#'`, or `j = -1` if there is none.
- `right = j - c`, where `j` is the smallest column index with `j > c` and `grid[r][j] == '#'`, or `j = n` if there is none.
- A robot directly next to a blocker or to the edge therefore has distance `1` in that direction, and every distance is at least `1`.
- A robot matches when its `[up, down, left, right]` equals `query` element by element.
- Return `[row, col]` for every matching robot, sorted by row and then by column. Return an empty list if no robot matches.
### Constraints
- `1 <= m <= 500` and `1 <= n <= 500`, where `m = len(grid)` and `n = len(grid[0])`; all rows have the same length.
- Every character of `grid` is `'R'`, `'#'` or `'.'`. The grid may contain no robots, and every cell may be a robot.
- `len(query) == 4` and `1 <= query[k] <= 10^9` for every `k`.
### Examples
**Example 1**
```text
Input: grid = ["R.#.R", ".R...", "#.R.R"], query = [2, 2, 2, 4]
Output: [[1, 1]]
```
The robots' distances `[up, down, left, right]` are: `(0, 0)` has `[1, 2, 1, 2]`, `(0, 4)` has `[1, 3, 2, 1]`, `(1, 1)` has `[2, 2, 2, 4]`, `(2, 2)` has `[2, 1, 2, 3]` and `(2, 4)` has `[3, 1, 4, 1]`. Robot `(1, 1)` has no blocker in any direction, so all four distances are measured to the edges: `up = 1 - (-1) = 2`, `down = 3 - 1 = 2`, `left = 1 - (-1) = 2` and `right = 5 - 1 = 4`.
**Example 2**
```text
Input: grid = ["R#R.", "....", "R#R#"], query = [3, 1, 1, 1]
Output: [[2, 0], [2, 2]]
```
Both robots in the bottom row have `[3, 1, 1, 1]`: the robots above them in row `0` do not block, so `up` is measured to the top edge, and on the other three sides each is next to a blocker or the edge. The robots in row `0` have `up = 1`, so they do not match.
**Example 3**
```text
Input: grid = ["R"], query = [1, 1, 1, 2]
Output: []
```
The only robot has distances `[1, 1, 1, 1]`.
Overview: Given a grid of robots, blockers and empty cells plus a query of four distances, return every robot whose distances to the nearest blocker or grid edge going up, down, left and right match the query exactly. Tests precise distance definitions, boundary handling and scaling past a per-robot scan.
Read the full Uber Machine Learning Engineer interview experience this question came from