← Uber Interview Insights

Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Apr 2026

Summary

Uber SWE coding round, one graph connectivity problem that looks deceptively simple but has a subtle condition on distance. The DSU approach clicked for me eventually but I wasted time on a brute-force path first.

Questions Asked (1)

Q1

Given a list of 2D points, find the number of connected components where two points are directly connected if they share the same row or column and their distance is strictly less than d. Connectivity is transitive.

Algorithms & Data Structures
Author's notes

My first instinct was to check every pair of points, which is obviously too slow but I coded it halfway anyway before catching myself.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the points as nodes in a graph where edges connect points sharing a row or column with distance < d, then count connected components using Union-Find (DSU). To avoid O(n^2) pairwise checks, group points by row and by column, sort each group by coordinate, and union adjacent points within distance d.

Pro tip: Mention that the distance condition is 1D within a row or column, so sorting each group and checking adjacent points suffices; this reduces the time complexity to O(n log n) and shows you optimize beyond the naive approach.

1. Clarify and Restate

Confirm the definition of 'directly connected' (same row or column, distance < d) and that connectivity is transitive. Ask about input size, coordinate ranges, and whether d is inclusive or exclusive.

2. Model as Graph

Treat each point as a node. Add an edge between two points if they share a row or column and their 1D distance is strictly less than d. The answer is the number of connected components in this graph.

3. Optimize Edge Creation

Group points by row and by column. For each group, sort points by the relevant coordinate (x for rows, y for columns). Then, only union adjacent points in the sorted order if their distance < d, since any farther pair would be connected via the chain of closer points.

4. Use Union-Find

Initialize a DSU with n components. For each valid adjacent pair, perform a union operation. After processing all groups, the number of distinct roots in the DSU is the number of connected components.

5. Analyze Complexity

Time: O(n log n) due to sorting; space: O(n) for DSU and grouping. Discuss potential edge cases like duplicate points, empty input, or large d.

Key Points to Mention

  • Union-Find (Disjoint Set Union) with path compression and union by rank for near-constant time operations.
  • Grouping points by row and by column to avoid O(n^2) pairwise comparisons.
  • Sorting each group and only checking adjacent points because the distance condition is 1D and transitive.
  • Handling duplicates: if multiple points share the same coordinates, they are distance 0 apart and should be unioned.
  • Time and space complexity analysis: O(n log n) time, O(n) space.
  • Edge cases: empty input, single point, d <= 0, and points with same row/column but distance >= d.

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