InternDoor

The middle of a stream of numbers

Harddesign · heapDesign a class

Reported in interviews at (where)

Build RunningMedian, which takes whole numbers one at a time and can say at any moment what the median of all of them is.

The median is the middle number once the numbers are sorted. When there are an even number of them, it is the average of the two middle numbers.

RunningMedian() starts with no numbers.

add(num) takes in num.

median() returns the median of every number taken in so far. It is only called after at least one add.

Sorting everything on every call is too slow for the largest tests: aim for O(log n) per add and O(1) per median.

Example 1
Input
["RunningMedian","add","median","add","median","add","median","add","median"]
[[],[6],[],[14],[],[2],[],[3],[]]
Output
[null,null,6.0,null,10.0,null,6.0,null,4.5]

Sorted, the numbers are 6, then 6 14, then 2 6 14, then 2 3 6 14: the median is 6, (6 + 14) / 2 = 10, 6, then (3 + 6) / 2 = 4.5.

Example 2
Input
["RunningMedian","add","add","median","add","median"]
[[],[-2],[-3],[],[-2],[]]
Output
[null,null,null,-2.5,null,-2.0]

The same number can come more than once: -3 -2 -2 has -2 in the middle.

Limits

  • -1000000 <= num <= 1000000
  • median is only called after at least one add
  • at most 20000 calls after the constructor
  • answers within 0.000001 of the median count as right

Hints

Hint 1

Split the numbers into a lower half and an upper half. The median only needs the largest of the lower half and the smallest of the upper half.

Hint 2

Keep the lower half in a max-heap and the upper half in a min-heap, with the lower one holding the same number or one more. After each add, move one top across if the sizes or the order are off.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.