CareerCup

Hello.. i am not clear with ur idea.. can u explain it more. Min heap will be applied to the whole integers and how to find the first 100 integers..
Thanks in advance

As it seems to me, question itself is ambiguous. What is meant by first 100 large numbers. As per my understanding, it should be find 100 large numbers.

So we can create min heap of 100 elements size. As soon you receive number from the stream, put it in heap and heapify.

I understand the question in a different way. There are stream of n integers and u r asked to print first 100 large numbers.

Use quick sort to get the 100 the number say x from the array O(n) and display the numbers which are <=x.O(n)

max = ans(a[],lower,upper,n) O(n)
print(all nos <= max in array) O(n)


ans(a[],lower,upper,n)
{
while(upper>= lower)
{
int i= spilt(a[],lower,upper,n); split function is Quick sort operation
if(i==n)
return a[i];
if(i<n)
{
upper=i+1;
n=n-i;
}
if(i>n)
{
lower=i+1;
n=n-i;
}
}
}

lol

eg: 1, 12, 13, 23,11,20,45,67,23.........
eg: we need first 4 largest
result : 1,12,13,2...when we read 23 then it has to delete the least one in the result and to accommodate the latest one
result after removing one : 12,13.2,23...so on

We can create a min heap of size 100 .pick the element from stream and put in Min heap when the 101 th element pick from stream find the minimum element of min heap ,if it is large ,then remove that min value and again arrange the heap.

Quick selection to pick 100th max number, e.g. A , then iterate array and take all number > A, and count them, if less than 100, say n, then repeat 100-n for A, should be O(n).