Let’s start someting new. I’ll add more as I find more stupidity to complain about, hmm?

The Linked List Interview Question

Stop me if you’ve heard this one before….

The bright eyed, bushy-tailed, academic who is so excited to be working in games asks you what he thinks is a very clever question: “How would you go about finding a loop in a singly linked list of unknown length?”

You think about it a moment, then ask, “Why is there a loop in the list at all? It’s an error condition that should have been caught before it corrupted the list.” He says, “Well, let’s just assume someone did something stupid, and it’s like this now.”

Okay. The most obvious cause of a loop is a double insertion. So we’re going to abandon the best practice of verifying input before working with it? Why would we do that? The point where the node is added is the obvious and optimal place to check. It’s also the point where you can stop the error before it breaks things, where you can actually have some sense of the context of the data. If you find the loop after the fact by analyzing the list without context, how do you repair the list? You can’t be certain what to do with a duplicate node. Do you remove all but the first instance? All but the last? Is order even important? Every ounce of experience tells you to modify the list code to prevent this from happening to begin with, and choose the correct course (ignore the new input, or remove the old one prior to adding) based on the intent of the list.

Hmm, how else could we get a loop? Someone could mod our pointer? C++ has private data members, and this is a classic case where they should be used. No one outside the linked list implementation should have access to these pointers to begin with.

Someone could delete an entry and not remove it from the list? Easily circumvented by overriding delete() for the class in question and doing a check. Again, C++ provides a good solution.

Memory stomp? The memory manager should have a debug mode to detect this and warn of the occurrence.

In all cases, we could and should be solving this problem at a centralized location, and using the facilities the language provides to avoid the situation entirely.

Only that’s not the answer the guy wants. “Let’s just assume you can’t do that.”

You ask why we don’t know the length of the list, since it’s an obvious and trivial thing to add to the implementation? Then you could walk the list and if you exceeded the count, you’d know something was wrong. “Well, never mind that, you just don’t. How would you go about it?”

Context is even more difficult now. Ok, so I am using a linked list that is not only half-assed and lacks the capabilities of a list in the STL, but also that I somehow I don’t have access to the source to fix it properly. Why would that be? Well, maybe it’s a library. But why am I using a broken library? Why don’t I replace it with my own code? It wouldn’t take very long to write a more robust system that would eliminate this situation and handle it properly.

Again, “Let’s just assume you can’t do that.”

Jeez, Louise, so I have to assume I suck as a programmer to answer the question? Why do you want to know how a sucky programmer would solve this problem? How can I think like a sucky programmer unless I am a sucky programmer? If you know C++, you know full well that there really isn’t such a programming situation. The entire point of C++ is modularity. Don’t like printf()’s default behavior? Override it with your own version. I really can’t think of a situation where this would be a problem. My feet are no longer in contact with the earth in regard to this question.

Okay, okay, let’s assume the code was written by the CEO, and he’s a crazy jealous guy who will fire me if I mod even one character of his precious code, or even have the temerity to suggest that his code is anything but absolutely perfect. Ignoring the obvious solution of refusing to work for such a person (“Let’s say the CEO has a gun….”), well then….

We could record all of the pointers and see if any of them matched. It’s expensive, though. It’s a bad solution.

He doesn’t really care that it’s a bad solution, just that it’s not the one he has in mind. “Let’s say you don’t have the memory for that.”

Hmm. *Scratches head.* Ok, if we’re on a modern system, and we’re behaving in a mostly sane manner, we’re dealing with aligned pointers. I could set bit 0 of each node pointer as I pass, and then if I come across one with the bit set, I would know  had a loop. Of course, I’d have to reset them after the fact, and it could be bad in a multithread environment if someone else was meddling with the list. We wouldn’t want to lock other threads out for that long, either. So it’s a bad solution, too.

Same deal, doesn’t really care about the ‘bad’ part, only that it’s not the clever answer he has in mind. “Well, let’s say this list is in ROM.”

At this point, I have no answer but the one no programmer should fear, but too many do: “I don’t know.” And junior programmer smiles patronizingly, certain that I know fuck all about anything. He concludes this not because I don’t understand programing, but because he has read or heard something he thought was clever, and I have not. But in point of fact, it’s not even clever.

The answer he wants, which anyone could find in less than 30 seconds searching google, is simple. You iterate the list with two pointers, one going one at a time, one going two at a time, and if the pointers are ever the same, then you have a loop. But it’s a useless solution. Once you detect the loop, you still don’t really know how to fix the problem, in that you have no context. The best you can do is hope that it was caused by a double insertion, and pick a node at random to preserve, or scissor it out entirely and hope for the best. If it was a double insertion, either choice is a hail Mary and hope for rain. If it was a memory stomp or someone meddling with the pointers, you’re just outright screwed. It is a fact that an error discovered in a linked list is a catastrophic failure that can’t be solved without context. Any solution that works is blind luck, not proper engineering, and is a bug waiting to happen because it relies on undocumented, perhaps unknown behavior.

In addition, it’s a more laborious process than having checked the input when the node was added.

But this was the clever answer he wanted, and no other solution counted, even if it was superior.

The academic will justify this scenario by saying it tells him how you think about things. But does it? I suppose it says something, in that it tells him whether you simply accept a problem at face value and plod away at it, or whether you actually try to dig deeper, find the root cause of the problem, and solve it correctly.

This question, like many others one runs across, says more about the questioner than the questioned. It says the questioner doesn’t think deeply about how his system interacts with others, and that his designs, while perhaps clever in their own right, may be completely wrong for the priorities at hand.