Re: [algogeeks] Re: A Billion Number Question
I think I find the max and then print max + 1 is not a correct strategy because overflow can occur or find the min and print min-1 underflow can occur. If you use a bitset, you can store all the values that appear in 10Mb. I believe that these integers are in the file are integers that are represented in 32bit. Am i correct? Wladimir Araujo Tavares *Federal University of Ceará * On Thu, Mar 17, 2011 at 2:53 PM, Don wrote: > This only works if the file is sorted. If the file starts out with > values 5,7,6,... and never contains another 7, the result will be 7, > which is in the file. > > On Mar 17, 12:19 pm, "arpit.gupta" wrote: > > read the first no. . > > now ans= first no +1; > > if now ans is encountered while reading the next nos. add 1 to ans. > > i.e. ans++; > > > > On Mar 17, 2:18 am, bittu wrote: > > > > > Given an input file with four billion integers, provide an algorithm > > > to generate an integer which is not contained in the file. Assume you > > > have 1 GB of memory. > > > > > 2nd Part > > > What if you have only 10 MB of memory? > > > > > Thank > > > Shashank > > > > > > -- > 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. > > -- 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.
[algogeeks] Re: A Billion Number Question
Assuming the data is 32-bit unsigned integers: Treat your memory (either amount) as an array A[] of M integers. E.g., with 10 MB of memory, M = 2,500,000. Initialize the array to zero. Read through the file. For each integer x, increment A[x mod M]. There will be at least one bin whose count is no more than 4,000,000,000 / M = 1,600. Call it bin i. Let K = maximum_unsigned_integer / M. This is the number of possible integers mapping to each bin. E.g., with 10 MB of memory, K = 1717. There must be at least one unused integer in bin i. Clear the first K elements of A[]. Read through the file. For each integer x, if x mod M = i then set A[x/ M] = 1. Now find j such that A[j] is zero. Then the integer j * M + i is missing from the file. The above algorithm is suitable as long as M >= sqrt(maximum_unsigned_integer). Dave On Mar 16, 4:18 pm, bittu wrote: > Given an input file with four billion integers, provide an algorithm > to generate an integer which is not contained in the file. Assume you > have 1 GB of memory. > > 2nd Part > What if you have only 10 MB of memory? > > Thank > Shashank -- 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.
[algogeeks] Re: A Billion Number Question
This only works if the file is sorted. If the file starts out with values 5,7,6,... and never contains another 7, the result will be 7, which is in the file. On Mar 17, 12:19 pm, "arpit.gupta" wrote: > read the first no. . > now ans= first no +1; > if now ans is encountered while reading the next nos. add 1 to ans. > i.e. ans++; > > On Mar 17, 2:18 am, bittu wrote: > > > Given an input file with four billion integers, provide an algorithm > > to generate an integer which is not contained in the file. Assume you > > have 1 GB of memory. > > > 2nd Part > > What if you have only 10 MB of memory? > > > Thank > > Shashank > > -- 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.
[algogeeks] Re: A Billion Number Question
read the first no. . now ans= first no +1; if now ans is encountered while reading the next nos. add 1 to ans. i.e. ans++; On Mar 17, 2:18 am, bittu wrote: > Given an input file with four billion integers, provide an algorithm > to generate an integer which is not contained in the file. Assume you > have 1 GB of memory. > > 2nd Part > What if you have only 10 MB of memory? > > Thank > Shashank -- 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.
