I've been working on similar things lately. 1st, if the file is unsorted, you'll have to just go through it, it'll be O(n) worst case, which is preferred rather than sorting it.
2nd if it is sorted, read and store the maximum chunk of the file that you can, a program is allotted 4 GB of address space, out of which in reality may be 3 GB is useable. So an array worth 3 GB, which is roughly ( ( 3 * 1024 * 1024 * 1024 ) / 4 ) 805306368 integer elements ( assuming each number fits in 4 bytes ), do a binary search. If not found, go to the next chunk.. etc On Thu, Oct 27, 2011 at 10:17 PM, Prem Krishna Chettri <[email protected]>wrote: > Clearly this is an external sorting question.. > Merge sort Can Be Used.. > > On 10/27/11, shiva@Algo <[email protected]> wrote: > > Given a file containing roughly 300 million social security > > numbers(9-digit numbers), find a 9-digit number that is not in the file. > > You have unlimited drive space but only 2megabytes of RAM at your > > disposal. > > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]. > > 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Anup Ghatage -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
