FastPrepMedian of a Number Stream
Problems/Median of a Number Stream

Median of a Number Stream

Adobe logoAdobe● HardFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: Two separate Adobe interviews, described in three posts, ask for the running median of integers that keep arriving. One of them is a short entry that names the task and nothing else. In the other, a max-heap for the lower half and a min-heap for the upper half was the answer, and an outline in pseudocode was all the interviewer wanted. The same candidate later retold that interview and added two details: the interviewer probed why keeping the two heaps balanced gives a correct median, and the outline takes the mean of both heap tops when the count is even.

No report gives limits, examples or a judged input form. Our choices: the stream comes as one array, medians are requested at given checkpoints, there are at most 10^4 numbers from -10^5 to 10^5 and at most 500 checkpoints. The examples are our own. The editorial answers the balanced-heaps question.

The judged task matches the reports at about 85%.

Integers arrive one at a time, in the order given by nums. At certain moments you are asked for the median of all the numbers that have arrived so far: checkpoints[j] means "after the first checkpoints[j] numbers have arrived".

The median of m numbers is found by sorting them:

  • if m is odd, it is the middle number;
  • if m is even, it is the average of the two middle numbers, which can end in .5.

Return the median for each checkpoint, in order.

Function

mediansAt(nums: int[], checkpoints: int[]) → double[]

Examples

Example 1

nums = [5,15,1,3,8]checkpoints = [1,2,3,4,5]return = [5.0,10.0,5.0,4.0,5.0]

After each number: [5] has median 5. [5, 15] has two middle values, so the median is (5 + 15) / 2 = 10. Sorted, [1, 5, 15] has median 5, [1, 3, 5, 15] has median (3 + 5) / 2 = 4, and [1, 3, 5, 8, 15] has median 5.

Example 2

nums = [-2,-7,4,4]checkpoints = [2,4]return = [-4.5,1.0]

After 2 numbers, sorted [-7, -2]: the median is (-7 + -2) / 2 = -4.5. After 4 numbers, sorted [-7, -2, 4, 4]: the median is (-2 + 4) / 2 = 1.

Example 3

nums = [100000,-100000]checkpoints = [2]return = [0.0]

Only one checkpoint, after both numbers. The two middle values are the extremes, and their average is 0.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^5 <= nums[i] <= 10^5
  • 1 <= checkpoints.length <= 500
  • checkpoints is strictly increasing and every value is between 1 and nums.length.

More Adobe problems

  • Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
  • All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
  • Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
All Adobe interview questionsSee Adobe hiring insights
Saved
public double[] mediansAt(int[] nums, int[] checkpoints) {
    // Write your code here.
}
Checking account…