Assuming each integer takes 4 bytes, for 4 billion numbers it turns out to
be 16 GB memory required. But we have only 1 GB memory.
1. So, break the 16GB file into 16 1GB files.
2. Then one by one take each file into memory and run quick sort algorithm
on it and put it back in the same file. After this step we will be having 16
1GB files which are all sorted.
3. Then open all the 16 files with 16 file pointers. Read 1 number from
each file and put it in an array in the memory.
4. Then run Min Heapify algorithm on it. Now we will have the smallest
number at index 0 of the array.
5. Remove that number from the array and read a new number into the array
from the file of which the previous element was deleted.Again run Min
Heapify algorithm on the array.
keep on doing this till we find the missing number. Because the number
deleted in one cycle should be 1 greater than the number deleted in the
previous cycle. If this condition is not satisfied, we can tell the missing
number.
The algorithm remains same if we have 10 MB memory, only change is that we
divide the initial file into small files each of size 10 MB.
Thanks and regards,
Ankit
On Wed, Mar 16, 2011 at 2:18 PM, bittu <shashank7andr...@gmail.com> wrote:
> Given an input file with four billion integers, provide an algorithm
> to generate an integer which is not contained in the file. Assume you
> have 1 GB of memory.
>
> 2nd Part
> What if you have only 10 MB of memory?
>
> Thank
> Shashank
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
