Find an integer not among four billion given ones - Stack Overflow
stackoverflow.com
stackoverflow.com
These programming puzzles are like the old fashion puzzles http://www.lehmans.com/store/Toys___Iron_Puzzles.
* If you know the "trick", they are trivial and don't test your skill at all.
* If you don't know the "trick", they are extremely frustrating and don't test your skill at all.
* Once you know the "trick", you will look like a "genius" every time.
* The "tricks" are widely available on the internet.
Besides the "trick" issue, the "integer not in four billion" suffers from having "domain knowledge bias", which is pretty common with programming puzzle problems. This is one of the reasons programmers only hire programmers like themselves - they cannot see outside their bias box.
For someone with a bit-twiddling C/assembly background, the obvious assumption behind the puzzle is that "four billion" and "integer not among" and 1GByte implies you are given the unsigned integers 0..2^32-1 with one of them missing and you are to make a bit-map of the integers.
For someone without a bit-twiddling C background, they quite likely will both produce a perfectly valid answer and will fail the interview. For instance, finding the highest value n and returning n+1 is both correct and better than the implicitly "correct" answer in that it will take much less memory than the implicit algorithm and run much faster.
In fact, if you are allowed to take advantage of the puzzle author's bias box, the answer 2^32 will be correct every time and will be impossibly fast compared to the "correct" answer or even the n+1 answer. In fact, the n+1 answer will always be 2^32, given the bias box - the puzzle author cannot conceive of an integer larger than 2^32-1.
If you fail the interview because you assumed "integer" meant the wrong thing, then maybe you deserved to fail. You should have asked what the interviewer meant. They could have meant mathematical integers (possibly only positive ones), 32-bit ints, 16-bit ints, "bignum"-style integers, etc. If you fail to ask for clarification, then at best you deserve to have the interviewer choose a different definition and then reveal that after you've wasted time assuming 32-bit ints. Ask for clarification and don't simply assume when there are multiple possibilities.
And you're neither correct nor especially clever for answering 2^32 if the interviewer tells you the question is about 32-bit unsigned ints. 2^32 is not a valid unsigned 32-bit int. This answer is either nonsensical or incorrect, depending on how we interpret it.
Let's assume 0 doesn't count. The first 9 numbers have 1 digit each. The next 90 numbers have 2 digits each. The next 900 have 3, etcetera. That's 38 888 888 889 digits. Assume one byte per digit. Add a delimiter between every two numbers, plus one delimiter between the 3 999 999 999th and 4 000 000 000th number. That gives us 42 888 888 888 bytes.
Subtract that number from the total file size to get the number of digits in the final number. Say the file is 40 GiB. 40 GiB is 42 949 672 960 bytes. That leaves 60 784 072 bytes (or digits) for the 4 000 000 000th number.
Add 1 to that number to make sure it's bigger than any of the numbers that can possibly be in the file. Now construct a number of 60 784 073 digits by whatever method you wish.