There is a big file containing 10^8 integers, one per line. Devise an algorithm to find the largest 100 integers among them. Remember you cannot read all of them into memory at once.
courtesy: Vibhaj
Click here to see the solution.
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.
Hints: Value stored in any element of the Array reaches a maxima at certain index. |
|
Solution:
We simply use Min-Heap data structure to keep list of top 100 numbers replacing next with lowest if greater.
Complexity:
1. Time: O(N*logN)
2. Space: O(1)
/**
* Assume standard heap ADT operations : heap_min(), heap_remove() and heap_insert()
**/
void top_100(FILE *fp, int output[]){
int num, count=0;
while(fscanf(fp, "%d\n", &num)){
if(++count > 100 && num > heap_min(output)){
heap_remove(output);
}
heap_insert(output, num);
}
}
|
|
|
Posts
