FastPrep
Problem · Segment Tree

Streaming Median and Kth Smallest

Learn this problem
● HardGoogle logoGoogleFULLTIMEONSITE INTERVIEW
See Google hiring insights

Problem statement

Process an ordered stream of integer updates and order-statistic queries. The value range is deliberately small, so every inserted value is between -1000 and 1000.

Each row in operations is one of:

  • ["add", value]: insert one occurrence of value.
  • ["median"]: return the current median. For an even number of values, use the average of the two middle values.
  • ["kth", k]: return the current one-indexed kth-smallest value.

Return one string for each query, in query order. Write integer results without a decimal point and half-integer medians with exactly one decimal digit, such as "2.5" or "-0.5". Add operations do not produce output.

Function

processOrderStatistics(operations: String[][]) → String[]

Examples

Example 1

operations = [["add","1"],["add","5"],["median"],["add","2"],["median"],["kth","2"]]return = ["3","2","2"]

The first median averages 1 and 5. After adding 2, both the median and the second-smallest value are 2.

Example 2

operations = [["add","-2"],["add","1"],["median"],["add","1"],["kth","3"],["median"]]return = ["-0.5","1","1"]

The even median is (-2 + 1) / 2 = -0.5. Duplicate values count as separate stream elements.

Example 3

operations = [["add","1000"],["median"],["add","-1000"],["kth","1"],["kth","2"],["median"]]return = ["1000","-1000","1000","0"]

The range endpoints are retained exactly, and their even median is 0.

Constraints

  • 1 <= operations.length <= 100000
  • Every value is an integer in [-1000, 1000].
  • At least one value has been added before every query.
  • For each kth query, 1 <= k <= current stream size.

More Google problems

drafts saved locally
public String[] processOrderStatistics(String[][] operations) {
    // Write your code here.
}
operations[["add","1"],["add","5"],["median"],["add","2"],["median"],["kth","2"]]
expected["3", "2", "2"]
checking account