Yeah, it's a terrible interview question because it's just trivia. It's one of those things where the best response may be "I know this problem. It's called tortoise and the hare. Do you still want me to do it on the whiteboard?"

Yeah seems like theres somewhat of a debate over whether you should say “I know this one” on an interview, which I generally would not, but most linked list questions are so much trivia its like you either know it or you don’t. Contrast with a graph problem that I immediately know requires dfs but I can never remember the details so I can honestly put on a convincing show of working them out.

FWIW, a company once FizzBuzzed me in an interview, but with the words Fizz and Buzz substituted with parts of their company name.

I told them I recognise this as FizzBuzz.

They told me I am overqualified.

Next time I do a FizzBuzz, I'm going to add a printline("duck") to the beginning, just to see if anyone tells me, "That looks great. Just one thing--get rid of the duck." If they don't, I'm walking out.

I got it but called SnoopDawg once. I miss California.

Oof. Note to self, don't display too much [basic] knowledge in interviews...

Ah yes the dreaded overqualified reasoning

I tried that at Amazon interview where the interviewer gave me the “Alien Dictionary” problem unmodified. Calling her out on it wasn’t wise, as I’m sure she torpedoed my chances while still doing decent on the rest of the loop.

An Amazon interviewer once gave me the word ladder problem unmodified.

I am not a recent college grad, and I don't encounter a lot of interesting algorithm problems in my work, so I had prepared by working through some leetcode problems. But I had worked through only "easy" and some "medium" problems because I had the impression they didn't ask the harder ones. I was able to recognize it as a BFS graph problem and gave the time complexity (and space complexity, IIRC), but I did not finish it on the whiteboard.

Live and learn. Maybe I'll have another go in six months. Can't argue with the money and the resume cred.

Amazon really isn’t that prestigious. Only work there if they have a job that interests you.

I'm in flyover country. It's certainly prestigious here.

I think she was surprised that this was a standard interview question? None of the other interviewers did a Leetcode question.

It is a standard question

> Sorting, graph traversal, and other algorithms are well covered by undergraduate computer science curriculums, but this algorithm is basically impossible to come up with unless you know it already and it’s not even something that you would “know to know”…

Even a lot of the "basic algorithms" taught in undergrad courses would be gnarly to invent on your own without clues in less than an hour. There's a reason they're named after famous computer scientists. If they were easy, we wouldn't bother teaching them.

Most LeetCode questions like this are just riddles, especially at the moderate+ range. You either studied the question and know the answer or haven’t but could figure it out in a day or say, but not 45 minutes. And studying these questions have no value outside of acing interviews. But at least they know the interviewee cares enough to cram for the interview.

I never have had to suffer these types of interviews. But I keep thinking, the problem was thought up and answered with a lot of work by someone smarter than anyone in the room. And they want to see if the victim can cough up the answer like a trained monkey? What does that prove exactly.

I can only come to the conclusion that it shows you think like they do (or at least can change to do so)—for better or for worse?

actually, that's a good observation - this question depends a lot on knowing one specific solution to a problem. It really is an old "riddle", as was amusingly observed in the line: "Tim retells an old riddle, though he does not know its origins, and has the words wrong." I knew this was going to be a good one when I read that line, had me chuckling within the first few minutes.

I’ve had it in 2 interviews. I got better positions at better companies.

I don't know why this was downvoted - it only takes a single counter example to invalidate an absolute claim like "impossible".

Of course I can't prove I independently reinvented the tortoise-and-hare algorithm, you'll have to take my word for it. But it should be obvious that somebody did it or it wouldn't be well known today.

Yeah, considering it was an open question for 12 years, I'd be pretty surprised if you solved it immediately after hearing the solution. If you were provided hints by the interviewer and got to it with some directions, I most would believe it more.

What's more likely, somebody figured the solution out to a problem that previously took over a decade in under an hour and then felt the need to brag about it to strangers on the internet; or somebody lied online to feel better about themselves. People are certainly more likely to assume the latter.

Or perhaps people in the late 2010s are just better placed to answer this sort of question easily than people were in the late 1960s.

I don't remember when I ran into this, but it was certainly earlier than the 2010's. Perhaps 1980's or '90's.

Certainly the Internet has made it more likely that you've run into it and heard the solution.

I didn't know the history, I had no idea it was an open question for 12 years!

As I said, it was a very long time ago when I heard of the problem. I don't think it was in an interview, but I honestly don't remember the circumstances. I do remember being quite proud of myself, so I guess there's truly an element of bragging in my statement. Doesn't mean I lied though.

It appears the tortoise-and-hare solution was found by Floyd in 1967. That means the problem was first proposed in 1955? I'd love to learn more about it, do you have a source for that?

mark-r, when somebody uses the term "impossible" - generally it may mean 2 things: a) it's truly impossible b) It's very unlikely but still possible.

You settled for a). Typically of what geeks do ( yeah, I'm guilty of it too).

Anyway. you seem to be an outlier to being able to solve the problem without having being familiar with it before hand. Do you realize you are extraordinary? (FYI: I'm not saying that with sarcasm, you might indeed be "riddle" genius, or perhaps even a "real problem", problem solver)

I can see now that I was interpreting the statement contrary to the intent of the writer. Sorry about that, and thanks for pointing it out.

I've always thought of myself as being pretty clever, but I'll bet many HN readers would say the same about themselves. "extraordinary" seems a little over the top, but thank you.

>I've always thought of myself as being pretty clever, but I'll bet many HN readers would say the same about themselves. "extraordinary" seems a little over the top, but thank you.

There are enormous implications to this seemingly harmless labeling of yourself ( not blaming you). I insist you are extraordinary, not merely 'pretty clever', not only based on my observation but also judging by other people's reactions to you your post.

Off the top of my head there are 2 implications that can be typically attributed to such traits ( and I'm not saying that you are particularly cause those implications, it's just typical):

- if someone like you is an interviewee for a programming position, your average Joe interviewer who asks you algorithmic questions ( or often some clever question) will not like the fact that you can easily solve the problems that you are presented with.

- If a person like you is an interviewer for a regular corporate programming position( which does not involve algorithms), the person is likely to pose problems of this nature to candidates for the job. When candidates routinely fail to solve those problems the person is left wondering why the candidate pool is so bad. To the interviewer the solutions seems so obvious ( or can be figured out easily) to someone who is just 'clever'.

And the industry complains how it cannot find people for CRUD programming jobs....

Note that I said "basically impossible", so I was leaning towards b :)

I figured, that's what most "normal" people would assume. ( and so would I).

But computer geeks ( we are talking about kind of people who code for 'fun') are not normal people. Their default is to take words' meaning literally, unless they have somehow (often painstakingly) managed to learn the ways of normal folks communicate.

I think what folks are implying here is that the 'somebody' who initially came up with this likely didn't do so in a 55 minute whiteboard session.

Other people are implying that named algorithms, especially those named after someone famous, are somehow more special/difficult. Sometimes they are, but often they aren't. "Linear search" for instance is the name given to the easy idea of: iterate through an array until the value == search value or you hit the end. Most candidates could do this, though they might sweat a bit if you said "find x by implementing linear search" as the name for such a straightforward idea might not be known. They might have trouble writing proofs about its properties, which is where I imagine a lot of supposed scariness comes from. (i.e. "This approach looks correct but I haven't proved it yet." Academics aren't satisfied with just a test suite, or "looking at it".)

My favorite named-after-a-person one like this is Dijkstra's algorithm, which he claimed to have come up with in 20 minutes on the back of a napkin. If we suppose the average professional engineer is at most 3x slower/less brilliant than Dijkstra, it's not that unreasonable to imagine someone could reproduce the design on a whiteboard in a full hour...

Of course I don't buy that assumption, nor do I think it's a good problem or good idea to have as an interview filter even if it was true. (While I enjoy the occasional programming puzzle, I hate that they're lazily used to evaluate people in interviews so at least I avoid ever giving pure algorithm puzzles for interviews.) Nevertheless I agree with Mark that it's not "basically impossible" to come up with a good algorithm for many classes of algorithms and problems. I do wonder though how many people who could reinvent tortoise+hare without seeing it explicitly before would then be able to reinvent the teleporting turtle optimization right after.

There are other simple algorithms you could come up with that have the same big-O.

I’d be happy to hear about them if you know any!

Iterate over the list, re-tying it backwards as you go. If you reach the end, there's no loop. If the order is important, you can re-tie again, still in O(N) time. If you end up at the head, there's a loop.

Fun and really dirty solution! I would never come up with this because I would not dare to modify a passed data structure unless this was the purpose of the procedure.

One could use that answer to gauge the humour of the interviewer :-) For me the expected reaction of a peer to this would be "Cute! Now explain the problems I could encounter when using it." If they can't deal with some fun, well, their loss.

If you can't modify the original list, you can create another as you iterate. But that will require extra O(N) memory, so is worse than the textbook solution with two pointers.

Interesting! I didn't know the solution with two pointers and would have assumed O(n) memory as a lower boundary.

I must admit I didn't follow the bytecode too closely. So thanks for pointing that out.

> Iterate over the list, re-tying it backwards as you go.

What does "re-tying backwards" mean?

Before: a->b->c

After: a<-b<-c

What if you end up at head+1, not head?

How would you end up there? With a loop, head+1 would point to head after the first pass, so you'll end up at the head. With no loop, head+1 would only be passed once.

Take the naive n^2 algorithm, but test only the nodes whose distance from the start is a power of two.

This seems just as magical as the original algorithm. Do you have insight as to why it works and what though process is necessary to arrive to it?

> This seems just as magical as the original algorithm.

If you do a "change of coordinates" the original algorithm becomes trivial: If you know that any loop in the list doesn't begin after the node you're on, you can just mark where that is, run ahead, and check if you ever come back. In the general case, "change coordinates" so that with every step, the origin advances one step. Now you'll eventually be in the previous case.

It's an act of logification.

since it's java, you have access to a Set. add each node to the set if it is not present, O(1). A bit more aggressive, check System.Runtime.heapSize() calculate how many nodes can fit in the heap, and subtract 1 for each element visited. Still O(1) With lower level access, recognize that pointers are always powers of 2, so go ahead and tag that pointer (p = p | 1, if *p & 1, it's a cycle.) you'll build up a stack, and have to fix the tagged pointers, but also O(1). I dunno. the double advance is a cute trick, but if the fast moving pointer doesn't do the check, you can easily spin into an infinite loop. It's not a _hard_ problem. You just have to keep your wits about you. Lots of ways to solve it.

> add each node to the set if it is not present, O(1).

Not in space complexity.

> A bit more aggressive, check System.Runtime.heapSize() calculate how many nodes can fit in the heap, and subtract 1 for each element visited.

This one will take quite a while…

> recognize that pointers are always powers of 2, so go ahead and tag that pointer

They're not always, and this is also technically uses extra space.