## A9 Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**Phone Interview

it can be done in linear time O(n), say you are allowed 512 mb storage, and only 32 bit integers. 2^32 bits = 512 mb ram. that is 1 bit per number. One iteration to store all numbers in the bitmap array and second iteration on the bitmap array to find the first k bits that are 1.

That's assuming integer means 32 bits. You'd want to check with your interviewer what is meant by "integer"

maintain a min/max heap of k elements in RAM and fetch blocks of integers at a time and update the heap using the fetched block of integers.

- raja roy January 20, 2012Do this unless you are done with all the integers stored on disk.

At the end you will get the top K elements as in the heap.