Track the median of a number stream after each insert
A monitoring dashboard receives response times one at a time and must show the median latency after every new sample. Sorting the whole history on every update is too slow once there are tens of thousands of samples.
Implement a MedianTracker class:
const tracker = new MedianTracker();
tracker.add(num); // records a number, returns nothing
tracker.getMedian(); // => the median so far, or null when empty
tracker.size(); // => how many numbers were added
[1, 2, 3, 4] is 2.5.getMedian() returns null before any number is added.add(num) accepts any finite number: negatives, decimals, and duplicates are all allowed.num is not a finite number (NaN, Infinity, a numeric string, null, and so on), add throws a TypeError and the tracker is left unchanged.The tests add tens of thousands of numbers and call getMedian() after every single add. Sorting on each call is too slow. Aim for O(log n) per add and O(1) per getMedian().
const latency = new MedianTracker();
latency.getMedian(); // => null
latency.add(120);
latency.getMedian(); // => 120
latency.add(80);
latency.getMedian(); // => 100 (average of 80 and 120)
latency.add(300);
latency.getMedian(); // => 120 (80, 120, 300)
latency.add(95);
latency.getMedian(); // => 107.5 (80, 95, 120, 300)
latency.size(); // => 4
latency.add(NaN); // throws TypeError
latency.size(); // => 4