Hacker News Reader

Comment by 13of40 | Hacker News Reader

There was a linked list interview question going around back then that went: In constant time, without allocating memory, given a pointer to the first element of a linked list, how can you tell if it eventually ends in a null or if it loops back on itself at any point? I actually ended up implementing the solution while tracking down a hang in a DCOM service I was working on...

View on HN

In constant time? O(1)?

Isn’t that normally the 2 pointers (tortoise/hare) thing? If yes then I agree it’s not constant time.

I personally hate this kind of interview question. It’s one that is easily answerable when one heard the exact question before (in training for interviews). But super hard to answer if not. And it even does not have big applications in practice - in 20years of programming, I never encountered a problem like this. In the end the question just wastes time on both sides and won’t really tell a lot about the candidate.

He meant constant memory. It's to invalidate solutions marking items visited.

I too got this question at an interview once, and failed. For fun I asked everyone at work and predictably nobody came close to figuring it out.

No, I meant O(n) but used the wrong word for it.

Marking items visited can actually work, because on any(?) modern OS the memory for the elements in the list would be allocated at even addresses, meaning the low order bit of the Next pointer is always zero and can be reused as a marker.

Your solution isn't thread safe :)

It's in a critical section. (Which you pretty much have to do with the canonical one too, since it can run off the rails if another thread modifies the list.)

There was a blog post shared a while ago on HN where the author ranted that it was his least favorite interview question because the solution (fast/slow pointers) was - if I recall correctly - literally somebody's PhD thesis. There was a years-long window where anyone "clever enough" could have waltzed in with a one page paper.

If you've never seen the pattern before, there is a very good chance that you're hosed.

Edit: found it [1]

[1] https://news.ycombinator.com/item?id=7953725

The tortoise & hare algorithm [1] was not just discovered by some random PhD student, but by Robert Floyd, who won a Turing award.

[1] https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoi...

[2] https://en.wikipedia.org/wiki/Robert_W._Floyd

I used to ask this (cycles in linked list) question all the time, and I found it useful as a way to see how the candidate worked through an unfamiliar problem. No-one gave the 2-pointer answer, ever.

For me it wasn’t a pass/fail “do you know the right answer” question, it’s more of a “can I work with this person” question.

This is a pretty standard linked list question (called cycle detection) – one of the easiest questions on LeetCode. You can use the two-pointer method to just detect if there's a cycle. If you want to find the node that the cycle starts at, you can just walk the slow pointer from the slow/fast meeting point and a pointer to the head of the list 1 step at a time until they both meet (there's a simple explanation for this that I won't bother writing out).

I must admit I didn’t figure that one out till I saw the solution which was a “oh duh” moment. I don’t think i would have ever stumbled upon it without lots of hints during an interview.

The constraints, if correctly stated, can help a lot to figure what to do if you take a look at them closely.

In constant memory there's not that many things to do, a single pointer clearly won't be enough as you can't recall if you already visited the node or not, so `K>1` pointers must be used. If any two pointers moved at the same pace they would be duplicated and the second won't give any information. That and the fact that you can only move forward leaves a pretty constraint situation and acts as a guide.

It's not a bad thought problem, but I guess the fact that it's really unlikely to happen in a real world scenario plays against it (the memory on a hash table is probably way cheaper than the extra reasoning this takes). Also, knowing a bit about the answer is an unfair advantage, it might be more of a test on memory than on reasoning, which makes the problem bad for interviews.

I don't think it is a very good thought problem because I think very few would figure it out unless they have encountered the algorithm or a similar one before.

It is one that a lot of people will go "Aha, of course" when they hear about it but not figure out themselves.

I understand the reasoning now since I know the answer but I still don’t think I would arrive at the answer even with the reasoning. I don’t use it as an interview question so I don’t know if people ever genuinely solve it or just memorize the solution.

Reply on news.ycombinator.com