Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Uber SWE coding round with a graph clustering problem. The key was recognizing it as a connected components question, which made the solution pretty clean once that clicked.

Questions Asked (1)

You have a set of balls on a 2D plane, each with coordinates (x, y) and a distance threshold d. Two balls attract each other if their Euclidean distance is less than d, and attraction is transitive. At each time step you pick one ball, which instantly merges with all balls reachable through chains of attraction into a single cluster. Find the minimum number of time steps needed so all balls end up in one group.

Algorithms & Data Structures

Author's notes

Took me a minute to see past the physics-y framing.

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 within distance d, then find the connected components. The minimum number of time steps is the number of connected components minus one, because each step can merge one component with another by picking a ball in one component that is reachable to another component. However, since attraction is transitive, picking any ball in a component merges the entire component, so the answer is simply the number of connected components minus one.

Pro tip: Clarify that the merging is instantaneous and transitive, so the problem reduces to counting connected components in a graph where edges are defined by distance threshold. Mention that if all balls are already in one component, the answer is 0.

1. Understand the problem

Restate the problem: balls attract if distance < d, attraction is transitive, and picking a ball merges its entire connected component. Goal: minimum steps to merge all balls into one group.

2. Model as a graph

Represent each ball as a node. Add an edge between two balls if their Euclidean distance is less than d. The transitive attraction means connected components in this graph.

3. Find connected components

Use union-find (DSU) or BFS/DFS to identify all connected components. The number of components, say C, is the key value.

4. Determine minimum steps

Each time step, picking a ball merges its entire component with all components reachable from it. Since the graph is static, the minimum steps to merge all components is C - 1. If C = 1, answer is 0.

5. Discuss complexity and edge cases

Mention time complexity: O(n^2) to build graph naively, or O(n log n) with spatial indexing. Edge cases: no edges (C = n, answer n-1), all connected (C = 1, answer 0).

Key Points to Mention

Graph representation: nodes as balls, edges if distance < d.
Transitive attraction implies connected components.
Union-Find (DSU) or BFS/DFS to find components efficiently.
Minimum steps = number of connected components - 1.
Edge cases: all isolated (answer n-1), all connected (answer 0).
Optimization: use spatial data structures (e.g., k-d tree, grid) to avoid O(n^2) edge checks.

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