Hi, While external sorting is a probable way to sort it. Still it changes the content and time complexity will be > O(n). It is a trivial job to copy the entire file and do the sorting and find a number which is not present in file but I am looking for a solution which essentially does the job in O(n).
Thanks. Atul On Thu, Jun 23, 2011 at 6:59 PM, Douglas Diniz <[email protected]> wrote: > 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 <[email protected]> > 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 [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. > > > > > > -- > ------------------------------------------------------------------- > Douglas Gameiro Diniz > Engenheiro de Computação - 2003 - UNICAMP > > Mobile: (19) 92158777 > Gtalk: dgdiniz > Msn: [email protected] > > -- > 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. > > -- Atul Purohit -- 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.
