← Uber Interview Insights

Uber·Backend Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say
Jun 2026Remote

Summary

Uber backend interview that went deep into dynamic graph connectivity, specifically a variant of the rider-connection problem where you have to handle both union and deletion operations on a graph over time. Harder than I expected and I'm not sure I fully nailed the complexity analysis.

Questions Asked (1)

Q1

You have a time-sorted event log with two types of events: two riders sharing a ride (connecting them in a graph), and one rider blocking another (removing that edge and potentially splitting a connected component). Find the earliest timestamp at which all riders belong to a single connected component. Standard union-find won't work because it doesn't support deletions. What's your approach, and what's the time complexity?

Algorithms & Data StructuresTechnical Trade-offsSystem Design
Author's notes

This wrecked me a little.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize that deletions make incremental union-find infeasible, so process the log in reverse: start from the final graph state and treat each blocking event as an addition and each ride-sharing event as a removal. Use union-find on the reversed timeline to track when the graph first becomes connected, then map back to the original timestamp.

Pro tip: Mention that if the final graph is already connected, the answer is the last timestamp (or zero if no events needed); this shows you handle edge cases and understand the problem's monotonicity.

1. Clarify problem constraints and edge cases

Confirm that events are time-sorted, that blocking removes an existing edge (or is a no-op), and that we need the earliest time when the graph is connected. Discuss what happens if connectivity is never achieved.

2. Explain why standard union-find fails

State that union-find supports only incremental edge additions, not deletions, so processing events forward would require dynamic connectivity structures that are more complex.

3. Propose reverse processing with union-find

Describe building the final graph by applying all events forward, then processing events in reverse: a blocking event becomes an edge addition (union), and a ride-sharing event becomes an edge removal (which we ignore for union-find but must handle for connectivity tracking).

4. Track connectivity and find the earliest timestamp

During reverse processing, maintain the number of connected components. The moment it drops to 1, record the corresponding original timestamp. If the final graph is already connected, the answer is the last event's time (or 0 if no events).

5. Analyze time and space complexity

State that building the final graph and reverse processing each take O(E α(V)) time with union-find, where E is the number of events and V the number of riders, and space is O(V + E) for storing the graph and events.

Key Points to Mention

  • Reverse processing converts deletions into additions, enabling union-find.
  • Union-find with path compression and union by rank gives near-constant amortized time per operation.
  • Need to handle the case where the graph never becomes connected (return -1 or equivalent).
  • If the final graph is already connected, the answer is the last timestamp (or 0 if no events).
  • Complexity: O(E α(V)) time, O(V + E) space.
  • Mention that this approach assumes blocking events only remove existing edges; if not, they are no-ops.

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