Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

Uber SWE interview with a grid-based coding problem that looked straightforward until I actually had to think about the precomputation strategy. Not the hardest problem I've seen but definitely requires you to slow down and think before coding.

Questions Asked (1)

You're given a 2D grid where each cell is either empty, a robot, or an obstacle. Given a target tuple of four distances [left, up, right, down] representing how far a robot sits from the nearest obstacle in each direction, return the coordinates of all robots in the grid whose distances match that tuple exactly. Note that other robots do not count as obstacles.

Algorithms & Data Structures

Author's notes

My first instinct was to just BFS from every robot cell and call it a day.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Precompute the distance to the nearest obstacle in each of the four directions for every cell using four directional passes (left-to-right, right-to-left, top-to-bottom, bottom-to-top). Then iterate through the grid, and for each robot cell, compare its precomputed distance tuple with the target tuple, collecting matching coordinates. This approach runs in O(m*n) time and space, which is optimal for grid traversal.

Pro tip: Clarify upfront that robots are not obstacles, so distance calculations should only consider obstacle cells. Also, handle edge cases like no obstacles (distances to grid boundaries) and robots on the grid edges.

1. Clarify problem and constraints

Confirm that robots do not block distances and that distances are measured to the nearest obstacle in each direction, not to the grid boundary. Ask about grid size and whether multiple robots can share a cell.

2. Design precomputation strategy

Use four 2D arrays to store distances to the nearest obstacle in left, up, right, and down directions. Initialize distances to infinity or a large number, then update during directional scans.

3. Perform directional scans

For left distances, scan each row left-to-right: if cell is obstacle, set distance 0; else distance = previous cell's distance + 1. Similarly, scan right-to-left for right distances, top-to-bottom for up distances, and bottom-to-top for down distances.

4. Collect matching robots

Iterate over all cells; if the cell contains a robot, check if its four precomputed distances equal the target tuple. If so, add its coordinates to the result list.

5. Analyze complexity and edge cases

State that time and space complexity are O(m*n). Discuss edge cases: no obstacles, robots at boundaries, and target tuple with large distances.

Key Points to Mention

Robots are not obstacles, so distance calculations ignore other robots.
Four directional passes (left, right, up, down) efficiently compute distances in O(m*n).
Use of dynamic programming or prefix sums to propagate distances from obstacles.
Handling of grid boundaries: distances to nearest obstacle may be limited by grid edges if no obstacle exists in that direction.
Time and space complexity: O(m*n) for both, which is optimal.
Edge cases: empty grid, no obstacles, multiple robots, and target tuple with values exceeding grid dimensions.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.