Top K Largest Values from a Stream
The D.E. Shaw Group● MediumFULLTIMEONSITE INTERVIEWProblem statement
Numbers arrive one at a time from a stream. You are given a fixed integer k and a list operations that describes the stream in order. Process the rows from left to right. The stream starts empty, and each row has one of these forms:
[0, value]addsvalueto the stream.[1]asks for the topkvalues of the stream so far.
The top k values are the k largest values added so far, listed from largest to smallest. Repeated values count separately, so a value that was added twice can appear twice. If fewer than k values have been added, return all of them from largest to smallest. If no value has been added yet, return an empty list.
Return one list for every [1] row, in the order the rows appear. [0, value] rows produce no output.
Function
topKFromStream(k: int, operations: int[][]) → int[][]Examples
Example 1
k = 3operations = [[0,5],[0,1],[1],[0,9],[0,3],[1],[0,7],[1]]return = [[5,1],[9,5,3],[9,7,5]]At the first query only 5 and 1 have arrived, which is fewer than k = 3, so both are returned: [5,1]. After 9 and 3 arrive, the three largest of 5, 1, 9, 3 are [9,5,3]. After 7 arrives, the three largest of 5, 1, 9, 3, 7 are [9,7,5].
Example 2
k = 2operations = [[1],[0,4],[0,4],[1],[0,-2],[1]]return = [[],[4,4],[4,4]]The first query runs before any value arrives, so it returns an empty list. The two copies of 4 count separately, so the second query returns [4,4]. Adding -2 does not change the two largest values, so the last query also returns [4,4].
Example 3
k = 1operations = [[0,-3],[1],[0,-8],[1],[0,0],[1]]return = [[-3],[-3],[0]]With k = 1, each query returns only the largest value so far. -8 is smaller than -3, so the second answer stays [-3]. 0 is larger than -3, so the last answer is [0].
Constraints
1 <= k <= 1001 <= operations.length <= 10^4- Each row of
operationsis either[0, value]or[1]. - Every added
valuesatisfies-10^9 <= value <= 10^9. - There is at least one
[1]row and at most1000of them.