Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Uber coding interview with a grid traversal problem that sounds straightforward until you realize the query batching angle makes it way harder than a basic BFS.

Questions Asked (1)

You're given an m x n integer matrix and a list of limit values. For each limit, starting from (0,0), you can move in four directions and collect a cell's value only if it's strictly less than the limit and you haven't visited it before. You stop expanding as soon as you hit a cell that's >= the limit. Return the max points collectible for each limit value.

Algorithms & Data Structures

Author's notes

My first instinct was just run a BFS for each limit independently, which technically works but felt wrong as soon as I said it out loud.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

For each limit, perform a BFS/DFS from (0,0) to explore all reachable cells with values strictly less than the limit, summing their values. To handle multiple limits efficiently, sort the limits and process them incrementally, reusing the exploration from smaller limits and only expanding to newly allowed cells. This avoids redundant work and achieves near-linear time in the total number of cells across all limits.

Pro tip: Mention that sorting the limits and using a priority queue (or sorting cells by value) allows you to process limits in increasing order, adding cells as they become valid. This demonstrates awareness of offline processing and amortized analysis, which interviewers at Uber value for scalability.

1. Clarify and Restate

Confirm the problem details: movement is 4-directional, cells must be strictly less than the limit, and you stop expanding when hitting a cell >= limit. Ask about constraints (e.g., matrix size, number of limits) to determine the optimal approach.

2. Brute Force Baseline

For each limit independently, run BFS/DFS from (0,0) to collect all reachable cells with value < limit. This is O(k * m * n) where k is number of limits, which may be too slow for large inputs.

3. Optimize with Sorting and Incremental Expansion

Sort the limits and process them in increasing order. Maintain a set of visited cells and a running sum. For each new limit, expand the frontier to include cells with values between the previous limit and the new limit, using a priority queue or sorted list of cells by value.

4. Implement Efficiently

Use a min-heap to always expand the smallest-valued cell first. When the smallest cell's value is >= current limit, stop expansion and record the sum. Then move to the next limit, continuing from where you left off.

5. Analyze Complexity and Edge Cases

Time complexity: O(mn log(mn) + k log k) due to sorting and heap operations. Space: O(mn). Discuss edge cases: empty matrix, limits smaller than (0,0), unreachable cells, and duplicate limits.

Key Points to Mention

BFS/DFS for reachability with value constraint
Sorting limits to enable incremental processing
Using a priority queue (min-heap) to expand cells in increasing value order
Maintaining a running sum and visited set to avoid recomputation
Time complexity analysis: O(mn log(mn) + k log k) and space O(mn)
Handling edge cases like limits <= matrix[0][0] or unreachable regions

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