How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Find earliest time all riders become connected

Quick Overview

This question evaluates graph connectivity and dynamic event-processing skills, testing conceptual understanding of connectivity in undirected graphs as well as practical algorithmic implementation for tracking when components merge; it belongs to the Coding & Algorithms category.

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given activity logs for a ride-sharing app. Each log entry indicates that two riders shared a ride at a certain time, which creates an undirected connection between them (they can “reach” each other either directly or through other riders). ## Problem Given: - An integer `n` = number of riders, labeled `0..n-1`. - A list `logs`, where each entry is `[timestamp, a, b]` meaning rider `a` and rider `b` shared a ride at `timestamp`. Return the **earliest timestamp** at which **all riders become mutually connected** (i.e., the graph of riders becomes a single connected component). If this never happens, return `-1`. ### Notes / Constraints - `logs` may be unsorted. - Multiple logs can share the same timestamp. - You may assume `0 <= a, b < n`, `a != b`. - Choose reasonable time and space complexity for large inputs (e.g., up to `1e5` logs). ## Follow-up (harder variant) Now suppose riders can also **block** each other. A block means two riders should be treated as **not connected**, even if there is a path between them that would otherwise connect them. You may model this as additional events like `[timestamp, "BLOCK", x, y]` (and optionally `[timestamp, "UNBLOCK", x, y]`). Discuss how you would modify your approach to support block events, and how you would determine the earliest time when all riders are mutually connected under these constraints.

Quick Answer: This question evaluates graph connectivity and dynamic event-processing skills, testing conceptual understanding of connectivity in undirected graphs as well as practical algorithmic implementation for tracking when components merge; it belongs to the Coding & Algorithms category.

Part 1: Earliest Timestamp When All Riders Become Connected

You are given activity logs for a ride-sharing app. Each log entry [timestamp, a, b] means riders a and b shared a ride at that time, creating a permanent undirected connection between them. Two riders are considered connected if there is a path between them through one or more shared rides. Return the earliest timestamp at which all n riders belong to a single connected component. If this never happens, return -1. If n is 1, return 0 because the only rider is already connected to themself.

Constraints

1 <= n <= 10^5
0 <= len(logs) <= 2 * 10^5
Each log is [timestamp, a, b] with 0 <= a, b < n and a != b
Timestamps are integers and logs may be unsorted
An efficient near-linear solution after sorting is expected

Examples

Input: (6, [[20190104, 3, 4], [20190101, 0, 1], [20190107, 2, 3], [20190211, 1, 5], [20190224, 2, 4], [20190301, 0, 3], [20190312, 1, 2], [20190322, 4, 5]])

Expected Output: 20190301

Explanation: After sorting by time, the last merge needed to connect the two remaining groups happens at timestamp 20190301.

Input: (4, [[3, 0, 1], [1, 2, 3]])

Expected Output: -1

Explanation: The riders end up in two separate components: {0,1} and {2,3}.

Input: (1, [])

Expected Output: 0

Explanation: A single rider is trivially fully connected.

Input: (4, [[2, 0, 1], [2, 1, 2], [2, 2, 3]])

Expected Output: 2

Explanation: All riders become connected during timestamp 2.

Hints

Sort the logs by timestamp so you process connections in chronological order.
Use a Disjoint Set Union (Union-Find) structure and keep track of how many connected components remain.

Part 2: Earliest Valid Connectivity with BLOCK / UNBLOCK Events

You are given n riders and a list of events. Each event is [timestamp, type, a, b], where type is one of: - 'RIDE': riders a and b become permanently connected in the ride graph. - 'BLOCK': pair (a, b) becomes blocked. - 'UNBLOCK': remove the block on pair (a, b) if it exists. At time t, the ride graph contains all RIDE edges with timestamp <= t. A pair of riders is required to be connected only if that pair is not currently blocked. The network is considered fully connected under blocking constraints if every unblocked pair of riders lies in the same ride-connected component. Equivalently, any pair of riders that is in different ride components must currently be blocked. Return the earliest timestamp when this condition is true after applying all events at that timestamp. If it never becomes true, return -1. If n is 1, return 0. Notes: - Events may be unsorted. - RIDE edges never disappear. - Repeated BLOCK on an already blocked pair or UNBLOCK on a non-blocked pair has no extra effect. - For the same unordered pair and the same timestamp, there will not be both a BLOCK and an UNBLOCK event.

Constraints

1 <= n <= 10^5
0 <= len(events) <= 2 * 10^5
Each event is [timestamp, type, a, b] with type in {'RIDE', 'BLOCK', 'UNBLOCK'}
0 <= a, b < n and a != b
Events may be unsorted, and multiple events may share the same timestamp
An O(m log m) to O(m log^2 n) style solution is appropriate

Examples

Input: (3, [[1, 'RIDE', 0, 1], [2, 'BLOCK', 0, 2], [2, 'BLOCK', 1, 2]])

Expected Output: 2

Explanation: At time 2, riders 0 and 1 are connected, and both cross-component pairs involving rider 2 are blocked. Therefore every unblocked pair is connected.

Input: (4, [[1, 'BLOCK', 0, 2], [1, 'BLOCK', 0, 3], [1, 'BLOCK', 1, 2], [1, 'BLOCK', 1, 3], [2, 'RIDE', 0, 1], [3, 'RIDE', 2, 3]])

Expected Output: 3

Explanation: At time 3, the two ride-components are {0,1} and {2,3}. All four cross pairs between those components are blocked, so the condition holds.

Input: (3, [[1, 'BLOCK', 0, 2], [2, 'RIDE', 0, 1], [3, 'UNBLOCK', 0, 2], [4, 'RIDE', 1, 2]])

Expected Output: 4

Explanation: The unblock at time 3 breaks the condition. It becomes true again only when the whole ride graph becomes connected at time 4.

Input: (4, [[1, 'RIDE', 0, 1], [2, 'BLOCK', 0, 2]])

Expected Output: -1

Explanation: There are still many unblocked pairs across different ride-components, so the condition is never satisfied.

Input: (1, [])

Expected Output: 0

Explanation: A single rider satisfies the condition immediately.

Hints

Think in terms of ride-connected components. The condition is true exactly when every pair of riders in different components is currently blocked.
Maintain two counts: the total number of cross-component pairs, and how many active blocked pairs currently cross components. Union-Find helps with merges, and small-to-large map merging helps update blocked-pair counts efficiently.

Quick Overview