Questions

Design a class to calculate the median of a number stream. The class should have the following two methods:

    insertNum(int num): stores the number in the class
    findMedian(): returns the median of all numbers inserted in the class

If the count of numbers inserted in the class is even, the median will be the average of the middle two numbers.

Example 1:

1. insertNum(3)
2. insertNum(1)
3. findMedian() -> output: 2
4. insertNum(5)
5. findMedian() -> output: 3
6. insertNum(4)
7. findMedian() -> output: 3.5

Implementation: MedianOfNumberStream

-> Median for an odd number of elements is the middle element. For an even number of elements, its the average of the two middle elements.

Considering, we divide these set of elements into equal halves (n/2+1 for odd number of elements);

For even number of elements, we need to keep track of the max for all elements on the left half, and for odd number of elements, we need to keep track of the min of all elements on the right half.

        1   2   3

        left half = 1   2
        right half = 3

        In this case, median is the max of the left half

        1   2   3   4

        left half = 1   2
        right half = 3  4

        In this case, median is (2+3)/2 or max(left_half)+min(right_half)/2.

Thus, we will use a max-heap for the left half and a min-heap for the right half.

Time complexity

O(logn) for insert and heapify on every insert. O(1) for find.

Space complexity

O(1)

Return to Index