4 ms·

Fucking Christ, both the OP's answer and logfromblammo's one are all that's wrong with this industry: really zero field experience and requiring the academic, P

Fucking Christ, both the OP's answer and logfromblammo's one are all that's wrong with this industry: really zero field experience and requiring the academic, PhD-thesis level clever fucking answer. A seasoned professional would use a fucking map and get the job done. No XOR tricks, no clever arithmetic, no niche BitSet crap. FOR i=1 to 100 occurences_map[x[i]]++. FOR i=1 to 100 if occurences_map[i] == 0, found the fucking number. Of course giving this answer WHICH SOLVES THE FUCKING PROBLEM gets me instantly disqualified for not being cumbersome enough for the liking of the rookies running the industry.

anyfoo 8y ago
No, it does not get you "instantly disqualified". I think if an interviewer posed that question to you exactly as stated, namely with a 100 numbers, they would tell you that you did a good job and solved the problem in a perfectly reasonable way. So now that we've set the scene, let's scale for a million numbers, rounding up to 2^20. The existing solution needs at least an extra megabyte (since you are not setting individual bits, it will be at least a byte per number), and a second pass of scanning through that entire megabyte. Fine in a web application, maybe not so much in an embedded system kernel. How can we improve? And so we got a discussion started. I personally would not ask that question, since it's really a bit too generic, but you get the gist: Start out with something that sets the scene (and catch unqualified people really early), and opens up discussion for more and more interesting discussions.
logfromblammo 8y ago
I thought about including the answer that doesn't require branching, but didn't, because it sounded too fucking clever even just proofreading it. The N(N+1)/2 and summation is the answer they probably expect. Gimmicky XOR tricks set you slightly ahead of the pack. Magical bit-twiddling answers and branch elimination make you look pretentious, unless you're literally Carmack. My point was that solving the problem as posed does not solve the problem inherent in posing the problem. Finding the one missing number in an array of otherwise consecutive numbers means that you were already storing N-1 numbers instead of the one number you wanted. If you stored the missing number instead, it's trivial to construct an array from 1 to N that skips over it. Save space, save time. And if the profiler says that this problem is on a critical path in an inner loop, optimizing the heck out of it still won't help as much as unmaking the problem entirely, pulling all the cumbersome calculations out into less-used code. If the profiler says that it barely ever gets hit, then there should be zero algorithmic tricks, and the code should be optimized for human readability instead. As an interview question, it might as well be a cryptic crossword clue, because the solutions that would be put in place by perfectly good developers are not the ones in the back of the textbook.

anyfoo 8y ago

No, it does not get you "instantly disqualified". I think if an interviewer posed that question to you exactly as stated, namely with a 100 numbers, they would tell you that you did a good job and solved the problem in a perfectly reasonable way. So now that we've set the scene, let's scale for a million numbers, rounding up to 2^20. The existing solution needs at least an extra megabyte (since you are not setting individual bits, it will be at least a byte per number), and a second pass of scanning through that entire megabyte. Fine in a web application, maybe not so much in an embedded system kernel. How can we improve? And so we got a discussion started. I personally would not ask that question, since it's really a bit too generic, but you get the gist: Start out with something that sets the scene (and catch unqualified people really early), and opens up discussion for more and more interesting discussions.

logfromblammo 8y ago

I thought about including the answer that doesn't require branching, but didn't, because it sounded too fucking clever even just proofreading it. The N(N+1)/2 and summation is the answer they probably expect. Gimmicky XOR tricks set you slightly ahead of the pack. Magical bit-twiddling answers and branch elimination make you look pretentious, unless you're literally Carmack. My point was that solving the problem as posed does not solve the problem inherent in posing the problem. Finding the one missing number in an array of otherwise consecutive numbers means that you were already storing N-1 numbers instead of the one number you wanted. If you stored the missing number instead, it's trivial to construct an array from 1 to N that skips over it. Save space, save time. And if the profiler says that this problem is on a critical path in an inner loop, optimizing the heck out of it still won't help as much as unmaking the problem entirely, pulling all the cumbersome calculations out into less-used code. If the profiler says that it barely ever gets hit, then there should be zero algorithmic tricks, and the code should be optimized for human readability instead. As an interview question, it might as well be a cryptic crossword clue, because the solutions that would be put in place by perfectly good developers are not the ones in the back of the textbook.