Hacker News Reader

Comment by saagarjha | Hacker News Reader

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.

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

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.

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.

Reply on news.ycombinator.com