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 Rippling.

What role is this question designed for?

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

Compute unique-dasher concurrency with tie-breaking

Company: Rippling

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given N delivery assignments, each as (dasherId, startTime, endTime) with 0 <= startTime < endTime. A single dasher may hold multiple overlapping orders. Design an algorithm to compute: ( 1) the maximum number of simultaneously active dashers at any moment (count each dasher at most once at any instant), and ( 2) one timestamp (or interval) when this maximum occurs. Use an event-sweep approach: specify the event format, how you avoid double-counting when the same dasher has multiple overlapping orders (e.g., maintain a per-dasher active-order counter that changes the global active-dasher count only on 0->1 and 1->0 transitions), and your tie-breaking policy when multiple events share the same timestamp (process end (- 1) before start (+ 1)). In Python, show a correct sort key that enforces these rules (e.g., key=(time, delta, dasherId) with delta in {-1,+1}) and explain why putting dasherId before delta can break correctness. Analyze time and space complexity.

Quick Answer: The question evaluates understanding of sweep-line/event-sweep algorithms, interval overlap handling, tie-breaking and stable sort ordering as they affect deduplicating concurrent entities, situated in the Coding & Algorithms domain.

You are given a list of delivery assignments. Each assignment is a tuple `(dasherId, startTime, endTime)` with `0 <= startTime < endTime`. An assignment is active on the half-open interval `[startTime, endTime)`. A single dasher may hold multiple overlapping orders, but at any instant that dasher must be counted at most once. Write a function `solution(assignments)` that returns a list `[maxDashers, left, right]` where: - `maxDashers` is the maximum number of distinct dashers active at the same time. - `[left, right)` is the earliest interval between consecutive event times where this maximum occurs. - If `assignments` is empty, return `[0, -1, -1]`. Expected approach: use an event sweep. - Represent each order as two events `(time, delta, dasherId)`. - Use `delta = +1` for a start event and `delta = -1` for an end event. - Maintain a per-dasher active-order counter. The global active-dasher total changes only when a dasher transitions from `0 -> 1` active orders or from `1 -> 0` active orders. - When multiple events share the same timestamp, process all end events before start events. In Python, a correct sort key is `key=lambda e: (e[0], e[1], e[2])` because `-1 < +1`. - A key like `(time, dasherId, delta)` can break correctness because it may process a start at time `t` before an end at time `t` just because the start has a smaller `dasherId`, violating the required end-before-start tie rule. Important: process all events at the same timestamp before evaluating the interval to the next timestamp.

Constraints

0 <= N <= 2 * 10^5, where N is the number of assignments
0 <= startTime < endTime <= 10^9
dasherId is an integer
The assignments are not necessarily sorted

Examples

Input: []

Expected Output: [0, -1, -1]

Explanation: There are no assignments, so the maximum number of active dashers is 0 and no interval exists.

Input: [(1, 1, 5), (1, 2, 6), (2, 3, 4)]

Expected Output: [2, 3, 4]

Explanation: Dasher 1 has overlapping orders but still counts only once. On [3, 4), dashers 1 and 2 are both active, so the maximum distinct count is 2.

Input: [(1, 1, 3), (2, 3, 5)]

Expected Output: [1, 1, 3]

Explanation: At time 3, one order ends exactly when the other begins, so they are not simultaneous under [start, end) semantics. The maximum is 1, and the earliest interval is [1, 3).

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

Expected Output: [2, 2, 3]

Explanation: Dasher 1 hands off from one order to another at time 3. Processing all events at the same timestamp avoids double-counting or creating a false gap. The earliest interval with 2 distinct active dashers is [2, 3).

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

Expected Output: [3, 2, 5]

Explanation: From time 2 to 5, dashers 1, 2, and 3 are active. Dasher 1 still counts once even though it has two overlapping orders. The maximum distinct count is 3 on [2, 5).

Solution

def solution(assignments):
    from collections import defaultdict

    if not assignments:
        return [0, -1, -1]

    events = []
    for dasher_id, start_time, end_time in assignments:
        events.append((start_time, 1, dasher_id))   # start event
        events.append((end_time, -1, dasher_id))    # end event

    # Sort by time, then delta so end (-1) comes before start (+1), then dasherId.
    # Do not sort as (time, dasherId, delta): that can violate the required
    # end-before-start rule when different dashers share the same timestamp.
    events.sort(key=lambda e: (e[0], e[1], e[2]))

    active_orders = defaultdict(int)  # per-dasher active order count
    active_dashers = 0                # distinct dashers currently active

    best_count = 0
    best_start = -1
    best_end = -1

    i = 0
    m = len(events)

    while i < m:
        time = events[i][0]

        # Process every event at this timestamp before evaluating the interval
        # to the next timestamp.
        while i < m and events[i][0] == time:
            _, delta, dasher_id = events[i]

            if delta == -1:
                active_orders[dasher_id] -= 1
                if active_orders[dasher_id] == 0:
                    active_dashers -= 1
                    del active_orders[dasher_id]
            else:  # delta == +1
                if active_orders[dasher_id] == 0:
                    active_dashers += 1
                active_orders[dasher_id] += 1

            i += 1

        if i < m:
            next_time = events[i][0]
            if active_dashers > best_count:
                best_count = active_dashers
                best_start = time
                best_end = next_time

    return [best_count, best_start, best_end]

Time complexity: O(N log N). Space complexity: O(N).

Hints

Turn every assignment into two sweep events. What event ordering guarantees that an order ending at time t is removed before an order starting at time t is added?
Because the same dasher can have overlapping orders, keep a hash map from dasherId to its active-order count. Only change the distinct-dasher total when that count moves between 0 and 1.

Quick Overview

The question evaluates understanding of sweep-line/event-sweep algorithms, interval overlap handling, tie-breaking and stable sort ordering as they affect deduplicating concurrent entities, situated in the Coding & Algorithms domain.