Top-K Frequent Elements from Stream

MediumPython

Problem

Meesho processes a massive stream of integer event identifiers, such as product views or search events. Return the k most frequent identifiers without storing the entire stream.

Implement an exact algorithm that consumes the input iterable once. If multiple identifiers have the same frequency, prefer the smaller identifier. Return results ordered by decreasing frequency, then increasing identifier.

Formal Specification

Implement top_k_frequent(stream, k).

stream is an iterable of integers. It may be a list, generator, or another single-pass iterable.
k is a positive integer.
Return a list of at most k integers, ranked by frequency and then identifier as specified above.
The input stream contains at least one element, and 1 <= k.

The solution must be exact. It is acceptable to store one frequency entry per distinct identifier, but the result-ranking structure should store no more than k identifiers.

Constraints

1 <= len(stream) <= 10^7
1 <= k <= 10^5
-10^9 <= stream[i] <= 10^9
stream may be a single-pass iterator
The number of distinct identifiers can be as large as len(stream)

Function Signature

def top_k_frequent(stream, k):

Meesho processes a massive stream of integer event identifiers, such as product views or search events. Return the k most frequent identifiers without storing the entire stream.

Formal Specification

Implement top_k_frequent(stream, k).

stream is an iterable of integers. It may be a list, generator, or another single-pass iterable.
k is a positive integer.
Return a list of at most k integers, ranked by frequency and then identifier as specified above.
The input stream contains at least one element, and 1 <= k.

The solution must be exact. It is acceptable to store one frequency entry per distinct identifier, but the result-ranking structure should store no more than k identifiers.