Heh, I once was introduced to a particular interview question. It has a solution that is hugely better than the best naive solution, but is basically a giant gotcha that seems obvious in retrospect. I couldn't find it myself even though I was stumbling around in its neighborhood. Obviously I gave this question informally to a ton of people as entertainment (Bay Area techies in various companies), and most couldn't find it either.
However, one guy told me he now uses the question as his actual interview question because he thinks the way people suffer thru a seemingly impossible problem reveals how good of an engineer they are :D
Sorry, I was offline for the break. You have a singly linked list with each node having a "random pointer", an extra field that points to another node in the list (including itself or null). You need to make a copy of the list, in such manner that random pointers in the copy correspond to the original list, e.g. if the 10th element of the original points to the 3rd element of the original, 10th element of the copy needs to point to the 3rd element of the copy.
However, one guy told me he now uses the question as his actual interview question because he thinks the way people suffer thru a seemingly impossible problem reveals how good of an engineer they are :D