This is a cool little algorithm. I've heard about it first in the context of "nightmarish interview questions" though, where a programmer was meant to derive the technique from thin air :)
Yes it is routinely used as a way to humiliate candidates, because it's a perfect brain teaser: Devilishly simple but difficult to conjure unless you've seen it before - "Why couldn't I think of that???" Most undergrad CS curriculums won't cover it.
According to the solution in the video, the problem upthread was stated incorrectly. There's an additional constraint that only integers in the interval [1, N], where N is the size of the array, are permitted; or at least where the numbers can be trivially mapped to that interval (e.g. subtraction of an offset).
Haven't gone through the proof closely, but I suspect this would work for any prime for the tortoise, not just 2 (though 2 is probably optimal in actual implementation). This is the most I've used my discrete math degree in my 2.5 years post undergrad.
Well you want kx+b = x (mod m) to have a solution for all b and m (here b depends on how much earlier the hare enters the cycle). This means you'll need to have k-1 comprime to m for all m>0. Pretty sure k-1 = 1 is the only solution.
As a counter example where both k and k-1 are prime consider k=3. Then:
> Well you want kx+b = x (mod m) to have a solution for all b and m
I prefer to think about this another way.
I'm also confused by your parent's comment "I suspect this would work for any prime for the tortoise, not just 2". In the post, 2 is the speed of the hare, and the tortoise's speed is 1.
Anyway, what you want is for the hare to meet the tortoise. In the general case, tortoise and hare both have arbitrary speeds t and h and enter the cycle at random positions.
The cycle is m nodes long. What you need is for (h - t), the amount by which the hare catches up to the tortoise, to be coprime to m. Since m could be anything, the only solution is h - t = 1. But you could have a hare going 6 nodes per timestep and a tortoise going 5.
If you check every node that the hare enters, you don't need the relative speed to be coprime to the cycle-length. This eliminates the need for the hare and tortoise to finish a round on the same node; the hare passing the tortoise is sufficient evidence to detect a cycle.
This change adds a performance penalty with the extra equality checks, but can reduce the total number of steps in certain contexts (e.g. lists with long cycles that appear at an early node can benefit from a much faster hare).
> If you check every node that the hare enters, you don't need the relative speed to be coprime to the cycle-length. This eliminates the need for the hare and tortoise to finish a round on the same node
> This change adds a performance penalty with the extra equality checks, but can reduce the total number of steps in certain contexts
The post seems to think that most of the value in this approach comes from the fact that it's easy to identify the beginning of the cycle after you've identified that the cycle exists. The method relies on the tortoise and hare finishing a round on the same node. Does that generalize to the case where the hare just passes the tortoise at some point?
I wasn't thinking about that when I commented, but you're absolutely right. I definitely missed the point.
I don't think there is any way to generalize the algorithm in the article to work on the method I described. However I was able to find an alternate algorithm to find the initial node of the cycle. It also has linear time complexity and constant storage, but it requires that the pointers in each node be mutable. It is also worse than Floyd's algorithm in almost every way. The algebra gets a little annoying, so I've just provided the informal algorithm below.
0) Find the meeting point as described above.
1) Find the cycle length.
2) Find the distance to the meeting point k+x (where k is the length of the linear portion and x is the number
of nodes from the start of the cycle to the meeting point).
2a) If the hare speed is double the tortoise speed and the tortoise speed is less than the cycle length, this can be found directly.
2b) Otherwise, we can send a probe from the head until it reaches the meeting point.
This unfortunately this isn't enough information to find the initial node of the cycle, so more drastic measures are needed.
3) Reverse all of the nodes of the cycle (We can actually do this during step 1 if we want to be more efficient, although some care needs to be taken (e.g. that step 2b is performed first).)
4) Send a probe from the head and count the steps until it reaches the meeting point node. This will have gone k + m - x steps.
5) Now we use some algebra to get x in terms of k and known values. We can substitute this into our equation that gives a known value for k+x (from step 3) to find k.
6) Reverse all the nodes of the cycle so they are back to how they originated.
7) Advance k times to reach the first node of the cycle; return this node.
The additional steps have a linear order complexity with respect to the number of nodes of the linked list. And like the OP algorithm, only a constant amount of storage is necessary, although reversing the list will require a couple more pointers to nodes. I'm not sure if there are many cases where this would perform better, but if they do exist they seem like they would be extremely rare.
> By now you may be wondering why we do not simply use a set, and return fast if we encounter a node already in the set. Or, indeed, to solve what we’re building towards, we could just return the first value which is already in the set. (...)
> However, as I mentioned, this solution is spatially inefficient,
Typically you'd need to store N pointers, and the list would be of size N(size_of(pointer) + size_of(node)) - which would normally be much larger than the pointers? (otherwise use an array, perhaps?)
What are some real world cases where long linked list of very light nodes are best checked for cycles with this algorithm?
You might have an abstract function f which takes and returns an integer, and you want to figure out if this function has “cycles”, eg if ffffff(n) = fff(n) etc. The numbers used might be enormous, and so trying to store them all is a non-starter.
As a semi off-topic aside, the title of this post is genius!
It serves both the job of making those curious who are not in the know (and hopefully get their clicks), while also telling the rest exactly what it's about (and save our time).
25 comments
[ 3.1 ms ] story [ 68.1 ms ] threadhttps://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoi...
The serious ones do. At least, I found it to be commonly known.
Ex: 1 2 3 1 1 3 1 => 1
Hints
1- It can be done in one pass, linear time, constant space
2- It doesn't have to be numbers
3- The algorithm it is literally just 2 statements in a loop
Edit: I think I figured it out!
[1] https://aphyr.com/posts/341-hexing-the-technical-interview
As a counter example where both k and k-1 are prime consider k=3. Then:
3 x + b = x (mod 2)
will fail to have a solution for odd b.
I prefer to think about this another way.
I'm also confused by your parent's comment "I suspect this would work for any prime for the tortoise, not just 2". In the post, 2 is the speed of the hare, and the tortoise's speed is 1.
Anyway, what you want is for the hare to meet the tortoise. In the general case, tortoise and hare both have arbitrary speeds t and h and enter the cycle at random positions.
The cycle is m nodes long. What you need is for (h - t), the amount by which the hare catches up to the tortoise, to be coprime to m. Since m could be anything, the only solution is h - t = 1. But you could have a hare going 6 nodes per timestep and a tortoise going 5.
This change adds a performance penalty with the extra equality checks, but can reduce the total number of steps in certain contexts (e.g. lists with long cycles that appear at an early node can benefit from a much faster hare).
> This change adds a performance penalty with the extra equality checks, but can reduce the total number of steps in certain contexts
The post seems to think that most of the value in this approach comes from the fact that it's easy to identify the beginning of the cycle after you've identified that the cycle exists. The method relies on the tortoise and hare finishing a round on the same node. Does that generalize to the case where the hare just passes the tortoise at some point?
I don't think there is any way to generalize the algorithm in the article to work on the method I described. However I was able to find an alternate algorithm to find the initial node of the cycle. It also has linear time complexity and constant storage, but it requires that the pointers in each node be mutable. It is also worse than Floyd's algorithm in almost every way. The algebra gets a little annoying, so I've just provided the informal algorithm below.
0) Find the meeting point as described above.
1) Find the cycle length.
2) Find the distance to the meeting point k+x (where k is the length of the linear portion and x is the number of nodes from the start of the cycle to the meeting point).
This unfortunately this isn't enough information to find the initial node of the cycle, so more drastic measures are needed.3) Reverse all of the nodes of the cycle (We can actually do this during step 1 if we want to be more efficient, although some care needs to be taken (e.g. that step 2b is performed first).)
4) Send a probe from the head and count the steps until it reaches the meeting point node. This will have gone k + m - x steps.
5) Now we use some algebra to get x in terms of k and known values. We can substitute this into our equation that gives a known value for k+x (from step 3) to find k.
6) Reverse all the nodes of the cycle so they are back to how they originated.
7) Advance k times to reach the first node of the cycle; return this node.
The additional steps have a linear order complexity with respect to the number of nodes of the linked list. And like the OP algorithm, only a constant amount of storage is necessary, although reversing the list will require a couple more pointers to nodes. I'm not sure if there are many cases where this would perform better, but if they do exist they seem like they would be extremely rare.
> However, as I mentioned, this solution is spatially inefficient,
Typically you'd need to store N pointers, and the list would be of size N(size_of(pointer) + size_of(node)) - which would normally be much larger than the pointers? (otherwise use an array, perhaps?)
What are some real world cases where long linked list of very light nodes are best checked for cycles with this algorithm?
It serves both the job of making those curious who are not in the know (and hopefully get their clicks), while also telling the rest exactly what it's about (and save our time).
Jokes on you, I've got 128 gigs of heap.