Interview follow-ups
Using 2 HeapsCodeFollow-Up Questions :
If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

If 99% of all in
# Using 2 Heaps


# Code
```java []
class MedianFinder {
    PriorityQueue<Integer> max;
    PriorityQueue<Integer> min;

    public MedianFinder() {
        max = new PriorityQueue<>(Collections.reverseOrder());
        min = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        max.add(num);
        min.add(max.poll());
        if (min.size() > max.size()) {
            max.add(min.poll());
        }
    }
    
    public double findMedian() {
        if (max.size() > min.size()) {
            return max.peek();
        }
        return (max.peek() + min.peek())/2.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
```
# Follow-Up Questions : 
- If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
 
```java []
class MedianFinder {
    private int[] count;
    private int total;

    public MedianFinder() {
        count = new int[101]; // Range is [0, 100]
        total = 0;
    }

    public void addNum(int num) {
        count[num]++;
        total++;
    }

    public double findMedian() {
        int cumulativeCount = 0;
        int left = -1, right = -1;

        // Traverse the count array to find the median(s)
        for (int i = 0; i < 101; i++) {
            cumulativeCount += count[i];

            // Find the left median (total/2 for even, or total/2+1 for odd)
            if (left == -1 && cumulativeCount >= (total + 1) / 2) {
                left = i;
            }

            // Find the right median (total/2+1 for even)
            if (cumulativeCount >= total / 2 + 1) {
                right = i;
                break;
            }
        }

        // If total is odd, both left and right point to the same value
        return total % 2 == 0 ? (left + right) / 2.0 : left;
    }
}
```
- If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

```java []
class MedianFinder {
    private int[] buckets; // Buckets for numbers in the range [0, 100]
    private int smallerCount; // Count of numbers smaller than 0
    private int largerCount; // Count of numbers larger than 100
    private int totalCount; // Total count of numbers

    public MedianFinder() {
        buckets = new int[101]; 
        smallerCount = 0;
        largerCount = 0;
        totalCount = 0;
    }

    public void addNum(int num) {
        if (num < 0) {
            smallerCount++;
        } else if (num > 100) {
            largerCount++;
        } else {
            buckets[num]++;
        }
        totalCount++;
    }

    public double findMedian() {
        
        int medianIndex1 = (totalCount - 1) / 2 + 1; 
        if (totalCount % 2 == 0) {
            // Even case: median is the average of two middle elements
            int medianIndex2 = medianIndex1 + 1;
            int median1 = findKthElement(medianIndex1);
            int median2 = findKthElement(medianIndex2);
            return (median1 + median2) / 2.0;
        } else {
            // Odd case: median is the middle element
            return findKthElement(medianIndex1);
        }
    }

    private int findKthElement(int k) {
        
        k -= smallerCount;
        for (int i = 0; i < buckets.length; i++) {
            if (k <= buckets[i]) {
                return i; 
            }
            k -= buckets[i];
        }
        return 101; 
    }
}
```
- Thread-safe Method

```java []
class MedianFinder {
    private PriorityQueue<Integer> max; 
    private PriorityQueue<Integer> min; 
    private final Object lock = new Object(); 

    public MedianFinder() {
        max = new PriorityQueue<>(Collections.reverseOrder());
        min = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        synchronized (lock) {
            max.add(num);
            min.add(max.poll());
            if (min.size() > max.size()) {
                max.add(min.poll());
            }
        }
    }
    
    public double findMedian() {
        synchronized (lock) {
            if (max.size() > min.size()) {
                return max.peek();
            }
            return (max.peek() + min.peek()) / 2.0;
        }
    }
}
```
- How to handle when the data is very large?
1. Use 2 lists : unsorted and sorted
2. Now add the new elements into the unsorted list.
3. Whenever the findMedian function is called, only then sort the unsortedList and assign it to the sortedList.

Though the time complexity would be O(nlogn) in worst case but the number of calls for findMedian might be lesser.

['Java']