Uber·Backend Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jun 2026Remote

Summary

Uber backend interview that went deep on dynamic graph connectivity, specifically a variant of the rider-connection problem where you have to handle both link additions and deletions in a time-sorted event log. The problem was harder than I expected and the follow-up about block events basically invalidated the approach I'd been building toward.

Questions Asked (1)

You have a time-sorted log of events between riders: connect events (two riders shared a ride) and block events (a rider blocked another, severing that link and potentially splitting a connected component). Find the earliest timestamp at which all riders belong to a single component. Standard Union-Find won't work because it can't handle deletions. Walk through your approach, its time complexity, and the key invariant that makes it correct.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

This wrecked me a little.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Process events in reverse chronological order using a Union-Find structure that only adds edges, treating block events as additions of edges in the reversed timeline. Track the number of connected components and find the earliest timestamp where the component count becomes 1, which corresponds to the latest time in reverse processing.

Pro tip: Mention that this is a classic offline dynamic connectivity problem and that reversing time is a common trick to convert deletions into additions, which Union-Find handles efficiently. Also, clarify that if the graph never becomes fully connected, return -1 or the appropriate sentinel.

1. Understand the problem and constraints

Restate the problem: given a time-sorted log of connect and block events, find the earliest time when all riders are in one connected component. Note that blocks can split components, so standard Union-Find fails.

2. Reverse time to convert deletions to additions

Process events from latest to earliest. In reverse, a block event becomes an addition of an edge (reconnecting riders), and a connect event becomes a removal of an edge (which we can ignore if we only care about the moment all are connected).

3. Use Union-Find to track connectivity

Initialize Union-Find with all riders as separate components. Process reversed events: for each block event, union the two riders; for connect events, do nothing (since in reverse they represent edge removals, which we don't need to simulate if we stop at the first time all are connected).

4. Track component count and find the answer

Maintain the number of connected components. After each union, if the count becomes 1, record the timestamp of the current event (in original time) as a candidate. Continue until all events are processed; the earliest such timestamp is the answer.

5. Analyze complexity and correctness

Time complexity: O(E α(V)) where E is number of events and V is number of riders, due to Union-Find operations. Space: O(V). Correctness relies on the invariant that after processing events in reverse up to time t, the Union-Find represents the connectivity at time t in the original timeline.

Key Points to Mention

Reverse time processing to turn deletions into additions, enabling Union-Find.
Union-Find with path compression and union by rank for near-constant time operations.
Maintain a component count to detect when all riders are connected.
The key invariant: after processing reversed events up to time t, the DSU reflects the graph at time t in the original timeline.
Edge cases: no events, already connected initially, never fully connected.
Time complexity O(E α(V)) and space O(V).

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