Programmer's conundrums

Chuck Guzis wrote: Ah, this is funny. I was once asked the following trick question. Say you have a singly linked list. This list might be a simple chain, or it might loop on itself. For reasons that can't be explained, you are allowed to use only two memory locations to decide if the list loops or not. After a couple questions to clarify, it was allowed that speed wasn't important and that the size of an integer and a pointer were the same. A 0 pointer marks the end of the list. I quickly answered with a dumb, brute force solution: one location is a pointer, one is a counter. Increment the counter every time you advance the pointer. If the counter hits a maximal value, you know the list loops, otherwise you'll hit the end of list value first. (and no, the counter can't overflow even with a maximally long list since at least two of the 2^N locations are used by the scratch locations). The questioner was peeved with me. I had answered it and he agreed that it satisfied the question, but I could tell he discounted it because it wasn't the clever answer that he had in mind. In fact, I'm sure he hadn't even though of my answer, and I'm also sure he wasn't the clever person who thought up the question. At some point he heard this problem with the clever answer and from then on he looked down on anybody who hadn't heard it yet. The clever answer is to have two pointers. At each step of the algorithm, one pointer advances two steps and the other pointer advances three steps (any relatively prime pair of increments would work). After the pointers are advanced, check if they are the same. If there is a loop, eventually the two pointers will coincide, even if they have to race around the loop a few times before their phases align. Never mind the fact that actually coding it is a bit of a mess since at each of the places where the pointers must be advanced, each intermediate step must be checked for the end of list condition.