Word Frequency / Streaming Aggregation

Problem

Given a large stream of log lines, return the top-k most frequent tokens. The stream may be far larger than memory, so an exact in-memory tally is not always possible — be ready to discuss the memory-bounded variant.

Input / Output

• Input: a stream (or very large file) of tokens, and an integer k.
• Output: the k most frequent tokens, most frequent first.

Constraints

• The stream may not fit in memory; token cardinality can be very high.
• Ties may be broken arbitrarily unless the interviewer specifies (e.g. lexicographic).

Example

logs -> top 3 tokens by count