The Tortoise and The Hare: Loops in Linked Lists
coryg89.github.io
The Tortoise and The Hare: Loops in Linked Lists
1–10 of 20 posts
Re: The Tortoise and The Hare: Loops in Linked Lists
#2Added in edit below - I do like the write-up and have up-voted it!
Another edit: Did you get the job? Or the next interview?
Another post about an old friend. Note that this version is the more common Tortoise and Hare, rather than the Teleporting Turtle[0] version (also known as Brent's Algorithm[1]) that, under some distributions, can be faster.
[0] https://news.ycombinator.com/item?id=1068715
[1] http://en.wikipedia.org/wiki/Cycle_detection#Brent.27s_algor...
Re: The Tortoise and The Hare: Loops in Linked Lists
#3Added in edit below - I do like the write-up and have up-voted it! Another edit: Did you get the job? Or the next interview? Another post about an old friend. Note that this version is the more common Tortoise and Hare, rather than the Teleporting Turtle[0] version (also known as Brent's Algorithm[1]) that, under some distributions, can be faster. [0] https://news.ycombinator.com/item?id=1068715 [1] http://en.wikiped…
Yeah, I wish I had been reading HN back 1,429 days ago.
Re: The Tortoise and The Hare: Loops in Linked Lists
#4Added in edit below - I do like the write-up and have up-voted it! Another edit: Did you get the job? Or the next interview? Another post about an old friend. Note that this version is the more common Tortoise and Hare, rather than the Teleporting Turtle[0] version (also known as Brent's Algorithm[1]) that, under some distributions, can be faster. [0] https://news.ycombinator.com/item?id=1068715 [1] http://en.wikiped…
Yeah, I wish I had been reading HN back 1,429 days ago.
Indeed, if you had been reading HN back then you would have known the algorithm. Not sure if that would have been a good thing or not for the interview. If you aced that part they may have given you something harder. Besides, I did actually like your write-up.
Also, to some extent the point is more that there is substantial discussion back there, and some of it is interesting and useful. For those who think HN is in decline, one would therefore expect that the discussion from back then would be of high quality.
Even so, discussion there is closed, so for people who have something new to say, this would be the place. I look forward to seeing if anyone has got something new to add.
Actually, here is a serious question. Would there be value in collecting, indexing, and cross-referencing all the classics from HN?
Edited to try to clarify various points.
Re: The Tortoise and The Hare: Loops in Linked Lists
#5Earlier quoted context omitted.
Yeah, I wish I had been reading HN back 1,429 days ago.
Indeed, if you had been reading HN back then you would have known the algorithm. Not sure if that would have been a good thing or not for the interview. If you aced that part they may have given you something harder. Besides, I did actually like your write-up. Also, to some extent the point is more that there is substantial discussion back there, and some of it is interesting and useful. For those who think HN is in…
I agree.
> Actually, here is a serious question. Would there be value in collecting, indexing, and cross-referencing all the classics from HN?
Sounds like a decent idea to me. Seems like searching is the only way to get at the old stuff. If you can come up with something better than that then I'm sure you'd have something.
Re: The Tortoise and The Hare: Loops in Linked Lists
#6Funny, the "How can you detect a cycle in a Linked List" question is in the "Secrets of Programmer Job Interviews" Section (actually it is the Appendix) of the fabulous book "Expert C Programming: Deep C Secrets" by Peter van der Linden from 1994. Excellent read and apparently even the interview preparation section is still valid! ;-)
Re: The Tortoise and The Hare: Loops in Linked Lists
#7This is a bad interview question. It involves "rediscovering" a named algorithm on the fly, over the phone OR already knowing about it an acing it which is disingenuous on the part of the interviewee, or telling the truth that you know it and moving on to an equally bogus question. In the spectrum of questions, this one is near yes or no.
Good questions might start with, "how would you implement a system to ..."
or
"We have a system to solve VVV using UUU what issues good and bad do you see with this?"
Re: The Tortoise and The Hare: Loops in Linked Lists
#8Funny, the "How can you detect a cycle in a Linked List" question is in the "Secrets of Programmer Job Interviews" Section (actually it is the Appendix) of the fabulous book "Expert C Programming: Deep C Secrets" by Peter van der Linden from 1994. Excellent read and apparently even the interview preparation section is still valid! ;-)
Yes, I wonder though if books with interview prep sections like this aren't used more by the employers in later years as a reference for good interview questions to ask rather than programmers actually trying to prepare for interview questions they may be asked.
Re: The Tortoise and The Hare: Loops in Linked Lists
#9It's pretty unlikely that a person would think of this on the spot, and such a person would be almost indistinguishable from someone who had already seen the question.
On the other hand, easier but more complicated questions tend not to have single right answer, so it's harder to judge the candidate objectively.
At one interview, a lot of questions involved implementing problems that didn't require any trick (at least to people with sufficient knowledge of CS) but were fairly complex (10-20 lines of pseudocode). I think this is the right approach because sufficiently many moderately-hard questions will produce a bell curve, while questions with a "trick" provide little information.
Re: The Tortoise and The Hare: Loops in Linked Lists
#10This question seems to come up often enough. It came up in an interview I did a little while ago; I was delighted since I am a big fan of the Tortoise and the Hare algorithm (I think I originally read about it in The Connection Machine by Hillis, which is a great read in general).
I think it's a good interview question even if you're not familiar with it, because while you might not come up with the algorithm, it shows how the interviewee might reason about linked lists, and ask about what trade-offs you're looking for.