Find Median from Data Stream

Hard

heapdesignstream

Design a structure that ingests integers and can return the median of everything seen so far at any time.

Input: one operation per line —

addNum x — add integer x
findMedian — print the median formatted with one decimal place (e.g. 2.0, 1.5)

Output: addNum prints null; findMedian prints the median.

Example 1

Input:

addNum 1
addNum 2
findMedian
addNum 3
findMedian

Output:

null
null
1.5
null
2.0

Run your code against the sample tests, or Submit to run the full suite.