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 Data Scientist candidates at Uber during technical interviews.

Compute maximum concurrent trips from intervals

Q: Compute maximum concurrent trips from intervals

This question evaluates a candidate's skill in designing efficient algorithms for interval overlap counting, including event ordering, handling half-open interval edge cases, and reasoning about concurrent activity timing.

Company: Uber

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You’re given n trip intervals [start, end) in seconds, where start < end, representing when a rider’s trip starts and ends in a city on a specific day. Implement a function that returns (a) the maximum number of concurrent trips at any time, and (b) one time t at which this maximum occurs. Requirements: - If one trip ends exactly when another starts (end == start), they do NOT overlap (half-open intervals). - Time values are integers in [0, 1e9]; n ≤ 1e5. - Aim for O(n log n) time and O(1) extra space beyond the input (you may reorder in place). - Return any valid time t achieving the maximum. Example: Input: [[0,10],[5,12],[11,13],[2,7]] → Output: max = 3, t = 5 (any t in [5,7)). Follow-ups: - Also return the smallest time range [L, R) over which the maximum concurrency holds continuously. - Discuss how your approach changes if the intervals are streaming and you can’t store all of them.

Quick Answer: This question evaluates a candidate's skill in designing efficient algorithms for interval overlap counting, including event ordering, handling half-open interval edge cases, and reasoning about concurrent activity timing.

Part 1: Maximum Concurrent Trips and Earliest Time

You are given a list of half-open trip intervals [start, end), where start < end. Return a tuple (max_count, t), where max_count is the maximum number of trips happening at the same time, and t is the earliest integer time at which this maximum occurs. If one trip ends exactly when another starts, they do not overlap. If the input is empty, return (0, None).

Constraints

0 <= n <= 10^5
0 <= start < end <= 10^9
Intervals are half-open: [start, end)
If end == start for two trips, they do not overlap
An O(n log n) time solution is expected

Examples

Input: [[0, 10], [5, 12], [11, 13], [2, 7]]

Expected Output: (3, 5)

Explanation: The maximum overlap is 3, first reached at time 5.

Input: [[1, 3], [3, 5]]

Expected Output: (1, 1)

Explanation: The intervals touch at 3 but do not overlap, so the maximum is 1.

Input: []

Expected Output: (0, None)

Explanation: No trips means no concurrency.

Input: [[4, 9]]

Expected Output: (1, 4)

Explanation: A single interval has maximum concurrency 1 starting at its own start.

Input: [[2, 6], [2, 5], [2, 4], [6, 8]]

Expected Output: (3, 2)

Explanation: Three trips start together at time 2.

Hints

Sort all start times and end times separately, then sweep through them with two pointers.
Because the intervals are half-open, when a start time equals an end time, process the end first.

Part 2: Earliest Continuous Range of Maximum Concurrency

You are given a list of half-open trip intervals [start, end), where start < end. Return a tuple (max_count, L, R), where max_count is the maximum number of concurrent trips, and [L, R) is the earliest continuous time range during which the number of active trips equals max_count at every instant. If the maximum occurs on multiple disjoint ranges, return the earliest such range. If the input is empty, return (0, None, None).

Constraints

0 <= n <= 10^5
0 <= start < end <= 10^9
Intervals are half-open: [start, end)
If end == start for two trips, they do not overlap
An O(n log n) time solution is expected

Examples

Input: [[0, 10], [5, 12], [11, 13], [2, 7]]

Expected Output: (3, 5, 7)

Explanation: The concurrency is 3 for the continuous range [5, 7).

Input: [[0, 2], [1, 3], [4, 6], [5, 7]]

Expected Output: (2, 1, 2)

Explanation: Maximum concurrency 2 happens on [1, 2) and [5, 6), so return the earliest one.

Input: []

Expected Output: (0, None, None)

Explanation: No trips means no maximum range.

Input: [[1, 2], [2, 3]]

Expected Output: (1, 1, 3)

Explanation: Even though the intervals only touch, the concurrency stays at 1 continuously from time 1 to 3.

Input: [[0, 10], [5, 8], [8, 12]]

Expected Output: (2, 5, 10)

Explanation: At time 8 one trip ends and another starts, but the concurrency remains 2 continuously on [5, 10).

Hints

The active-trip count only changes at interval boundaries, so sweep across sorted unique event times.
Aggregate all changes at the same timestamp; if a trip ends and another starts at the same time, the maximum range may continue without a break.

Part 3: Maximum Concurrent Trips in a Start-Sorted Stream

Trips arrive as a stream of half-open intervals [start, end), already sorted by nondecreasing start time. You cannot store all intervals. Process the stream and return a tuple (max_count, t), where max_count is the maximum number of concurrent trips seen so far, and t is the earliest time at which this maximum occurs. If the input is empty, return (0, None). For testing, the stream is provided as a list, but your algorithm should work in one pass using only memory proportional to the number of active trips.

Constraints

0 <= n <= 10^5
0 <= start < end <= 10^9
Intervals are half-open: [start, end)
The input is sorted by nondecreasing start time
Use only O(k) extra space, where k is the number of active trips

Examples

Input: [[0, 10], [2, 7], [5, 12], [11, 13]]

Expected Output: (3, 5)

Explanation: The maximum number of active trips is 3, first reached when the trip starting at 5 arrives.

Input: []

Expected Output: (0, None)

Explanation: No trips means no concurrency.

Input: [[1, 4], [1, 3], [1, 2], [2, 5]]

Expected Output: (3, 1)

Explanation: Three trips are active at time 1.

Input: [[0, 1], [1, 2], [2, 3]]

Expected Output: (1, 0)

Explanation: Trips only touch at boundaries, so concurrency never exceeds 1.

Input: [[0, 10], [10, 20], [10, 15], [12, 18]]

Expected Output: (3, 12)

Explanation: The trip ending at 10 does not overlap the two trips starting at 10, and the maximum of 3 is first reached at time 12.

Hints

Keep the end times of currently active trips in a min-heap.
Before adding a new trip [s, e), remove every active trip with end <= s, because touching intervals do not overlap.

Quick Overview

This question evaluates a candidate's skill in designing efficient algorithms for interval overlap counting, including event ordering, handling half-open interval edge cases, and reasoning about concurrent activity timing.