Create a range tree, pruning out as needed to stay in the memory constraint.
Don On Jun 9, 6:24 am, Dumanshu <duman...@gmail.com> wrote: > Given a file containing roughly 300 million social security numbers(9- > digit numbers) find a 9-digit number that isnt there in the file. You > have unlimited drive space but only 2mb of RAM. > > Solution is as follows: > In the first step, we build an array of 2^16 integers that is > initialized to 0 and for every number in the file we take its 16 most > significant > bit to index into this array and increment that number. Since there > are less than 2^32 numbers in the file there is bound to be one number > in the array that is less than 2^16 . This tells us that there is at > least one number missing among the possible numbers with those upper > bits. In the second pass, we can focus only on the numbers that match > this criterion and use a bit-vector of size 2^16 to identify one of > the missing numbers. > > Someone plz explain this solution( may be using some small values > numbers) or suggest another approach. -- 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.
