FastPrepFind Median from Data Stream
Problem · Design

Find Median from Data Stream

Learn this problem
● HardIntuit logoIntuitINTERNOA

Problem statement

Process a finite sequence of operations on a stream of integers.

  • ["add", value] inserts value into the stream.
  • ["median"] asks for the median of all values inserted so far.

Return the answers to the median operations in their original order. For an odd number of values, the median is the middle value after sorting. For an even number of values, it is the arithmetic mean of the two middle values.

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 sorted stream is [5], then [1,5], then [1,5,9]. Their medians are 5, (1 + 5) / 2 = 3, and 5.

Example 2

operations = [["add","-4"],["add","8"],["median"],["add","8"],["median"],["add","20"],["median"]]return = [2.0,8.0,8.0]

The three queried stream states have medians 2, 8, and 8. The duplicate value participates independently.

Example 3

operations = [["add","1000000000"],["add","999999999"],["median"]]return = [999999999.5]

The mean of the two middle values is 999999999.5. Compute the sum without overflowing a 32-bit integer.

Constraints

  • 1 <= operations.length <= 100000.
  • Each operation is exactly ["add", value] or ["median"].
  • -10^9 <= value <= 10^9.
  • Every median operation occurs after at least one add operation.

More Intuit problems

drafts saved locally
public double[] processMedianOperations(String[][] operations) {
    // Write your code here
}
operations[["add","5"],["median"],["add","1"],["median"],["add","9"],["median"]]
expected[5.0,3.0,5.0]
checking account