2dbi
Home/Datadog/Merge Sorted Streams / Top-K
DDatadog·DSAL3Technical Phone Screen

Merge Sorted Streams / Top-K

Problem

Merge k sorted event streams into one ordered stream, then return the top-k by a score.

Example

k streams of timestamped events -> merged ordered; top 10 by value

Constraints

  • k can be large

Approach

Min-heap of stream heads; second heap for top-k. Discuss O(N log k).

added 6 days ago
LeadersAccount