14 ms·

One of my all-time favourites is this: suppose you have a linked list that eventually cycles: that is, the link of one of the nodes in the list points to a prev

One of my all-time favourites is this: suppose you have a linked list that eventually cycles: that is, the link of one of the nodes in the list points to a previous node in the list, but not necessarily the first node. Write a function to compute the cycle length of the cycle. Now if it was just a simple circular list, this would be trivial: set a pointer to a node, and move another pointer a node at a time until the two pointers meet. However, this list has an initial sequence of nodes of unknown length that is not in the cycle. So the trick is really to find a node that is guaranteed to be in the cycle. A nice way to do this is to start with two pointers to the head to the list, and then advance one by a single node at a time, and the other by two nodes at a time. It is easy to see that they will eventually meet on the cycle. Once that happens, it is easy to count the cycle length. Now suppose you are running a casino and you are using a random number generator. For any given seed, the generator will eventually cycle, but not necessarily to the seed. You can compute the cycle lengths for a given seed with two variables by analogy with the linked list solution stated above.

avodonosov 9y ago
> It is easy to see that they will eventually meet on the cycle. Not easy for me, but thanks for the algorithm, maybe I will find time and energy to understand and believe. Why by two at a time and not by 3?
- RomanPushkin 9y ago
  3 will also work. People pick 2 intuitively, and it minimizes the overall runtime of the algorithm. (google "Proof of Floyd's Cycle Chasing" for details)
  - tzs 9y ago
    Another advantage of 2 is that it works even if the two pointers do not start on the same element.
    - Spivak 9y ago
      It's not specifically 2, any two speeds that are coprime will have the same property.
      - tzs 9y ago
        Counterexample: loop of 8 nodes, numbered 0, 1, ..., 7. Start with one pointer at node 0, moving with speed 5. Start the second pointer at node 1, with speed 3 which is coprime to 5, the speed of the first pointer. The pointer positions at each step are: 0 5 2 7 4 1 6 3 repeat 1 4 7 2 5 0 3 6 repeat The condition we need in order to guarantee it works regardless of where the two pointers start is that the difference between the speeds is coprime to the cycle length.
- gamegoblin 9y ago
  Consider a cycle of length n. Consider two integers, i and j that have arbitrary initial values in [0, n). We want to prove that the following loop always terminates: while i % n != j % n: i += 1 j += 2 If we represent this as an equation over time, where t is the number of loops, we want to prove that for some t the following is true: (i + t) % n = (j + 2t) % n Solving for t: (i % n) + (t % n) = (j % n) + (2t % n) (i % n) - (j % n) = t % n (i - j) % n = t % n We can generalize for arbitrary speeds of the pointers. Let's say i moves at speed x and j moves at speed y: (i + x*t) % n = (j + y*t) % n (i % n) + (x*t) % n = (j % n) + (y*t % n) (i - j) % n = t*(y - x) % n This will always have a solution if (y-x) is coprime with n. A trivial case where it doesn't work, for example, is x=2, y=4, n=any even number. Imagine if i starts on an odd number and j starts on an even number. It's clear that i will always be odd and j will always be even. Note that y-x (2 in this case) shares a prime factor (not coprime) with all even numbers.
  - avodonosov 9y ago
    Thank you very much. I like the equation over time. Your explanation is difficult to follow when you do distributivity of % over +. I mean when you move from (i + t) % n = (j + 2t) % n to (i % n) + (t % n) = (j % n) + (2t % n) Here I read the '=' as normal number equality. A simplified example to demostrate that distributivity is not valid here: (5 + x) % 3 = 4 5 % 3 + x % 3 = 4 In the second line x=5 is a solution. But in the first line x is not a solution. It's better to express your explanation using "= (mod n)" from the beginning. (i + t) % n = (j + 2t) % n i + t = j + 2t (mod n)
  - tzs 9y ago
    Note that if you add the requirement that i and j start on the same node, then no matter what step size you use for x and y, as long as they are integers > 0 and x != y, then i and j will meet again if and only if there is a cycle. For particular values of x, y, and loop period there may be values of i and j such that going forward from those they never meet, but it is not possible to get into one of those positions if a past state had i == j. Proof: In the following I'll use your notation for the most part, except allowing for a "lead in" of length L from that common starting node to the start of the loop, so the nodes are numbered 0, 1, 2, ..., L-1, L, L+1, ..., L+n-1, with the nodes in the loop being {L, L+1, L+2, ..., L+n-1}. At time t, i has taken xt steps and j has taken yt steps. Let t >= L/x and t >= L/y, so that i and j are both past the lead in into the loop. Then i is xt-L steps into the loop, and j is yt-L into the loop. These will be at the same spot in the loop if xt-L = yt-L mod n, which happens whenever (x-y)t = 0 mod n. All multiples of n are solutions of this, so just pick any that are >= L/x and L/y, and you have a solution. If i and j do not start at the same place, all bets are off. That 0 is replaced with the differences between the starting node numbers, and as your example shows may not have a solution for some combinations of parameters.
- abalone 9y ago
  Intuitive explanation: Once the pointers enter the cycle the fast one will eventually approach the slow one from behind like runners on a stadium track. If it's one node behind the slow one, then they'll meet on the next move (slow advances one, fast advances two). And if the fast one is two nodes behind, on the next move it'll be one node behind.
- simonh 9y ago
  Off the top of my head, because if you don’t know where the last element points back to, and there’s an even chance it could be any previous element, the median element is the one on the middle. Two at a time means when you reach the last element and loop back. The lagging pointer will point to the middle element so. Across a population on lists, it will perform better that ratios that favour the lagging pointer being closer to ge back end of the list when the leading pointer loops. Also, with a 3 skip you could jump 2 ahead of the lagging pointer when you loop back behind and jump over it, which means when it advances it won’t catch you so they won’t meet.
jnwatson 9y ago
I recently received this as an interview question. This is one of those tricks once you know it, you'll remember it forever.
- pvg 9y ago
  Which makes it a fun thing to be aware of but a really terrible interview question. It's been kicking around forever as such, unfortunately.
xroche 9y ago
This is the tortoise and the hare (https://en.wikipedia.org/wiki/Cycle_detection https://en.wikipedia.org/wiki/Cycle_detection) Expecting a candidate to actually know this trick is however condoning the fact that the technical interview is just a matter of cheating and cramming.
- mhandley 9y ago
  Whether it is a good or a bad interview question depends on how you use it. I've used a variant of this when interviewing CS PhD candidates. I don't expect anyone to know how to solve this immediately. If anyone did, I'd assume they'd seen it before, and ask something else. What I want is to see how someone thinks about algorithmic problems. As they talk through what they're thinking, there are certain to be problems or limitations with their first suggestion. I'll probe on these, and see whether they understand those issues as they're pointed out. I'll give hints and see how they assimilate new ideas and information. In the end, 75% of candidates will get to a reasonable solution, and 25% will get to an optimal one, given some hints along the way. I'm much less interested in whether they get to the optimal one, or even in how fast they get there, than in what happens during the discussion along the path to a solution. You learn a lot about how someone thinks from that. It's also useful to learn how someone communicates - this is also an essential part of a PhD - there's a lot of back-and-forth goes on regarding possible research ideas, so seeing how someone communicates their ideas is useful. In summary, in an interview, such questions can be good as the basis of a dialog, but are useless unless the interviewer understands this is what they're actually trying to achieve.
  - sidlls 9y ago
    You're not getting any insight into the candidate's problem solving ability in general, though. You may be getting insight into how they think about a specific class of algorithmic problems, and possibly (although it's unlikely) algorithmic problems in general. What this interview question does is confirm your own biases regarding what "algorithmic thinking" is and little more.
    - 9y ago
greenleafjacob 9y ago
As others have said, this is actually a, perhaps the best, canonical example of a terrible interview question [1]. [1] https://news.ycombinator.com/item?id=7953725 https://news.ycombinator.com/item?id=7953725
- abalone 9y ago
  I mostly agree with this, however if the job requires a C.S. degree or equivalent and you assume all qualified candidates have been exposed to this, then perhaps it can be a useful question for testing how well you can explain a solution. Just look at how varied and complicated some of the explanations are for this out there. Some take mathematical approaches, others (me) try to boil it down to a few intuitive sentences... I can see it giving some insight into a candidate.
  - marcus_chang 9y ago
    Unless you're interviewing Dijkstra, it's a ridiculous question to ask. Anyone who's heard it before knows the answer instantly (I knew the answer before I even finished reading the description) and anyone unfamiliar with it will likely flail.
    - mort96 9y ago
      I’m not convinced anyone unfamiliar would likely fail. A pretty obvious solution is to just have a list of all nodes you’ve been to, and check if the current node is in that list. Not the most optimal solution, but one I’d imagine a lot of decent programmers would be able to come up with. Not saying it’s a good interview question, just that most good programmers shoukd be able to come up with some form of answer if they understand linked lists.
    - trhway 9y ago
      >Unless you're interviewing Dijkstra, it's a ridiculous question to ask. like many ridiculously looking interview questions, they are actually a filter. For this particular types of questions young people tend to quickly solve them. In 1987, in 9th grade, during one of the first computer classes, never before seeing or touching programming (previous years of school in a small town in USSR), I myself came up with Dijkstra algorithm in less than 10 minutes when we were assigned task of finding shortest path. I remember the teacher looking impressed :) These days i treat it more like a signal - if people asks such puzzles a lot then they either intentionally filtering or even don't understand that and seriously think it is important CS(cience).
linkpoint1 9y ago
A proof that the algorithm detects the existence of a cycle. If there is a cycle of length n then eventually both pointers get into the cycle. Since at each step the distance between the two pointers is increased by one module n then the distance becomes zero. Also the time to detect the loop is bounded by the time it takes both pointers to get into the loop plus the cycle length. Also this proof shows that the key ingredient is that the difference between the pointers must be coprime with n but still n steps are required to guarantee that the difference eventually becomes zero. So there is no advantage in choosing other values for the increment of the pointers except to achieve that the slowest get faster into the cycle.
- avodonosov 9y ago
  Thank you, super.
  - linkpoint1 9y ago
    if you program in Lisp the function list-length gives nil for circular lists. Ninety-nine problems contains similar problems with lists. I should have said that the difference between increments must be coprime with n to guarantee that the differece becomes 0 module n, that is both pointers get equal.
xamuel 9y ago
You didn't say the answer has to use O(1) space, so I'd just throw the nodes in a WeakSet, and when I reach a node that's already in the WeakSet, that's the start of the loop. Or better yet, use a WeakMap to associate nodes with their position, so that once I find the start of the loop I can immediately subtract to get the loop length, no second pass needed.
Retr0spectrum 9y ago
This algorithm can also be used for integer factorisation: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
- itissid 9y ago
  I always wonder if odd(and perhaps pointless) interview Q like this have been contorted from the original(much useful) problem like pollard's rho or it just happened to reduce to more useful ones. Digging deeper into such questions yields fun observations which may be the only useful thing that comes from questions like these. Like the length of the Longest Increasing Subsequence of a sequence A, has a fun fact to do with the Chromatic Number of a graph derived formed from a matching between A and sorted(A). Theoretical Math is beautiful and the answer to so many things.
simooooo 9y ago
"It is easy to see that they will eventually meet on the cycle. Once that happens, it is easy to count the cycle length." Is that so?
- microtherion 9y ago
  The second part of this confused me as well, because the algorithm only detects the existence of the cycle, not its length. However, once you know a node in the cycle (which this algorithm will provide), you simply go around the cycle once more and you have the length.
  - Spivak 9y ago
    More specifically you stop moving the hare and send the tortoise around again until it meets the hare counting your steps along the way.
AzzieElbab 9y ago
I was asked this exact question during an interview for a senior scala dev position and nearly walked out. I asked the guy to show me how one would go about implementing a cycle with prepend only api and of course did not get an answer or the job

avodonosov 9y ago

> It is easy to see that they will eventually meet on the cycle. Not easy for me, but thanks for the algorithm, maybe I will find time and energy to understand and believe. Why by two at a time and not by 3?

RomanPushkin 9y ago
3 will also work. People pick 2 intuitively, and it minimizes the overall runtime of the algorithm. (google "Proof of Floyd's Cycle Chasing" for details)
- tzs 9y ago
  Another advantage of 2 is that it works even if the two pointers do not start on the same element.
  - Spivak 9y ago
    It's not specifically 2, any two speeds that are coprime will have the same property.
    - tzs 9y ago
      Counterexample: loop of 8 nodes, numbered 0, 1, ..., 7. Start with one pointer at node 0, moving with speed 5. Start the second pointer at node 1, with speed 3 which is coprime to 5, the speed of the first pointer. The pointer positions at each step are: 0 5 2 7 4 1 6 3 repeat 1 4 7 2 5 0 3 6 repeat The condition we need in order to guarantee it works regardless of where the two pointers start is that the difference between the speeds is coprime to the cycle length.
gamegoblin 9y ago
Consider a cycle of length n. Consider two integers, i and j that have arbitrary initial values in [0, n). We want to prove that the following loop always terminates: while i % n != j % n: i += 1 j += 2 If we represent this as an equation over time, where t is the number of loops, we want to prove that for some t the following is true: (i + t) % n = (j + 2t) % n Solving for t: (i % n) + (t % n) = (j % n) + (2t % n) (i % n) - (j % n) = t % n (i - j) % n = t % n We can generalize for arbitrary speeds of the pointers. Let's say i moves at speed x and j moves at speed y: (i + x*t) % n = (j + y*t) % n (i % n) + (x*t) % n = (j % n) + (y*t % n) (i - j) % n = t*(y - x) % n This will always have a solution if (y-x) is coprime with n. A trivial case where it doesn't work, for example, is x=2, y=4, n=any even number. Imagine if i starts on an odd number and j starts on an even number. It's clear that i will always be odd and j will always be even. Note that y-x (2 in this case) shares a prime factor (not coprime) with all even numbers.
- avodonosov 9y ago
  Thank you very much. I like the equation over time. Your explanation is difficult to follow when you do distributivity of % over +. I mean when you move from (i + t) % n = (j + 2t) % n to (i % n) + (t % n) = (j % n) + (2t % n) Here I read the '=' as normal number equality. A simplified example to demostrate that distributivity is not valid here: (5 + x) % 3 = 4 5 % 3 + x % 3 = 4 In the second line x=5 is a solution. But in the first line x is not a solution. It's better to express your explanation using "= (mod n)" from the beginning. (i + t) % n = (j + 2t) % n i + t = j + 2t (mod n)
- tzs 9y ago
  Note that if you add the requirement that i and j start on the same node, then no matter what step size you use for x and y, as long as they are integers > 0 and x != y, then i and j will meet again if and only if there is a cycle. For particular values of x, y, and loop period there may be values of i and j such that going forward from those they never meet, but it is not possible to get into one of those positions if a past state had i == j. Proof: In the following I'll use your notation for the most part, except allowing for a "lead in" of length L from that common starting node to the start of the loop, so the nodes are numbered 0, 1, 2, ..., L-1, L, L+1, ..., L+n-1, with the nodes in the loop being {L, L+1, L+2, ..., L+n-1}. At time t, i has taken xt steps and j has taken yt steps. Let t >= L/x and t >= L/y, so that i and j are both past the lead in into the loop. Then i is xt-L steps into the loop, and j is yt-L into the loop. These will be at the same spot in the loop if xt-L = yt-L mod n, which happens whenever (x-y)t = 0 mod n. All multiples of n are solutions of this, so just pick any that are >= L/x and L/y, and you have a solution. If i and j do not start at the same place, all bets are off. That 0 is replaced with the differences between the starting node numbers, and as your example shows may not have a solution for some combinations of parameters.
abalone 9y ago
Intuitive explanation: Once the pointers enter the cycle the fast one will eventually approach the slow one from behind like runners on a stadium track. If it's one node behind the slow one, then they'll meet on the next move (slow advances one, fast advances two). And if the fast one is two nodes behind, on the next move it'll be one node behind.
simonh 9y ago
Off the top of my head, because if you don’t know where the last element points back to, and there’s an even chance it could be any previous element, the median element is the one on the middle. Two at a time means when you reach the last element and loop back. The lagging pointer will point to the middle element so. Across a population on lists, it will perform better that ratios that favour the lagging pointer being closer to ge back end of the list when the leading pointer loops. Also, with a 3 skip you could jump 2 ahead of the lagging pointer when you loop back behind and jump over it, which means when it advances it won’t catch you so they won’t meet.

jnwatson 9y ago

I recently received this as an interview question. This is one of those tricks once you know it, you'll remember it forever.

pvg 9y ago
Which makes it a fun thing to be aware of but a really terrible interview question. It's been kicking around forever as such, unfortunately.

xroche 9y ago

This is the tortoise and the hare (https://en.wikipedia.org/wiki/Cycle_detection https://en.wikipedia.org/wiki/Cycle_detection) Expecting a candidate to actually know this trick is however condoning the fact that the technical interview is just a matter of cheating and cramming.

mhandley 9y ago
Whether it is a good or a bad interview question depends on how you use it. I've used a variant of this when interviewing CS PhD candidates. I don't expect anyone to know how to solve this immediately. If anyone did, I'd assume they'd seen it before, and ask something else. What I want is to see how someone thinks about algorithmic problems. As they talk through what they're thinking, there are certain to be problems or limitations with their first suggestion. I'll probe on these, and see whether they understand those issues as they're pointed out. I'll give hints and see how they assimilate new ideas and information. In the end, 75% of candidates will get to a reasonable solution, and 25% will get to an optimal one, given some hints along the way. I'm much less interested in whether they get to the optimal one, or even in how fast they get there, than in what happens during the discussion along the path to a solution. You learn a lot about how someone thinks from that. It's also useful to learn how someone communicates - this is also an essential part of a PhD - there's a lot of back-and-forth goes on regarding possible research ideas, so seeing how someone communicates their ideas is useful. In summary, in an interview, such questions can be good as the basis of a dialog, but are useless unless the interviewer understands this is what they're actually trying to achieve.
- sidlls 9y ago
  You're not getting any insight into the candidate's problem solving ability in general, though. You may be getting insight into how they think about a specific class of algorithmic problems, and possibly (although it's unlikely) algorithmic problems in general. What this interview question does is confirm your own biases regarding what "algorithmic thinking" is and little more.
  - 9y ago

greenleafjacob 9y ago

As others have said, this is actually a, perhaps the best, canonical example of a terrible interview question [1]. [1] https://news.ycombinator.com/item?id=7953725 https://news.ycombinator.com/item?id=7953725

abalone 9y ago
I mostly agree with this, however if the job requires a C.S. degree or equivalent and you assume all qualified candidates have been exposed to this, then perhaps it can be a useful question for testing how well you can explain a solution. Just look at how varied and complicated some of the explanations are for this out there. Some take mathematical approaches, others (me) try to boil it down to a few intuitive sentences... I can see it giving some insight into a candidate.
- marcus_chang 9y ago
  Unless you're interviewing Dijkstra, it's a ridiculous question to ask. Anyone who's heard it before knows the answer instantly (I knew the answer before I even finished reading the description) and anyone unfamiliar with it will likely flail.
  - mort96 9y ago
    I’m not convinced anyone unfamiliar would likely fail. A pretty obvious solution is to just have a list of all nodes you’ve been to, and check if the current node is in that list. Not the most optimal solution, but one I’d imagine a lot of decent programmers would be able to come up with. Not saying it’s a good interview question, just that most good programmers shoukd be able to come up with some form of answer if they understand linked lists.
  - trhway 9y ago
    >Unless you're interviewing Dijkstra, it's a ridiculous question to ask. like many ridiculously looking interview questions, they are actually a filter. For this particular types of questions young people tend to quickly solve them. In 1987, in 9th grade, during one of the first computer classes, never before seeing or touching programming (previous years of school in a small town in USSR), I myself came up with Dijkstra algorithm in less than 10 minutes when we were assigned task of finding shortest path. I remember the teacher looking impressed :) These days i treat it more like a signal - if people asks such puzzles a lot then they either intentionally filtering or even don't understand that and seriously think it is important CS(cience).

linkpoint1 9y ago

A proof that the algorithm detects the existence of a cycle. If there is a cycle of length n then eventually both pointers get into the cycle. Since at each step the distance between the two pointers is increased by one module n then the distance becomes zero. Also the time to detect the loop is bounded by the time it takes both pointers to get into the loop plus the cycle length. Also this proof shows that the key ingredient is that the difference between the pointers must be coprime with n but still n steps are required to guarantee that the difference eventually becomes zero. So there is no advantage in choosing other values for the increment of the pointers except to achieve that the slowest get faster into the cycle.

avodonosov 9y ago
Thank you, super.
- linkpoint1 9y ago
  if you program in Lisp the function list-length gives nil for circular lists. Ninety-nine problems contains similar problems with lists. I should have said that the difference between increments must be coprime with n to guarantee that the differece becomes 0 module n, that is both pointers get equal.

xamuel 9y ago

You didn't say the answer has to use O(1) space, so I'd just throw the nodes in a WeakSet, and when I reach a node that's already in the WeakSet, that's the start of the loop. Or better yet, use a WeakMap to associate nodes with their position, so that once I find the start of the loop I can immediately subtract to get the loop length, no second pass needed.

Retr0spectrum 9y ago

This algorithm can also be used for integer factorisation: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm

itissid 9y ago
I always wonder if odd(and perhaps pointless) interview Q like this have been contorted from the original(much useful) problem like pollard's rho or it just happened to reduce to more useful ones. Digging deeper into such questions yields fun observations which may be the only useful thing that comes from questions like these. Like the length of the Longest Increasing Subsequence of a sequence A, has a fun fact to do with the Chromatic Number of a graph derived formed from a matching between A and sorted(A). Theoretical Math is beautiful and the answer to so many things.

simooooo 9y ago

"It is easy to see that they will eventually meet on the cycle. Once that happens, it is easy to count the cycle length." Is that so?

microtherion 9y ago
The second part of this confused me as well, because the algorithm only detects the existence of the cycle, not its length. However, once you know a node in the cycle (which this algorithm will provide), you simply go around the cycle once more and you have the length.
- Spivak 9y ago
  More specifically you stop moving the hare and send the tortoise around again until it meets the hare counting your steps along the way.

AzzieElbab 9y ago

I was asked this exact question during an interview for a senior scala dev position and nearly walked out. I asked the guy to show me how one would go about implementing a cycle with prepend only api and of course did not get an answer or the job