Jul 1, 2010


I was thinking about an old job interview question the other day:

You have a list of numbers. Each number has a duplicate on the list except for one number. How do you find this number?

This is clearly linear time. A little less obvious is that it can be done in constant space. As far as I know, I was the only one to actually come up with a solution to this one. It's not easy, at least in my appraisal. My solution, however, wasn't exactly the one they were looking for. I'll cover my line of thought, and then cover "the" answer and explain my feelings on them.

The constant space part led me to try adding all the numbers together. Fortunately, the sum of the numbers has an important relation to the exceptional number in the list: if it is even or odd, so is the exceptional number. This is due to the fortunate fact that the sum of two even numbers and two odd numbers is even. I immediately told this to my interviewer and convinced him it was true. He didn't seem to be impressed, so I abstracted my result using group theory and showed that the same process could be essentially used to derive the value of the number bit by bit. (The full thing is a fun bit of math. I'll leave it to the reader until I get around to writing it up.) 

My interviewer wasn't impressed. Here's the official answer:

Bit-wise xor all the numbers together.

It's immediately clear why this works and I might have thought of it had I been more into low level programming. This solution seems so simple compared to the one I promised. So why is it so unappealing to me? It is the illusion of simplicity, nothing more.

There's nothing particularly natural about bitwise Xor. The solution works, but its not clear how you could get to the solution other than to conveniently know a function which does what Xor does. More importantly, the solution doesn't reveal where the power of the solution comes from. Understanding this solution doesn't help with related problems. When I was asked the problem, I approached it abstractly -- which probably hurt my ability to solve it. Thinking more about programming would have helped, but it wouldn't have led to the deeper solution I found. This is why I am more fond of my own solution, and why I believe in abstract mathematical reasoning. Thinking about computers when trying to solve computers tends to lead to concrete thinking, destroying creative thought. Creative thought is rare.