Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Tortoise and The Hare: Loops in Linked Lists

coryg89.github.io

Post reply on HN
Print view View original

11–20 of 20 posts

Re: The Tortoise and The Hare: Loops in Linked Lists

#11

Post by sliverstorm »

sitkack wrote: post #7

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 ..." or "…

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.

Re: The Tortoise and The Hare: Loops in Linked Lists

#12

Post by CoryG89 »

tokenrove wrote: post #10

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 sho…

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.

Re: The Tortoise and The Hare: Loops in Linked Lists

#13

Post by CoryG89 »

ColinWright wrote: post #2

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.wikiped…

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.

Re: The Tortoise and The Hare: Loops in Linked Lists

#14

Post by gsg »

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.

Re: The Tortoise and The Hare: Loops in Linked Lists

#15

Post by rjzzleep »

sitkack wrote: post #7

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 ..." or "…

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.

Re: The Tortoise and The Hare: Loops in Linked Lists

#16

Post by walshemj »

rjzzleep wrote: post #15
sitkack wrote: post #7

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 ..." or "…

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 ou…

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.

Re: The Tortoise and The Hare: Loops in Linked Lists

#17

Post by yetanotherphd »

rjzzleep wrote: post #15
sitkack wrote: post #7

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 ..." or "…

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 ou…

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

Re: The Tortoise and The Hare: Loops in Linked Lists

#18

Post by TLSaracen »

sitkack wrote: post #7

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 ..." or "…

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!

Re: The Tortoise and The Hare: Loops in Linked Lists

#20

Post by sitkack »

rjzzleep wrote: post #15
sitkack wrote: post #7

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 ..." or "…

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 ou…

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