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 peak busy dashers with overlaps | Rippling Coding Question

Compute peak busy dashers with overlaps

Company: Rippling

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given delivery logs as (dasherId, startTime, endTime) with integer times, where endTime is exclusive. A single dasher may accept multiple orders that overlap in time. a) Compute the maximum number of busy dashers at any moment, counting each dasher at most once at any given time even if they hold multiple overlapping orders. b) Design and implement an O(n log n) sweep-line algorithm: describe how you create events, how you deduplicate multiple simultaneous starts for the same dasher, and how you handle ties so that an end at time t is processed before a start at time t. c) If your event tuples include dasherId, explain the pitfall of sorting by (dasherId, time, delta) and provide a correct key/comparator (e.g., (time, delta, dasherId) with delta ordered so -1 comes before + 1). d) How would your approach change if dashers could not take overlapping orders (i.e., you’re asked for the peak number of concurrent orders instead)? Analyze time and space complexity.

Quick Answer: This question evaluates skills in interval-overlap reasoning, sweep-line algorithm design, event creation and deduplication, comparator and tie-breaking subtleties, and asymptotic time/space complexity analysis within the Coding & Algorithms domain.

Part 1: Peak Busy Dashers with Overlapping Orders

You are given delivery logs where each log is [dasherId, startTime, endTime]. Times are integers, and endTime is exclusive. A dasher may hold multiple overlapping or back-to-back orders, but at any single moment that dasher should count at most once. Return the maximum number of distinct dashers that are busy at the same time.

Constraints

0 <= len(logs) <= 200000
0 <= dasherId <= 10^9
0 <= startTime < endTime <= 10^9
endTime is exclusive

Examples

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

Expected Output: 2

Explanation: Dasher 1 is busy continuously from 1 to 6 after merging its overlapping orders. Dasher 2 overlaps from 4 to 6, so the peak is 2.

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

Expected Output: 1

Explanation: Because endTime is exclusive, the first order ends before the second begins at time 3.

Hints

First combine each dasher's intervals so overlapping or touching intervals become one busy block.
After merging per dasher, the problem becomes a standard interval overlap sweep.

Part 2: Sweep-Line Busy Dashers in O(n log n)

You are given delivery logs where each log is [dasherId, startTime, endTime]. Times are integers and endTime is exclusive. Implement an O(n log n) sweep-line algorithm that computes the maximum number of busy dashers. Create start and end events for every order, process all events in chronological order, and when times tie, process end events before start events. A dasher may have multiple overlapping orders, so use per-dasher active-order counts: a dasher should increase the busy count only when its active count changes from 0 to 1, and decrease it only when its active count changes from 1 to 0.

Constraints

0 <= len(logs) <= 200000
0 <= dasherId <= 10^9
0 <= startTime < endTime <= 10^9
You should target O(n log n) time

Examples

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

Expected Output: 2

Explanation: Dasher 1 starts two orders at time 1 but still counts as only one busy dasher. Dasher 2 overlaps later, so the peak is 2.

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

Expected Output: 2

Explanation: At time 3, dasher 1's first order ends before its second begins. Dasher 2 also starts at 3, so the peak becomes 2.

Hints

Sort events by (time, delta, dasherId) if you encode end as -1 and start as +1.
Multiple starts for the same dasher at the same time should not raise the busy count more than once; track active orders per dasher.

Part 3: Correctly Sort Sweep-Line Events

Each event is represented as [dasherId, time, delta], where delta is -1 for an end event and 1 for a start event. Sorting by (dasherId, time, delta) is incorrect because it groups events by dasher instead of processing the global timeline. Write a function that returns the events in the correct sweep-line order: sort by time ascending, then delta ascending so -1 comes before 1, then dasherId ascending.

Constraints

0 <= len(events) <= 200000
0 <= dasherId <= 10^9
0 <= time <= 10^9
delta is either -1 or 1

Examples

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

Expected Output: [[1, 3, 1], [1, 5, -1], [2, 5, 1]]

Explanation: Time 3 comes before time 5. At time 5, the end event comes before the start event.

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

Expected Output: [[1, 4, -1], [2, 4, 1], [3, 4, 1]]

Explanation: All events share the same time, so delta decides first and dasherId breaks the remaining tie.

Hints

The sweep-line must move through time globally, so time has to be the first sort key.
When two events share the same time, an end event should come before a start event because endTime is exclusive.

Part 4: Peak Concurrent Orders When Dashers Cannot Overlap Orders

You are given delivery logs where each log is [dasherId, startTime, endTime]. Times are integers and endTime is exclusive. In this version, dashers cannot take overlapping orders. That means each active order belongs to a different dasher, so the task reduces to finding the maximum number of concurrent orders. Return the peak number of simultaneously active orders.

Constraints

0 <= len(logs) <= 200000
0 <= dasherId <= 10^9
0 <= startTime < endTime <= 10^9
Orders for the same dasher do not overlap

Examples

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

Expected Output: 3

Explanation: All three orders overlap between times 3 and 4.

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

Expected Output: 1

Explanation: Because endTime is exclusive, these intervals only touch and never overlap.

Hints

You no longer need per-dasher active counts, because each order can be counted directly.
Use the standard interval sweep: add +1 at starts and -1 at ends, with ends processed before starts at the same time.

Quick Overview

This question evaluates skills in interval-overlap reasoning, sweep-line algorithm design, event creation and deduplication, comparator and tie-breaking subtleties, and asymptotic time/space complexity analysis within the Coding & Algorithms domain.