The Tortoise and The Hare: Loops in Linked Lists

http://coryg89.github.io/technical/2013/12/12/the-tortoise-and-the-hare-loops-in-linked-lists

by CoryG89 • 13 years ago

27 19 13 years ago

coryg89.github.io

ColinWright2• 13 years ago

Added 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...

CoryG895• 13 years ago

Yeah, I wish I had been reading HN back 1,429 days ago.

ColinWright2• 13 years 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.

CoryG895• 13 years ago

I am not sure about the job yet. I did get another interview on Skype. I had to do coding in a shared text editor while two interviewers watched me through a web cam. Puts someone looking over your shoulder to shame as far as pressure goes. I felt like I was much slower at everything because of how nervous I was. Other than that I feel it went okay. Hopefully I'll know more before too long.

gicmo• 13 years ago

Funny, 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! ;-)

CoryG895• 13 years ago

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.

sitkack2• 13 years ago

This 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 ..."

"We have a system to solve VVV using UUU what issues good and bad do you see with this?"

sliverstorm• 13 years ago

It could be a good interview question if they weren't looking for "the right answer", but the "we're out of time" after only the second go-round suggests it wasn't intended as the very-hard-question they want to watch you try to solve.

rjzzleep• 13 years ago

it's funny you say that. i once had an interview question from a bank saying how would you create a system that can find certain things in large xml documents faster than our competitors.

I said: "I would use grep"

so he asked, what if i also need to find attributes and some other stuff i can't remember.

I said: "ah okay, in that case I would use a document store, like eXist"

He asked: "but would it be faster than our competitors?"

i start thinking how the hell would i know, and said: "i'd get something running, and then think about how we can optimize it afterwards"

why the hell would i design a database system from scratch? needless to say he didn't really like what i had to say.

walshemj• 13 years ago

The q woudl be how fast our are competitors? searching a huge document store for a given id say scale out using something like hadoop.

yetanotherphd2• 13 years ago

You should have told him you would run it on overclocked CPUs

sitkack2• 13 years ago

I'd go get a job with the competition so I knew how faster their systems are. Also a ridiculous question.

TLSaracen• 13 years ago

I was under the impression that this question in particular was extremely common, and that most candidates already have heard of the solution. Because of this, I really hate this kind of question because you're getting an incredibly skewed view of the applicant's problem-solving skills. On the other hand, while design questions are important, there are other important qualities of a candidate that aren't best assessed by knowing how her or she would design a system (such as coding/problem solving/logic skills). I think the main point is interviewers should stop being lazy and come up with their own unique questions. For example, when I was interviewing at companies after college, I got the BST least common ancestor question at least 3 times. I'm sure the 3rd company had a much better impression of me than the first, even though I didn't get any better at problem solving. A simple question I sometimes ask is "through a football game, you can score (for simplicity's sake) some combination of touchdowns (7 points) and field goals (3 points). Write a function that takes a final score and outputs the number of possible ways a team could've reached that score."

OP, best of luck on the rest of the interview process!

yetanotherphd2• 13 years ago

It'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.

tokenrove• 13 years ago

This 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.

CoryG895• 13 years ago

I agree, they mentioned something along the same lines while I was coming up with my horrible attempts. I really like the algorithm as well.

gsg• 13 years ago

Cyclic lists might not be a good interview question, but working through some of the details is a great exercise.

A good follow on from finding whether there is a cycle is finding the length of the lead-in and cyclic parts of the list, and then implementing a map function over cyclic lists. There are some interesting tricks that rely on non-obvious properties of cyclic lists.

phamilton• 13 years ago

Which company was this?

The Tortoise and The Hare: Loops in Linked Lists

Related Stories