Compute 95th-percentile call concurrency
Overview
This question evaluates a candidate's ability to design scalable algorithms for computing the 95th-percentile of per-minute concurrent calls over a 24-hour window, testing competencies in streaming/event aggregation, de-duplication, percentile computation, and managing time and memory constraints.
Given N call sessions as half-open intervals [start, end) in UNIX seconds, design an algorithm to compute the 95th percentile of per-minute concurrent calls over the last 24 hours ending at 2025-09-01 00:00:00 UTC (i.e., minutes from 2025-08-31 00:00 to 2025-09-01 00:00). Requirements: (1) Input is an unsorted stream that may not fit in memory; (2) The same call_id may appear multiple times; treat duplicate intervals as one after de-duplication by (start,end); (3) A call active at timestamp t contributes to the minute floor(t/60); if an interval ends exactly at t, it does NOT contribute to that minute; zero-length intervals contribute nothing; (4) Return the 95th percentile (nearest-rank) of the 1440 per-minute concurrency counts; (5) Target time complexity O(n log n + M) where M=1440, and sublinear extra memory beyond storing the sweep-line events; (6) Describe your data structures (e.g., external sort + sweep or streaming bucketing), tie-breaking, and how you would extend it to compute the same metric per country if each interval carries a country code. Provide clear pseudocode and justify correctness.