FastPrep
Problem · Hash Table

Top K Frequent Elements After Each Stream Update

Learn this problem
● HardSalesforce logoSalesforceNEW GRADONSITE INTERVIEW
See Salesforce hiring insights

Problem statement

A conceptually unbounded integer stream is represented by the finite prefix stream. After each arriving value, return the current top k distinct values.

Order each snapshot by decreasing frequency. When frequencies tie, the numerically smaller value comes first. Before k distinct values have appeared, return all distinct values in that order.

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]]

The result is observed after every arrival; counts determine rank before the numeric tie rule.

Example 2

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

When 3 and 5 tie, 3 is ranked first.

Constraints

  • 1 <= stream.length <= 10000
  • 1 <= k <= min(100, stream.length)
  • -1000000000 <= stream[i] <= 1000000000
  • The total number of returned integers is at most 1000000.

More Salesforce problems

drafts saved locally
public int[][] topKAfterEach(int[] stream, int k) {
    // Write your code here
}
stream[1,2,1,3,2,1]
k2
expected[[1],[1,2],[1,2],[1,2],[1,2],[1,2]]
checking account