Yes, but is the same thing. You read the blocks to Ram and search for the number. If you find then you return False and stop the process. If you reach the end of file and didn't find the number, then you return True.
But if the file is sorted the complexity will be O(logn), because will can do binary search. On Thu, Jun 23, 2011 at 12:45 PM, atul purohit <gonewiththe...@gmail.com> wrote: > 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. > -- ------------------------------------------------------------------- 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.
