I like the idea of your optimization, but it will not work as stated. The largest would be something close to MAXINT, the smallest 3999. With a range of 2 billion over 32 bits, the odds of both these being within a list of a million is quite a bit poorer than 99.9%.
The stated inputs are integers between 1 and 100,000, so if you're generating 1 million inputs, then you have 0.99999 ^ 1e6 = 4.5e-5 chance (roughly e^-10) of missing any given number, or roughly double that for missing any pair of values.
The key observation here is that you're sampling a relatively small space with a much greater number of samples, such that you have very high probability of hitting upon any point in the space.
Of course, it wouldn't work if you considered the full 32-bit integer space without increasing the number of samples to compensate. And, you'd need to be a little more clever to compute the largest possible value in your range.
Indeed. My understanding is that people ask this sort of thing in interviews specifically to see if you notice the implications of restricting the input values to a narrow range.
