CareerCup

I guess we can use a min heap of size 100 and get an O(n) algo.

The algo can be as follows.

Let the array be stored in A[1..n]

1) Take the first 100 elements from the given array and build a heap. --> O(100)
Note : The heap can be created inplace i.e. on elements A[1] to A[100]
2) for(i = 101 to n) do
curr = A[i];
2.1) compare the curr element with the minimun element of the heap.
2.1.1) if (curr > minHeap) //Note : minHeap = A[1].
then
exchange the curr element with minHeap. --> O(1)
reheapify the resultant heap (of size 100). --> (O(ln(100)))
2.2) i = i + 1;
done
So overall complexity of this algo is

n*O(ln(100)){reheapify} + O(100){build heap} + O(n) {exchange minHeap with curr}
= O(n).

How about using a BitSet of billion elements and iterate through all the nos. in the array and set the particular bit in the BitSet. Now start from the end and print the 100 nos. where BitSet return true.

Thanks,

You are allowed to modify the array.I have given a solution of O(NlogN).But the interviewer wanted a solution of O(N).

I have sorted the Array by quickSort and printed the last 100 elements.It was O(NlogN).
The interviewer wanted just O(N).

@Lost:
That's not gonna do it, 'coz quickSort is an in-memory sort, and yet there're *billions* of ints.

We need some sort of stream algorithm.

What about processing sequentially, while bookkeeping the 100 max elements up until so far?

How about bubble sort looping only for 100 times...

essentially becomes = 100XO(N) =~ O(N).

Can i assume the above statement ?
100 << billions of numbers...(N)

Just an attempt.. suggestions are appreciated...

1) Have an array in sorted order of 100 elements.. Use insertion sort preferably..

2) Choose an element from billion elements and put it in a right position in 100 elements.. Discard the lowest value..

3) Continue for all billion elements..


Time Complexity - Insertion sort = (n log n) = 100 log 100 = 200

So, for billion iterations it becomes = O(200 *billion(n))
= O(200 *n) = O(n)

Now, my question is can we ignore 200 in front of billion numbers??? I doubt though... :-D.. Please let me know this.. Thanks.

The solution lies in finding the nth element largest element from a sequence of number. This can be done using the famous SELECT algorithm which lets us find the nth largest element from a series of number. This work in O(n)(http://en.wikipedia.org/wiki/Selection_algorithm).

Try to find (N-100) element. The end result will give us 2 sets. Chose the one where all the elements are greater than the (N-100)th element.

I will not specify the complete working here. You may want to read here

http://en.wikipedia.org/wiki/Selection_algorithm

ProblemDissolver's solution is a general solution,using SELECT,
In this case, coder's solution cost less time (in the same magnitude)

Would it help if we sorted the array using Radix sort (sorts in O(n))? Space complexity would take a beating though.

Set up a circular buffer of 100 elements, initialize to 0. Set a buffer pointer to the first element. Read the billions of numbers sequentially. If the number read is larger than the largest element in the 100 element array (current buffer pointer), replace the smallest element with the element just read. Make the buffer pointer point to the largest element. Repeat.

You read through the entire 1 billion once. You do constant work per element read (one comparison, possibly one replacement and one pointer move).

O(n).

Multiple ways:

1) Create a heap of the array. Worst case time for this would be O(n). Find the first 100 numbers out of 7 levels.

2) Use SELECT algo to find the kth largest element (k=100). Loop again thru the array to find all the numbers greater than the given number.

divide billion numbers in chunks such that number can be stored in memory and sort(max to min) them and restore that part of chunk in secondary memory. Do same for all chunks . Now you have sorted chunks of memory. Now add all chunks initial address to game tree leaves. And pop up 100 maximum by using game tree. Order : if there are r chunks then it would be (n/r)(log(n/r))+100*log(r). which is <=O(n) for larger r value. If you want to know about game tree then just google it or find it some standard algorithm books(like - Cormen or K.Nuths)

divide billion numbers in chunks such that number can be stored in memory and sort(max to min) them and restore that part of chunk in secondary memory. Do same for all chunks . Now you have sorted chunks of memory. Now add all chunks initial address to game tree leaves. And pop up 100 maximum by using game tree. Order : if there are r chunks then it would be (n/r)(log(n/r))+100*log(r). which is <=O(n) for larger r value. If you want to know about game tree then just google it or find it some standard algorithm books(like - Cormen or K.Nuths)

Store the first 100 elements in a min-heap, then go through the 1 billion-100 elements, if one element is greater than the head root one, remove the root element and insert the new one. It would spend nlog100 =7n time in the worst case.

algorithm
1. Run a loop up to size-no of elements to be found (OR) run a loop upto sizeOfArray
for(i=0;i<size-NoOfElementsToBeFound;i++)
2. Base condition :check for each index if (index==arr[index])then continue; else go to step 3
3. swap(arr[index], arr[arr[index]]) repeat upto index!=arr[index];
4. once that upper loop terminates
5.print it from backwards(for(i=size-1;i>=size-NoOfElementsToBeFound))
or
forward for the max 100 elements.

Note- in case of repeatative elements it will work.

while checking if you find element already present at its original position so just make it negative and skip next to it
rest process it same
Correct me if i am wrong.