Interview Question for Software Engineer at Google:

First I would ask if the numbers in the file are sorted, if yes a thread pool might be a good idea with indexes seeking at different position in the file depending on the worker thread. Since we do not want to load the all file limiting the number of worker thread with a partition of the file and each returning the missing value I think would work, suggestions ?
If the numbers are not sorted then it is a all different story ! I would use the same technique but first I would use multiple Thread or process to sort the file (maybe merge sort since it would work well in parallel because of its divide and conquer methodology) and then apply the above method. just some thought...

Just use a hash, where keys are numbers. Then iterate through the sorted list of keys and push the missing ones into another list.

The number are from 100 - (1 billion -1). If we use a bitset then we would need 1 billion bits = 125 MB. Assuming it'll fit in given memory we can do a 1 pass on the file and in the end just print out the cleared(0) bits of bitset starting from index 99 (100th bit).

As it is clear requirement that file should not be loaded/open for long time. I think reading file in chunk and as alex also mention, having hash-map is faster solution then just using plan bit-set. Run-time complexity to set individual bit in bit-set based on number read from file is MORE than hash, which gives near O(1) complexity, but yes space complexity with hash is HIGH (could be "125MB + 125*8 MB" or 16*125MB)).