FastPrepRunning Medians

Running Medians

Microsoft logoMicrosoft● HardNEW GRADONSITE INTERVIEW
Learn

Problem statement

Given an integer array nums, process its values from left to right. After each insertion, return the median of all values seen so far.

For an even number of values, the median is the average of the two middle values. Return one median for every prefix of nums.

Function

runningMedians(nums: int[]) → double[]

Examples

Example 1

nums = [5,15,1,3]return = [5.0,10.0,5.0,4.0]

The sorted prefixes have medians 5, 10, 5, and 4.

Example 2

nums = [2,2,2]return = [2.0,2.0,2.0]

Every prefix consists only of the value 2.

Constraints

  • 1 <= nums.length <= 100000
  • -10^9 <= nums[i] <= 10^9
  • Results use absolute tolerance 1e-12

More Microsoft problems

See Microsoft hiring insights
public double[] runningMedians(int[] nums) {
  // Write your code here.
}
nums[5,15,1,3]
expected[5.0,10.0,5.0,4.0]
Checking account…