Katkat
Back

Implement Data Structure for Top-K Elements in Streams

PinterestData Scientist · Onsite
MediumData ScientistOnsiteCoding & Algorithms

Last updated

This question evaluates competency in streaming algorithms, dynamic data structures for maintaining top-K elements in real time, and scalability considerations for handling large or distributed input streams.

Scenario

Analytics feature that must constantly report the K largest numbers seen so far.

Question

Implement a data structure that ingests a stream of integers and returns the top-K elements at any moment. How do you extend it to very large K or distributed streams?

Hints

Maintain a min-heap of size K; for distribution, merge local heaps or use count-min sketches.