Find Median from Data Stream
Susquehanna International Group (SIG)● HardINTERNPHONE SCREENProblem statement
Numbers arrive one at a time, and at any point you may be asked for the median of all the numbers seen so far.
You are given operations, a list of rows to process in order. Each row has one of two forms:
["add", value]stores the integer written invalue.["median"]asks for the median of all values stored so far.
With an odd number of stored values, the median is the middle value after sorting. With an even number, it is the mean of the two middle values, which may end in .5. Repeated values all count.
Return a list with the answer to each ["median"] row, in the order those rows appear. An ["add", value] row adds nothing to the list.
Function
processMedianOperations(operations: String[][]) → double[]Examples
Example 1
operations = [["add","5"],["median"],["add","1"],["median"],["add","9"],["median"]]return = [5.0,3.0,5.0]The stored values at the three queries are [5], [1, 5], and [1, 5, 9]. Their medians are 5, 3, and 5.
Example 2
operations = [["add","-3"],["add","-2"],["median"],["median"]]return = [-2.5,-2.5]The two middle values are -3 and -2, and their mean is -2.5. A query stores nothing, so the second query gives the same answer.
Example 3
operations = [["add","4"],["add","4"],["add","10"],["add","1"],["median"]]return = [4.0]Repeated values are all kept. Sorted, the values are [1, 4, 4, 10], so the two middle values are 4 and 4, and their mean is 4.
Constraints
2 <= operations.length <= 1000- Each row is either
["add", value]or["median"]. - Each
valueis a base-10 integer from-1000000000through1000000000, written with no leading zeros or plus sign. - There is at least one
["median"]row, and each one comes after at least one["add", value]row.