554. Live Median

HardHeapDesignSortingData Stream3 hints
RPby Rohit Parihar

A sensor network streams in integer readings one by one, and a dashboard must be able to show the median of everything received so far at any moment. Implement a class LiveMedian with a constructor that takes no arguments and two methods.

addNum(num) stores one more reading and returns nothing. findMedian() returns the median of all stored readings as a floating-point number: the middle value when the count is odd, or the average of the two middle values when the count is even. Equal readings count separately. findMedian is only called after at least one reading has been stored.

Re-sorting on every query is too slow: addNum should take O(log n) time and findMedian O(1) time. Answers within 1e-6 of the true median are accepted.

Example 1

Input:
operations = ["LiveMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian"]arguments = [[],[5],[],[2],[],[9],[],[4],[]]
Output:
[null,null,5,null,3.5,null,5,null,4.5]
Explanation:

The medians are 5, then (2+5)/2 = 3.5, then 5, then (4+5)/2 = 4.5 as readings 5, 2, 9 and 4 arrive.

Example 2

Input:
operations = ["LiveMedian","addNum","addNum","findMedian","addNum","findMedian"]arguments = [[],[-1],[-1],[],[-1],[]]
Output:
[null,null,null,-1,null,-1]
Explanation:

All readings are equal, so the median is always -1.

Example 3

Input:
operations = ["LiveMedian","addNum","addNum","addNum","findMedian","addNum","addNum","findMedian"]arguments = [[],[10],[20],[30],[],[40],[50],[]]
Output:
[null,null,null,null,20,null,null,30]
Explanation:

After 10, 20, 30 the median is 20; after adding 40 and 50 the five readings have median 30.

Constraints

  • -109 ≤ num ≤ 109
  • At most 105 calls in total to addNum and findMedian
  • findMedian is called only when at least one reading has been added
  • The sum of two readings can exceed the 32-bit integer range; use a wider type for the average

How this problem is judged

Answers
Numbers are accepted within a tolerance of 1.0E-6: |answer - expected| <= 1.0E-6 x max(1, |expected|).
Tolerance
0.000001
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(log n) per addNum, O(1) per findMedian
Space
O(n)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.