3 ms·

The article seems to imply that the turtle and hare algorithm is only valid solution for this problem, which is certainly not the case. This problem can be als

by dfox 12y ago

The article seems to imply that the turtle and hare algorithm is only valid solution for this problem, which is certainly not the case. This problem can be also solved by building big set of already seen list nodes or adding bit to list nodes themselves. Whis is both something that everybody should be able to come up with and implement. I think that this is in fact quite good interview question because while there is one non-obvious perfect answer, it also has some sub-optimal solutions that are pretty obvious and simple to implement.

owenmarshall 12y ago
Yeah - the article built it up and built it up, but when the question finally came up my thought was "wait, that's it?!" If the interviewer asked the question and rejected anyone that didn't immediately answer with the tortoise/hare approach that's the fault of the interviewer, not the question.
potatolicious 12y ago
You're right, though I think he's talking about the weird type of interviewer who expects candidates to know obscure, non-intuitive optimal solutions to these problems. I once met an interviewer who liked to use the "reverse a string" question, except he was expecting candidates to know the XOR trick. Suffice to say few, if anyone, ever got past his "filter". Primadonna interviewers who use interviews as ego-strokes are a problem in our industry. It's where the stupid "why are manhole covers round" questions came from, and it's where these hyper-optimized algorithms questions come from.
skywhopper 12y ago
This was my first thought about how to solve it. It provably works in finite time. This ought to be a satisfactory answer in an interview, particularly if the candidate points out that it's unlikely to be The Optimal Solution. After which point, the appropriate follow-up question from the interviewers would be to ask what the time complexity of the algorithm would be in the worst case.
16bytes 12y ago
Agree. The anti-pattern here is expecting a specific answer for a question. The goal should be, "how does this candidate think through problems?" If they arrive at a logic solution and can critique it, then I would consider the question completed. Some questions are better than others here, specifically ones that have many correct implementations and varying levels of optimal-ness. I'm a big fan of asking for Fibonacci implementations, for instance. Since this question can have different correct implementations, then I would not consider it a bad question to ask. It's upon the interviewer to be open to different answers, evaluate them fairly and ask smart follow-up questions. "Ok, so what's the complexity of your answer? Do you think it's possible to do better?" or "Compare your answer with this implementation".

by dfox 12y ago

owenmarshall 12y ago

Yeah - the article built it up and built it up, but when the question finally came up my thought was "wait, that's it?!" If the interviewer asked the question and rejected anyone that didn't immediately answer with the tortoise/hare approach that's the fault of the interviewer, not the question.

potatolicious 12y ago

You're right, though I think he's talking about the weird type of interviewer who expects candidates to know obscure, non-intuitive optimal solutions to these problems. I once met an interviewer who liked to use the "reverse a string" question, except he was expecting candidates to know the XOR trick. Suffice to say few, if anyone, ever got past his "filter". Primadonna interviewers who use interviews as ego-strokes are a problem in our industry. It's where the stupid "why are manhole covers round" questions came from, and it's where these hyper-optimized algorithms questions come from.

skywhopper 12y ago

This was my first thought about how to solve it. It provably works in finite time. This ought to be a satisfactory answer in an interview, particularly if the candidate points out that it's unlikely to be The Optimal Solution. After which point, the appropriate follow-up question from the interviewers would be to ask what the time complexity of the algorithm would be in the worst case.

16bytes 12y ago

Agree. The anti-pattern here is expecting a specific answer for a question. The goal should be, "how does this candidate think through problems?" If they arrive at a logic solution and can critique it, then I would consider the question completed. Some questions are better than others here, specifically ones that have many correct implementations and varying levels of optimal-ness. I'm a big fan of asking for Fibonacci implementations, for instance. Since this question can have different correct implementations, then I would not consider it a bad question to ask. It's upon the interviewer to be open to different answers, evaluate them fairly and ask smart follow-up questions. "Ok, so what's the complexity of your answer? Do you think it's possible to do better?" or "Compare your answer with this implementation".