This is a good example of why programming puzzles do a poor job of testing an applicant's problem solving ability.<p>These programming puzzles are like the old fashion puzzles <a href="http://www.lehmans.com/store/Toys___Iron_Puzzles" rel="nofollow">http://www.lehmans.com/store/Toys___Iron_Puzzles</a>.<p>* If you know the "trick", they are trivial and don't test your skill at all.<p>* If you don't know the "trick", they are extremely frustrating and don't test your skill at all.<p>* Once you know the "trick", you will look like a "genius" every time.<p>* The "tricks" are widely available on the internet.<p>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.<p>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.<p>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 <i>n</i> and returning <i>n+1</i> is both <i>correct</i> and <i>better</i> than the implicitly "correct" answer in that it will take <i>much</i> less memory than the implicit algorithm and run much faster.<p>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 <i>n+1</i> answer. In fact, the <i>n+1</i> answer will always be 2^32, given the bias box - the puzzle author cannot conceive of an integer larger than 2^32-1.