If the file is sorted, use binary search. Divide the file in blocks of 2MB. Choose the blocks using binary search, an inside the block use binary search again to find the number.
If the file isn't sorted, sort the file with cosequential process, then use binary search. To learn cosequential process see the book File Structure from Folk. With cosequential process you can sort a terabyte file with only 100 bytes of Ram, for example. Or you can divide the file in blocks of 2MB or less and check all this blocks for the number. On Thu, Jun 23, 2011 at 9:59 AM, atul purohit <gonewiththe...@gmail.com> wrote: > > Hi, > Can someone explain me how to do this. > Given a file containing roughly 300 million 9-digit numbers. Find a 9-digit > number that isn't present in the file.You have unlimited drive space but > only 2MB of RAM available. > I suppose we have to use bit-vectors n all but still couldnt figure out a > proper way. A few steps or an algo will be great. > Cheers, > Atul > > -- > 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. > -- ------------------------------------------------------------------- Douglas Gameiro Diniz Engenheiro de Computação - 2003 - UNICAMP Mobile: (19) 92158777 Gtalk: dgdiniz Msn: thedougdi...@hotmail.com -- 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.
