Compute unique-dasher concurrency with tie-breaking

Q: Compute unique-dasher concurrency with tie-breaking

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.

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 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: (

the maximum number of simultaneously active dashers at any moment (count each dasher at most once at any instant), and (
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 (-
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.

Compute unique-dasher concurrency with tie-breaking

Quick Overview

Comments (0)