Katkat
Back

Find top-K frequent elements in a stream

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates understanding of streaming algorithms, frequency estimation, and data-structure-based top-K selection, emphasizing space/time and accuracy trade-offs when processing large or unbounded data.

You receive a large stream of items (e.g., integers or strings) that may not fit in memory. Design an algorithm that can return the top K most frequent items.

Requirements:

  • Provide an exact solution when the number of distinct items fits in memory.
  • Provide an approximate solution when distinct items are too many (state the error/accuracy tradeoff).

Explain time and space complexity for both approaches.