Compute peak busy dashers with overlaps

Q: Compute peak busy dashers with overlaps

This is a Coding & Algorithms interview question from Rippling for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Compute peak busy dashers with overlaps

Comments (0)