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 hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

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

Find robots matching obstacle-distance signature

Q: Find robots matching obstacle-distance signature

This question evaluates spatial reasoning on 2D grids, the ability to compute distance signatures to nearest obstacles, and careful handling of boundary and edge-case conditions.

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a 2D grid and a distance signature `dist = [left, top, bottom, right]`. ## Grid Each cell is one of: - `O` : a robot - `E` : empty - `X` : obstacle The **boundary outside the grid is also considered an obstacle** (i.e., moving off the grid in any direction hits an obstacle immediately). ## Distance signature For any cell `(r, c)`, define: - `left` = the number of **non-obstacle cells** strictly between `(r,c)` and the nearest obstacle when moving left in the same row. - `top` = the number of non-obstacle cells strictly between `(r,c)` and the nearest obstacle when moving up in the same column. - `bottom` = the number of non-obstacle cells strictly between `(r,c)` and the nearest obstacle when moving down in the same column. - `right` = the number of non-obstacle cells strictly between `(r,c)` and the nearest obstacle when moving right in the same row. Notes: - If the adjacent cell in that direction is an obstacle (or you would immediately leave the grid), the distance in that direction is `0`. - Obstacles (`X`) block the line of sight; only the nearest obstacle in that direction matters. ## Task Return the coordinates of **all robots** (`O` cells) whose distance signature equals the given `dist`. ## Input / Output (you may assume) - Input: `grid` as an `R x C` matrix of characters, and integer array `dist` of length 4. - Output: a list of coordinates `[(r1,c1), (r2,c2), ...]` for all matching robots (any order). ## Constraints (reasonable interview assumptions) - `1 <= R, C <= 2000` - `grid[r][c] ∈ { 'O', 'E', 'X' }` - `0 <= dist[i] <= max(R,C)`

Quick Answer: This question evaluates spatial reasoning on 2D grids, the ability to compute distance signatures to nearest obstacles, and careful handling of boundary and edge-case conditions.

You are given an R x C grid containing robots, empty cells, and obstacles. Each cell is one of 'O' for a robot, 'E' for empty, or 'X' for obstacle. The boundary outside the grid is also considered an obstacle. For any robot cell, compute its distance signature [left, top, bottom, right], where each value is the number of non-obstacle cells strictly between that robot and the nearest obstacle in that direction. Obstacles block line of sight, and moving off the grid hits an obstacle immediately. Return the zero-indexed coordinates of all robots whose signature exactly equals the given dist array.

Constraints

1 <= R, C <= 2000
grid[r][c] is one of 'O', 'E', or 'X'
dist has length 4 and is ordered as [left, top, bottom, right]
0 <= dist[i] <= max(R, C)
The boundary outside the grid is considered an obstacle

Examples

Input: ([['E','O','E'], ['O','O','O'], ['E','X','E']], [1, 1, 0, 1])

Expected Output: [(1, 1)]

Explanation: Robot (1,1) has one non-obstacle cell to the left, one above, zero below because of the obstacle at (2,1), and one to the right.

Input: ([['O']], [0, 0, 0, 0])

Expected Output: [(0, 0)]

Explanation: The only robot is surrounded by the grid boundary in all four directions, so all distances are 0.

Input: ([['X','O','X']], [0, 0, 0, 0])

Expected Output: [(0, 1)]

Explanation: The robot has obstacles immediately to its left and right, and the top and bottom boundaries are immediate obstacles.

Input: ([['O','O','O']], [0, 0, 0, 0])

Expected Output: []

Explanation: No robot has distance 0 in both horizontal directions because all three robots are in one non-obstacle segment.

Input: ([['E','E','E','X','E','E','E'], ['E','O','E','X','E','O','E'], ['E','E','E','X','E','E','E']], [1, 1, 1, 1])

Expected Output: [(1, 1), (1, 5)]

Explanation: Both robots are centered in separate 3 by 3 non-obstacle regions, so each has one non-obstacle cell in every direction before an obstacle or boundary.

Input: ([['X','E','O','E','X'], ['E','E','O','E','E'], ['X','E','O','E','X']], [1, 0, 2, 1])

Expected Output: [(0, 2)]

Explanation: Robot (0,2) has left/right distances 1, top distance 0 due to the boundary, and bottom distance 2 before the bottom boundary.

Hints

Obstacles and grid boundaries split each row and column into maximal non-obstacle segments.
Inside a horizontal segment [start, end], a cell at column c has left = c - start and right = end - c. A similar idea works for vertical segments.

Quick Overview

This question evaluates spatial reasoning on 2D grids, the ability to compute distance signatures to nearest obstacles, and careful handling of boundary and edge-case conditions.