Compute 95th-percentile call concurrency
Company: Meta
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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.
Quick Answer: 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 half-open call intervals and a minute-aligned window, de-duplicate identical intervals, count how many calls overlap each minute bucket, and return the nearest-rank 95th percentile of those per-minute counts.
Constraints
- Intervals are [start, end) UNIX-second pairs.
- windowStart and windowEnd define the half-open analysis window.
- Identical (start, end) intervals are counted once.
- A minute bucket is counted if an interval overlaps any timestamp in that minute.
Examples
Input: ([[0,60],[0,120],[60,180]], 0, 180)
Expected Output: 2
Explanation: The three minute buckets have counts 2, 2, and 1.
Input: ([[0,60],[0,60],[30,60],[60,120]], 0, 120)
Expected Output: 2
Explanation: Duplicate intervals are ignored and end boundaries are half-open.
Hints
- Clip intervals to the requested window before bucketing.
- Use a difference array over minute buckets, then sort the counts for nearest-rank percentile.