Hacker News new | past | comments | ask | show | jobs | submit login

yeah, the bitwise xor was my next solution, and what the interviewer was looking for. i found it a fun puzzle, satisfying to solve and not really brittle at all (why would you feel it was? it's just a simple loop with an xored accumulator; it cannot overflow or do anything funny).

i like the idea of subtracting from either the head or the tail of a virtual list too; that's clever :)




it's really brittle for the reason that I mentioned originally: by using a more robust, correct solution, (sorting) you can check that the input is proper, and if not, raise the appropriate exception or return the appropriate error, or simply return -1 or 0 or some other signal value. At any rate you will not silently, and in a way that seemingly works, return some arbitrary value which is simply not true. (Which is the worst kind of failure.) This does not have a large cost.

With the xor solution, on the other hand, you don't really have that option -- if the input does not exactly match the input condition, then it WILL return whatever - with no indication that anything is amiss. Even slightly wrong input will give unpredictable, completely wrong output with no indication that anything is wrong.

What's worse is that it's trivial to game: as an exercise try making a malicious generator that takes an n of at least 4 and Target number, and returns (generates) an array (of size n-1) for feeding the XOR solution that shall get the xor solution to output the Target as the missing number. Further, the malicious generator, instead of generating an array with one missing number, actually shall generate a list which is as close to correct as possible, except that it shall (as an extra 'fuck you') in all cases contain the "Target" value -- twice.

btw thanks for the feedback on the sum thing :)




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: