Meta·Data Scientist·Technical Phone Screen·Senior

SeniorPrefer not to say

Sep 2025Remote

Summary

Meta data scientist interview with a pretty gnarly algorithmic design question about concurrent call statistics. One round, one problem, a lot of moving parts. Walked out not totally sure how I did.

Questions Asked (1)

Given N call session intervals [start, end) in UNIX seconds, design an algorithm to compute the 95th percentile of per-minute concurrent call counts over a fixed 24-hour window. The input is a potentially memory-exceeding unsorted stream, duplicate call IDs must be deduplicated by (start, end) pair, half-open interval semantics apply, and the target complexity is O(n log n + M) where M is 1440. Describe your data structures, how you'd handle tie-breaking in the percentile calculation, and how you'd extend this to compute the metric per country if each interval includes a country code.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

This one took me a minute to even parse fully.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints and edge cases, then propose a sweep-line algorithm that processes events in sorted order to compute per-minute concurrent counts. Emphasize deduplication, half-open interval handling, and the O(n log n + M) complexity. Finally, discuss percentile tie-breaking and extension to per-country metrics.

Pro tip: Mention that you would validate the algorithm with a small brute-force implementation and discuss how to handle memory constraints by external sorting or streaming with a bounded priority queue for deduplication.

1. Clarify requirements and edge cases

Confirm interval semantics (half-open), deduplication criteria, percentile definition (e.g., nearest-rank or linear interpolation), and tie-breaking rules. Discuss memory constraints and whether the stream can be sorted externally.

2. Design deduplication and event generation

Deduplicate intervals by (start, end) using a hash set or external sort. For each unique interval, generate two events: +1 at start, -1 at end. Store events in a list.

3. Sort events and compute per-minute counts

Sort events by timestamp (O(n log n)). Sweep through events, maintaining a running count. For each minute boundary (0 to 1439), record the count after processing all events up to that minute. This yields an array of 1440 counts.

4. Compute 95th percentile with tie-breaking

Sort the 1440 counts (or use selection algorithm). For percentile, use nearest-rank method: index = ceil(0.95 * 1440) - 1. For ties, define a consistent rule (e.g., take the higher value or interpolate).

5. Extend to per-country metrics

Partition events by country code. For each country, run the same sweep-line algorithm independently, producing per-country per-minute counts. Then compute 95th percentile per country. Discuss memory trade-offs and possible optimizations (e.g., processing countries in batches).

Key Points to Mention

Half-open interval semantics: [start, end) means the call is active from start inclusive to end exclusive.
Deduplication by (start, end) pair: use a hash set or external sort to remove duplicates.
Sweep-line algorithm: sort events, maintain running count, and record counts at minute boundaries.
Complexity: O(n log n) for sorting events, O(M) for sweeping, where M=1440.
Percentile calculation: nearest-rank method and tie-breaking (e.g., take the higher value or interpolate).
Per-country extension: partition events by country, process each independently, and discuss memory/performance trade-offs.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.