← Uber Interview Insights

Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Uber SWE interview with a graph/clustering problem that looks deceptively simple until you realize it's just connected components. Clean problem, well-defined, nothing too tricky about the setup.

Questions Asked (1)

Q1

You have n balls on a 2D plane, each with coordinates. Two balls attract each other if their Euclidean distance is strictly less than a threshold d. Attraction is transitive, so connected balls form a cluster. Each time step you pick one unabsorbed ball and absorb its entire connected cluster. What is the minimum number of time steps to absorb all balls?

Algorithms & Data Structures
Author's notes

Took me a beat to see past the physics flavor of the problem.

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 number of connected components. The minimum number of time steps equals the number of connected components, since each step absorbs exactly one entire component.

Pro tip: Mention that building the graph naively is O(n^2), but for large n you can use spatial indexing (e.g., grid or k-d tree) to find neighbors efficiently, though the worst-case remains O(n^2) due to the output size.

1. Understand the problem

Restate the problem: balls are nodes, edges if distance < d, and clusters are connected components. The goal is to find the minimum number of steps to absorb all balls.

2. Identify the key insight

Realize that each step can absorb exactly one connected component, so the minimum number of steps is exactly the number of connected components.

3. Choose an algorithm

Use Union-Find (DSU) to efficiently merge balls within distance d, or BFS/DFS on the implicit graph. Discuss time complexity: O(n^2) for pairwise checks, or O(n log n) with spatial partitioning for sparse cases.

4. Handle edge cases and optimizations

Consider cases like n=0, all balls isolated, or all connected. Mention spatial data structures (grid, k-d tree) to avoid O(n^2) when possible, but note worst-case remains O(n^2).

5. Conclude and verify

State that the answer is the number of connected components. Walk through a small example to verify, and discuss potential follow-up questions like dynamic updates.

Key Points to Mention

  • Graph modeling: nodes as balls, edges if Euclidean distance < d.
  • Connected components and transitivity of attraction.
  • Union-Find (Disjoint Set Union) for efficient merging.
  • Time complexity: O(n^2) naive, O(n log n) with spatial indexing for sparse cases.
  • Edge cases: n=0, all isolated, all connected.
  • Spatial data structures: grid, k-d tree, or sweep line for neighbor queries.

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