Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Did a technical screen for an SWE role at Uber and got hit with a grid traversal problem that looked deceptively manageable at first glance. The query-ordering twist is what gets you.

Questions Asked (1)

Given an integer matrix and an array of query values, for each query count how many cells are reachable from the top-left cell by moving in four directions through cells whose values are strictly less than the query. Return answers in the original query order.

Algorithms & Data Structures

Author's notes

My first instinct was to just run a BFS for every query independently.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Sort the queries and process them in increasing order, maintaining a union-find structure of cells whose values are below the current threshold. As the threshold increases, activate cells that become eligible and union them with already active neighbors, then the answer for each query is the size of the component containing the top-left cell. Map the answers back to the original query order.

Pro tip: Mention that this offline approach reduces the time complexity to O(MN log(MN) + Q log Q) and handles large inputs efficiently, which is crucial for Uber's scale. Also, clarify that if the top-left cell's value is not less than the query, the answer is 0.

1. Understand the problem and constraints

Clarify that movement is only through cells with values strictly less than the query, and that we need to count reachable cells from (0,0). Discuss potential constraints to choose the right algorithm.

2. Choose an offline processing strategy

Sort queries in ascending order and process them incrementally, activating cells as the threshold increases. This avoids recomputing reachability for each query.

3. Implement union-find with cell activation

Sort all cells by value. For each query, activate all cells with value less than the query and union them with already active neighbors. Track the size of the component containing the top-left cell.

4. Record and reorder answers

Store the answer for each query in a map keyed by the query value or index, then output in the original query order.

5. Analyze complexity and edge cases

Discuss time and space complexity, and handle edge cases like empty matrix, queries smaller than the top-left cell's value, and duplicate queries.

Key Points to Mention

Union-Find (Disjoint Set Union) with path compression and union by rank/size for near-constant time operations.
Offline processing by sorting queries to avoid redundant computations.
Activation of cells in increasing order of their values, using a sorted list of cells.
Checking and unioning with four neighbors (up, down, left, right) only if they are already active.
Handling the top-left cell specially: if its value is not less than the query, answer is 0.
Time complexity: O(MN log(MN) + Q log Q + MN α(MN)) and space complexity O(MN + Q).

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