Numbers are randomly generated and stored into an expanding array. How would you keep track of the median? - Interview Question

 Click Me
Concept: We will be using two heaps - a min-heap and a max-heap to keep track of the median on every step. We will store the first half of the numbers in the max-heap and the second half of the numbers will be stored in the min-heap. If we get the same size of both heaps and we calculate the mean of the roots of min-heap and max-heap. If we get the different sizes of both heaps, the heap with the larger size will contain the median at its root.
All this time, we have to make sure that we keep a balance among the sizes of both heaps in such a way that either both of them are equal in size or differ in size only by 1. This will ensure our median candidates always be at the root of both heaps.

Note: To simulate the random generation and storage into an expanding array, I am passing a random number in insert() function after some sleep time. This way we can get a feeling that we are getting a stream of numbers continuously. Also, we calculate the median on every insert()

Time Complexity - O(log n)
Space Complexity - O(n)

Code: [Do not run this code in Online IDE as it may not work in online IDE due to Thread.sleep()]

import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
// the min-heap and the max-heap
PriorityQueue<Integer> minHeap;
PriorityQueue<Integer> maxHeap;
        // constructor
Main(){
this.minHeap = new PriorityQueue<Integer>(); // store right half of stream of numbers

                // By default PriorityQueue in Java implements min-heap.
                // So, to implement max-heap, we need to write our own comparator by overriding the compare method
this.maxHeap = new PriorityQueue<Integer>( new Comparator<Integer>() {
@Override
    public int compare(Integer a, Integer b) {
        return b - a; 
    }
});  // store left half of stream of numbers
}
        //method to insert a random number x into stream of numbers
public void insert(Integer x) throws InterruptedException {
                // This is used just to simulate the continious flow of numbers and median calculation at every step. 
Thread.sleep(3000);

System.out.println("Inserting " + x +" ...");

                // If both the heaps is empty - Inserting into minHeap
if(this.minHeap.isEmpty() && this.maxHeap.isEmpty()) {
this.minHeap.offer(x);
}
                // If minHeap is not empty and maxHeap is empty - Inserting into maxHeap if x is less than the root of minHeap, else inserting into minHeap
else if(!this.minHeap.isEmpty() && this.maxHeap.isEmpty()) {
if(x>minHeap.peek()) {
int extractMin = this.minHeap.poll();
this.maxHeap.offer(extractMin);
this.minHeap.offer(x);
}
else {
this.maxHeap.offer(x);
}
}
                // If minHeap and maxHeap both are non-empty - If x is greater than max-heap root value then it means 'x' will come in later half, so put it in minHeap. Otherwise put 'x' in maxHeap
else {
if(x>=this.maxHeap.peek()) {
this.minHeap.offer(x);
}
else {
this.maxHeap.offer(x);
}
}
                
                // Now we have to rebalance both the heaps so that their size are either equal of differ only by 1
rebalance();
System.out.println("Max-Heap: " + this.maxHeap);
            System.out.println("Min-Heap:" + this.minHeap);
                
                // calling method to calculate median after every insertion
            calculateMedian();
            System.out.println();
}
        // Method to rebalance both the heaps so that their size are either equal of differ only by 1
private void rebalance() {
                // if total number of elements are even in total,we can make their size equal
if((this.minHeap.size() + this.maxHeap.size()) % 2 == 0) {
if(this.maxHeap.size()>this.minHeap.size()) {
while(this.maxHeap.size()!=this.minHeap.size()) {
this.minHeap.offer(this.maxHeap.poll());
}
}
else if(this.maxHeap.size()<this.minHeap.size()) {
while(this.minHeap.size() != this.maxHeap.size()) {
this.maxHeap.offer(this.minHeap.poll());
}
}
}
}

        // Method to calculate the median at every insert
private void calculateMedian() {
if(this.minHeap.size()==this.maxHeap.size()) {
System.out.println("Median: " + (this.maxHeap.peek() + this.minHeap.peek())/2.0);
}
else if(this.maxHeap.size()>this.minHeap.size()) {
System.out.println("Median: " + this.maxHeap.peek());
}
else System.out.println("Median: " + this.minHeap.peek());
}
    public static void main(String[] args) throws Exception {
   
    Main m = new Main();
    m.insert(10);
    m.insert(3);
    m.insert(5);

    m.insert(2);
    m.insert(1);
    m.insert(2);
    m.insert(3);
   
    m.insert(5);m.insert(15);m.insert(1);m.insert(3);
   
    m.insert(2);m.insert(8);m.insert(7);m.insert(9);
   
    m.insert(10);m.insert(6);m.insert(11);m.insert(4);
        
    }
}


Output:

Inserting 10 ...
Max-Heap: []
Min-Heap:[10]
Median: 10

Inserting 3 ...
Max-Heap: [3]
Min-Heap:[10]
Median: 6.5

Inserting 5 ...
Max-Heap: [3]
Min-Heap:[5, 10]
Median: 5

Inserting 2 ...
Max-Heap: [3, 2]
Min-Heap:[5, 10]
Median: 4.0

Inserting 1 ...
Max-Heap: [3, 2, 1]
Min-Heap:[5, 10]
Median: 3

Inserting 2 ...
Max-Heap: [2, 2, 1]
Min-Heap:[3, 10, 5]
Median: 2.5

Inserting 3 ...
Max-Heap: [2, 2, 1]
Min-Heap:[3, 3, 5, 10]
Median: 3

Inserting 5 ...
Max-Heap: [3, 2, 1, 2]
Min-Heap:[3, 5, 5, 10]
Median: 3.0

Inserting 15 ...
Max-Heap: [3, 2, 1, 2]
Min-Heap:[3, 5, 5, 10, 15]
Median: 3

Inserting 1 ...
Max-Heap: [3, 2, 1, 2, 1]
Min-Heap:[3, 5, 5, 10, 15]
Median: 3.0

Inserting 3 ...
Max-Heap: [3, 2, 1, 2, 1]
Min-Heap:[3, 5, 3, 10, 15, 5]
Median: 3

Inserting 2 ...
Max-Heap: [3, 2, 2, 2, 1, 1]
Min-Heap:[3, 5, 3, 10, 15, 5]
Median: 3.0

Inserting 8 ...
Max-Heap: [3, 2, 2, 2, 1, 1]
Min-Heap:[3, 5, 3, 10, 15, 5, 8]
Median: 3

Inserting 7 ...
Max-Heap: [3, 2, 3, 2, 1, 1, 2]
Min-Heap:[3, 5, 5, 7, 15, 10, 8]
Median: 3.0

Inserting 9 ...
Max-Heap: [3, 2, 3, 2, 1, 1, 2]
Min-Heap:[3, 5, 5, 7, 15, 10, 8, 9]
Median: 3

Inserting 10 ...
Max-Heap: [3, 3, 3, 2, 1, 1, 2, 2]
Min-Heap:[5, 7, 5, 9, 15, 10, 8, 10]
Median: 4.0

Inserting 6 ...
Max-Heap: [3, 3, 3, 2, 1, 1, 2, 2]
Min-Heap:[5, 6, 5, 7, 15, 10, 8, 10, 9]
Median: 5

Inserting 11 ...
Max-Heap: [5, 3, 3, 3, 1, 1, 2, 2, 2]
Min-Heap:[5, 6, 8, 7, 11, 10, 15, 10, 9]
Median: 5.0

Inserting 4 ...
Max-Heap: [5, 4, 3, 3, 3, 1, 2, 2, 2, 1]
Min-Heap:[5, 6, 8, 7, 11, 10, 15, 10, 9]
Median: 5

Comments

Post a Comment

Popular posts from this blog

Binary Heap - Introduction

Image
#Image Credit - GeeksForGeeks Types of heap: Min Heap - every node is less than or equal to  its children(s) Max Heap - every node is more than or equal to its children(s) Operations on any heap : create insert extract/delete - we can extract/delete only the top node in any heap traverse delete entire heap get size of heap peek top of heap We should prefer implementing binary heap using arrays and not linked list, as during bottom to top heapify, in reaching the bottom rightmost node we take only 0(1) time in case of array but we take 0(n) time in case of linked list because first, we need to level order traverse the binary heap tree to get bottom-most rightmost element.  Heaps are used to efficiently implement:  Prim's Algorithm Heapsort Priority queue
Read more

Divide and Conquer - Introduction

Image
What is Divide and Conquer? Divide and Conquer is an algorithm paradigm in which we break down a given problem into smaller sub-problems of similar type until the sub-problems are small enough to be solved directly. The solution to these sub-problems are then combined to give a solution to the original problem.  Study the diagram below, it will then make more sense about what we do in Divide and Conquer : Where to Apply Divide and Conquer? The Divide and Conquer can be applied to all those problems that show Optimal Substructure property.  So, What is this Optimal Substructure property now? If we can break down a problem into similar sub-problems and the solution of these sub-problems can be used to create the solution of the whole problem, then that problem is said to have the Optimal Substructure property. For eg. : Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2),    In this example, we can see that if we want to find the Fibonacci number at the nth place, we can break this problem in
Read more

Bubble Sort

Time complexity - O(n^2)  || Space Complexity - O(1) Bubble sort is an inplace sorting algorithm, that means we do not any extra space while bubble sorting public class Main {     public static void main(String[] args) throws Exception {         int[] arr={1,4,4,5,6,2,3,90,120,43,0};                  System.out.println("UnSorted Array :");         for(int i=0;i<arr.length;i++){             System.out.print(arr[i]+" ");         }         System.out.println();         // bubble sort         for(int i=0;i<arr.length-1;i++){ // iterates through first to last cell             for(int j=0;j<arr.length-1-i;j++){ // inner loop controls swapping and extent to which swapping is to be performed in array                 if(arr[j]>arr[j+1]){                     int temp = arr[j];                     arr[j]=arr[j+1];                     arr[j+1]=temp;                 }             }             // after each iteration we ge
Read more