i wud do that if i was searching for a number in the file. I am doing the search for a number NOT present in the file.
On Thu, Jun 23, 2011 at 9:09 PM, Douglas Diniz <dgdi...@gmail.com> wrote: > Well, reading the file in blocks of 2MB or less, putting this blocks > in Ram one by one and check for the number untill you reach the end of > file is O(n). > > On Thu, Jun 23, 2011 at 12:17 PM, atul purohit <gonewiththe...@gmail.com> > wrote: > > 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 <dgdi...@gmail.com> > 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 <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. > >> > > > > > > > > -- > > > > 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 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. > > -- 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 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.
