Recently I read a blog post about the supposedly worst programming interview question. So here is the question:
Write a function that can detect a cycle in a linked list.
Basically the guy that asked the question was testing of whether you've heard of Floyd's cycle-finding algorithm (aka. the tortoise and hare algorithm) or not. If you come up with alternative solution he'd just give you more constraints. The author of the blog post has two major points of criticism about this question.
- It's a puzzler and it's just testing whether or not you've heard of this particular algorithm before and you probably won't be able to come up with the solution that matches the constraints you are given in an interview.
- You'll probably never need to implement this particular algorithm, since typically a linked list will never contain cycles if you restrict your API and the language or framework you are using might even prevent you from mangling with the pointers to create cycles.
While I consider both points are absolutely legitimate, I don't consider the question to be the worst interview question. I consider the expectations of the Interviewer to be bad. I guess there really are no stupid questions.
So let me ellaborate. The interviwer the author described was expecting to hear the answer: "Well, I'd implement the tortoise and hare algorithm and it has that complexity...". If the applicant doesn't come up with exactly this algorithm the question is considered to be answered wrongly. Here lies the error. A smart interviewer could turn this question into the best programming interview question, if he doesn't expect a particular answer but judges how the applicant is handling the situation.
Let's consider the first case: The applicant knows the solution or at least remembers the name of the algorithm. This shows knowledge on the subject. This is good. Next question.
The second case is far more interesting in my opinion. The applicant doesn't come up with this particular algorithm. Now the interviewer can judge how the applicant handles the situation. Remember it's an interview, not a test in college or university. The applicant can start questioning the assignment he received. "Why is this particular runtime constraint needed?", "Is it possible to guarantee that the given list will never contain cycles by restricting the interface?" and "Can we restrict the visibility of the pointers in the list?" are some question I'd ask, if given this assignment in an interview. This shows that when given a problem and certain constraints the applicant doesn't just mindlessly apply an algorithm he learned, but thinks about the problem itself. Maybe it can be avoided all along with little additional effort, as is often the case.
Of course this reaction might also be a sign of an applicant, who's all talk and nothing else, but this is just a single question in an interview. You can't judge a person by asking a single question. I say there's no harm in mixing in such a puzzler. It gives opportunity to judge how a person handles this situation.