Sunday, March 11, 2012

Adobe Question: Find median of infinite stream of numbers

Use one max heap and one min heap.

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.

if count of total numbers are even then the new number will be inserted into min heap else it will go to max heap. We also need to remember that numbers in max heap should be less than numbers in min heap.

Code ::

class Container
{
public:
void insert(int val);
float median();

private:
vector<int> minHeap;
vector<int> maxHeap;
};

void Container::insert(int val)
{
if((minHeap.size() + maxHeap.size()) % 2 == 0)
{
if(maxHeap.size() > 0 && val < maxHeap[0])
{
maxHeap.push_back(val);
push_heap(maxHeap.begin(), maxHeap.end());
val = maxHeap[0];
pop_heap(maxHeap.begin(), maxHeap.end());
maxHeap.pop_back();
}
minHeap.push_back(val);
push_heap(minHeap.begin(), minHeap.end(), greater<int>());
}
else
{
if(minHeap.size() > 0 && val > minHeap[0])
{
minHeap.push_back(val);
push_heap(minHeap.begin(), minHeap.end(), greater<int>());
val = minHeap[0];
pop_heap(minHeap.begin(), minHeap.end(), greater<int>());
minHeap.pop_back();
}
maxHeap.push_back(val);
push_heap(maxHeap.begin(), maxHeap.end());
}
}

float Container::median()
{
int count = minHeap.size() + maxHeap.size();
if(count == 0)
return -1; //error value
if(count%2 == 0)
return (float)(minHeap[0] + maxHeap[0]) / 2;
else
return minHeap[0];
}

No comments:

Post a Comment