Find top-K frequent elements in a stream
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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.
Quick Answer: 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.