Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Uber SWE coding round with a graph/union-find problem that looks deceptively straightforward until you hit the scale constraints. The O(n^2) naive approach gets you partway through the reasoning but TLEs, so the whole interview basically pivots around whether you can figure out the smarter grouping strategy.

Questions Asked (1)

You have a list of balls at 2D integer coordinates and a distance threshold d. Two balls connect if they share a row or column and their coordinate difference along that axis is at most d. When you trigger a ball, it pulls in everything connected to it transitively. What is the minimum number of triggers needed to collect all balls?

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was union-find, which was right, but I went straight to checking every pair and the interviewer let me code it up before pointing out the scale.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the balls as nodes in a graph where edges connect balls sharing a row or column within distance d. The minimum number of triggers equals the number of connected components in this graph, so the problem reduces to efficiently building the graph and counting components.

Pro tip: Avoid O(n^2) pairwise comparisons by sorting balls by row and column and only connecting adjacent balls within distance d; this reduces the graph construction to O(n log n) and shows you care about scalability.

1. Clarify and Restate

Confirm the connection rules and that triggering a ball collects its entire connected component. Restate that the answer is the number of connected components.

2. Model as a Graph

Treat each ball as a node. Add edges between balls that share a row or column and are within distance d along that axis.

3. Efficient Graph Construction

Group balls by row and by column. Within each group, sort by coordinate and connect consecutive balls if their difference ≤ d. This captures all necessary edges without O(n^2) comparisons.

4. Count Connected Components

Use Union-Find (Disjoint Set Union) or BFS/DFS to count the number of connected components. The count is the minimum number of triggers.

5. Analyze Complexity and Trade-offs

Discuss time and space complexity. Mention that the sorting-based approach is O(n log n) and that Union-Find with path compression and union by rank is efficient. Consider edge cases like duplicate coordinates or isolated balls.

Key Points to Mention

Graph modeling: balls as nodes, connections as edges.
Minimum triggers = number of connected components.
Efficient edge generation by sorting within rows and columns.
Union-Find (Disjoint Set Union) for component counting.
Time complexity: O(n log n) with sorting, O(n α(n)) for Union-Find.
Handling edge cases: duplicate coordinates, isolated balls, large n.

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