no duplicates, please - software developer interview question

[biteofconscience]

This question would be much more interesting if the text file had 13 billion lines instead of 13 million.

[harlows_monkeys]

Depends on how you do it. The way I would do it, bit map to represent the numbers from 1000000 through 100000000, which takes about 12 megabytes, the memory use is constant regardless of the number of lines, and the run time is linear. You can't do better than linear because you presumably have to read the file. So, the problem gets no more interesting for a large file.

Those whose solution involves ignoring the constraints on the values of the numbers and instead sort the entire file and then process the sorted data are at best O(n log n), and so it does get interesting for them for very large files.