Hacker News Reader

Comment by billsix | Hacker News Reader

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.

Reply on news.ycombinator.com