A9 Interview Question
Software Engineer / DevelopersCountry: 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.