How should I practice Streaming Top K Frequent Elements?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon phone screen and onsite interview problems in FastPrep.

Is Streaming Top K Frequent Elements associated with Amazon?

FastPrep tags this as a Amazon phone screen and onsite interview coding practice problem when the problem catalog has that company and stage context.

Streaming Top K Frequent Elements

Amazon● HardFULLTIMENEW GRADPHONE SCREENONSITE INTERVIEW

Learn

Problem statement

Given an integer array stream and an integer k, process the values from left to right. After each new value arrives, return the current most frequent distinct values.

Return at most k values for each prefix.
Order values by decreasing frequency in the prefix.
When two values have the same frequency, place the smaller value first.

The result contains one row for each arrival, in the same order as stream.

Function

topKAfterEach(stream: int[], k: int) → int[][]

Examples

Example 1

stream = [1,2,1,3,2,1]k = 2return = [[1],[1,2],[1,2],[1,2],[1,2],[1,2]]

Value 1 becomes the unique leader after its second arrival. When values 1 and 2 both have frequency 2, the smaller value comes first.

Example 2

stream = [4,4,5,5,3]k = 1return = [[4],[4],[4],[4],[4]]

At the fourth arrival, values 4 and 5 are tied, so 4 remains the single returned value.

Constraints

1 <= stream.length <= 10^5.
1 <= k <= 10^5.
Every value in stream is a signed 32-bit integer.
Each row contains min(k, distinctPrefixValues) values.