Median of a stream
Numbers arrive one at a time, and at any moment you may be asked for the median of all the numbers so far. The median is the middle number once the numbers are sorted. With an even count there are two middle numbers, and the median is their average: for 1, 3, 4, 8 it is (3 + 4) / 2 = 3.5.
Write a class MedianFinder:
MedianFinder()starts with no numbers.add_num(num)records one integernum.find_median()returns the median of every number recorded so far and removes nothing. It is only called after at least oneadd_num.
For an even count, return the average as Python's / gives it, a float such as 3.5 or 3.0. For an odd count, return the middle number; an int and a float with the same value both pass. Both methods are called many times, so both must stay fast.
MedianFinder(), then add_num(5), find_median(), add_num(1), find_median(), add_num(8), find_median(), add_num(2), find_median()Output5, 3.0, 5, 3.5The sorted numbers are [5], then [1, 5], then [1, 5, 8], then [1, 2, 5, 8]. The medians are 5, (1 + 5) / 2, 5, and (2 + 5) / 2.
MedianFinder(), then add_num(-3), add_num(4), find_median()Output0.5(-3 + 4) / 2 = 0.5. Negative numbers and medians that are not whole numbers are both fine.
-105 ≤ num ≤ 105
At most 5 × 104 calls in total.
find_medianis called only after at least oneadd_num.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.