Quick Overview

Assesses understanding of graph connectivity, temporal event processing, and dynamic graph data-structures for determining when a set of nodes becomes a single connected component.

Find earliest time all riders become connected

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given a time-ordered log of events involving Uber riders. Each event has a timestamp and two rider names. Event types: 1. `t X shared-ride-with Y` — riders `X` and `Y` shared a ride at time `t`, which creates an (undirected) connection between them. Two riders are considered **connected** if there is a path of shared rides between them (transitive connectivity). For example, if `A` shared with `B` and `B` shared with `C`, then `A` is connected to `C`. Example (already sorted by time): - `t1 Alice shared-ride-with Bob` - `t2 Charlie shared-ride-with Dan` - `t3 Bob shared-ride-with Charlie` - `t4 Alice shared-ride-with Eve` - `t5 Bob shared-ride-with Dan` Task: - Return the **earliest timestamp** at which **all riders that appear in the logs** become connected in a single connected component. If this never happens, return an appropriate value (e.g., `-1`). Follow-up: The log may also contain **block** events: - `t X blocked Y` — starting at time `t`, treat riders `X` and `Y` as **no longer directly connected by their shared-ride relationship** (i.e., the edge between `X` and `Y` is removed for times `>= t`, even if they shared earlier). How would you modify your approach to still find the earliest time when all riders are connected, given that connections can be both added (`shared-ride-with`) and removed (`blocked`)?

Quick Answer: Assesses understanding of graph connectivity, temporal event processing, and dynamic graph data-structures for determining when a set of nodes becomes a single connected component.

Part 1: Earliest Time All Riders Become Connected

You are given a time-ordered list of shared-ride events. Each event is a tuple `(timestamp, rider_a, rider_b)` meaning `rider_a` and `rider_b` shared a ride at that time, creating an undirected connection between them. Two riders are considered connected if there is a path of shared rides between them. Return the earliest timestamp at which all riders that appear anywhere in the log belong to a single connected component. If this never happens, return `-1`.

Constraints

  • `0 <= len(events) <= 2 * 10^5`
  • Timestamps are strictly increasing integers.
  • `rider_a` and `rider_b` are non-empty strings.
  • `rider_a != rider_b` for every event.
  • All riders that appear anywhere in the log must be considered when deciding connectivity.

Examples

Input: [(1, 'Alice', 'Bob'), (2, 'Charlie', 'Dan'), (3, 'Bob', 'Charlie'), (4, 'Alice', 'Eve'), (5, 'Bob', 'Dan')]

Expected Output: 4

Explanation: After time 3, Alice/Bob/Charlie/Dan are connected, but Eve is still separate. At time 4, Eve joins the same component, so the answer is 4.

Input: [(1, 'A', 'B'), (2, 'A', 'B'), (3, 'B', 'C')]

Expected Output: 3

Explanation: The duplicate edge at time 2 changes nothing. All three riders become connected at time 3.

Hints

  1. Model riders as nodes in an undirected graph, and process edges in time order.
  2. If you know the full set of riders in advance, a Disjoint Set Union (Union-Find) can track how many connected components remain.

Part 2: Earliest Time All Riders Become Connected with Shared and Blocked Events

You are given a time-ordered list of rider events. Each event is a tuple `(timestamp, action, rider_a, rider_b)`. If `action == 'shared'`, riders `rider_a` and `rider_b` become directly connected from that time onward. If `action == 'blocked'`, the direct edge between `rider_a` and `rider_b` is removed from that time onward. A later `shared` event for the same pair can add the edge again. Connectivity is still transitive through other riders. Return the earliest timestamp at which all riders that appear anywhere in the full log are connected at the same time. If this never happens, return `-1`.

Constraints

  • `0 <= len(events) <= 2 * 10^5`
  • Timestamps are strictly increasing integers.
  • `action` is either `'shared'` or `'blocked'`.
  • `rider_a` and `rider_b` are non-empty strings, and `rider_a != rider_b`.
  • The same pair may appear many times.
  • A `blocked` event for a pair that is not currently active has no effect.
  • All riders that appear anywhere in the log, including riders that only appear in block events, count toward the final connectivity check.

Examples

Input: [(1, 'shared', 'Alice', 'Bob'), (2, 'shared', 'Charlie', 'Dan'), (3, 'shared', 'Bob', 'Charlie'), (4, 'blocked', 'Alice', 'Bob')]

Expected Output: 3

Explanation: At time 3, all four riders are connected. The later block at time 4 breaks one direct edge, but the earliest successful time is still 3.

Input: [(1, 'shared', 'A', 'B'), (2, 'shared', 'B', 'C'), (3, 'blocked', 'B', 'C'), (4, 'shared', 'C', 'A')]

Expected Output: 2

Explanation: All riders are already connected at time 2. Even though they disconnect later and reconnect again, the earliest valid time is 2.

Hints

  1. A normal Union-Find handles edge additions well, but not deletions. Try processing the problem offline instead of updating one mutable graph directly.
  2. Think about the time interval during which each edge is active, then add that edge to a segment tree over time and use a rollback DSU while traversing it.

Loading coding console...