[Adobe] Find median of infinite stream of numbers

Problem: The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

• For example, for arr = [1, 2, 3], the median is 1.
• For example, for arr = [1, 2], the median is (1 + 2) / 2 = 1.5.

Implement the MedianFinder class:

• MedianFinder() initializes the MedianFinder object.
• void AddNum(int num) adds the integer num from the data stream to the data structure.
• double FindMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

Example:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

Approach: Use one max heap and one min heap in following way:

• Max heap will be containing the numbers which are less than median.
• Min heap will be containing the numbers which are greater than or equals to median.
• Difference between the size of two heaps will never be greater than 1.

The numbers in max heap should be less than numbers in min heap so if the current number is less than or equal to the top of max heap then it will go to max heap otherwise it will go to min heap. 

We just need to take care of the violation of third condition after insertion.

When we try to find the median, we can just see if max heap has more elements than min heap (case of number of elements are odd) then we can return it's top otherwise its the case of even number so we can safely return (top of max heap + top of min heap) / 2.


Implementation in C#:

public class IntMaxCompare : IComparer<int>

{

    public int Compare(int x, int y) => y.CompareTo(x);

}

public class MedianFinder

{

    public MedianFinder()

    {

        this.maxHeap = new PriorityQueue<int, int>(new IntMaxCompare());

        this.minHeap = new PriorityQueue<int, int>();

    }

   

    public void AddNum(int num)

    {

        if (this.maxHeap.Count == 0 || this.maxHeap.Peek() >= num)

        {

            this.maxHeap.Enqueue(num, num);

        }

        else

        {

            this.minHeap.Enqueue(num, num);

        }

        if (this.maxHeap.Count > this.minHeap.Count + 1)

        {

            int elem = this.maxHeap.Dequeue();

            this.minHeap.Enqueue(elem, elem);

        }

        else if (this.maxHeap.Count < this.minHeap.Count)

        {

            int elem = this.minHeap.Dequeue();

            this.maxHeap.Enqueue(elem, elem);

        }

    }

   

    public double FindMedian()

    {

        if (this.maxHeap.Count > this.minHeap.Count)

        {

            return (double) this.maxHeap.Peek();

        }

        return (this.maxHeap.Peek() + this.minHeap.Peek()) / 2.0;

    }

    PriorityQueue<int, int> maxHeap;

    PriorityQueue<int, int> minHeap;

}

Complexity: AddNum - O(logn), FindMedian - O(1)