Software Engineer · Full Journey · Coding

Uber — Software Engineer

Level: Staff-Level

Round: Full Journey · Type: Coding · Difficulty: 7/10 · Duration: 120 min · Interviewer: Neutral

Topics: Arrays, Matrices, Dynamic Programming, Prefix Sum

Location: San Francisco, CA

Interview date: 2025-12-28

Summary

Round 1: Screening

Question: Locate robot positions in a grid based on distances to blockers in four directions.

Round 2: Onsite

Question: Locate robot positions in a grid based on distances to blockers in four directions.

Details

Problem Description

I was given a 2D grid representing a map of positions. Some cells contain robots ('O'), others are empty ('E') or blocked ('X'). The edges of the grid are treated as blockers.

I was also given an integer array distance of length 4, describing how far a robot is from its nearest blocker in each of the four cardinal directions: [left, top, bottom, right].

Task

My task was to identify all robot positions whose distances to the closest blocker in all four directions exactly match the given distance array. I had to return the result as a list of coordinate pairs [row, col]. If no robot satisfies the condition, return an empty list.

Examples

Example 1:

board = [ ["O","E","E","E","X"], ["E","O","X","X","X"], ["E","E","E","E","E"], ["X","E","O","E","E"], ["X","E","X","E","X"] ] distance = [2, 2, 4, 1]

Output:

[[1, 1]]

Explanation:

Only the robot located at position (1, 1) has:

• 2 cells to the nearest blocker on the left
• 2 cells upward to the nearest blocker
• 4 cells downward to the nearest blocker
• 1 cell to the nearest blocker on the right

All distances match the provided specification.

What This Problem Is Really Testing

• Matrix scanning and directional traversal
• Preprocessing distances efficiently (DP / prefix-style scans)
• Careful boundary handling (edges as implicit blockers)
• Avoiding brute-force (O(mn(m+n))) solutions
• Designing clean logic for multi-directional constraints

My Solution

`python from typing import List, Optional

class Solution: LEFT = 0 TOP = 1 BOTTOM = 2 RIGHT = 3

def findRobotsPosition(self, board: List[List[str]], distance: List[int]) -> List[List[int]]:
    if not board or not board[0] or len(distance) != 4:
        return []

    rows, cols = len(board), len(board[0])
    result = []

    # Map to store distances for each robot at position (r, c)
    map_ = {}

    # Array to keep track of the last 'X' seen from the top for each column
    top = [-1] * cols

    # First pass to calculate left and top distances
    for r in range(rows):
        left = -1
        for c in range(cols):
            if board[r][c] == 'O':
                distanceLeft = abs(c - left)
                distanceTop = abs(r - top[c])
                map_[f"{r},{c}"] = [distanceLeft, distanceTop, -1, -1]
            if board[r][c] == 'X':
                left = c      # Update the last seen 'X' on the left
                top[c] = r    # Update the last seen 'X' on the top for this column

    # Array to keep track of the last 'X' seen from the bottom for each column
    bottom = [rows] * cols

    # Second pass to calculate bottom and right distances
    for r in range(rows - 1, -1, -1):
        right = cols
        for c in range(cols - 1, -1, -1):
            if board[r][c] == 'O':
                distanceBottom = abs(r - bottom[c])
                distanceRight = abs(c - right)
                key = f"{r},{c}"
                if key in map_:
                    distances = map_[key]
                    distances[self.BOTTOM] = distanceBottom
                    distances[self.RIGHT] = distanceRight
                    # Compare with the distance parameter
                    if (distances[self.LEFT] == distance[self.LEFT] and
                        distances[self.TOP] == distance[self.TOP] and
                        distances[self.BOTTOM] == distance[self.BOTTOM] and
                        distances[self.RIGHT] == distance[self.RIGHT]):
                        result.append([r, c])
            if board[r][c] == 'X':
                right = c      # Update the last seen 'X' on the right
                bottom[c] = r  # Update the last seen 'X' on the bottom for this column

    return result

`

Preparation Tips & Key Takeaways

What I Learned

• I learned that careful boundary handling is crucial when working with grids.
• I need to practice optimizing solutions to avoid brute-force approaches.

Recommended Preparation

Coding Practice

• Practice matrix traversal and scanning problems.
• Focus on dynamic programming techniques for preprocessing distances.

Algorithms

• Review dynamic programming (DP) and prefix sum techniques to optimize the distance calculation process.

Resources I Recommend

• LeetCode for similar matrix problems.
• Topcoder tutorials on dynamic programming.

Common Pitfalls to Avoid

• Avoid brute-force solutions that result in O(mn(m+n)) time complexity.
• Pay close attention to boundary conditions when calculating distances.