Given an input file with four billion non-negative integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB of memory available for this task.
bitmap.
FOLLOW UP
What if you have only 10MB of memory? Assume that all the values are distinct and we now have no more than one billion non-negative integers.
Make bucket.[1,10000] in bucket 1. [10001,20000] in bucket 2 and so on. In the second pass, just check every bucket.