When will Floyd's cycle-finding algorithm fail?

2
votes

I get an interview question about the Floyd's cycle-finding algorithm :

When will Floyd's cycle-finding algorithm fail ?

I mean, is there rule for finding the step between the fast and slow pointers ?

2
c++algorithmfloyd-cycle-finding
Perhaps when it's badly implemented? - user529758
As described by the Wiki, when there is no cycle, it will fail to detect one (thats a giant duh, to be sure, but none the less important). - WhozCraig
@NPE Were the interview question posed as "Assuming there exists a cycle within a sequence, under what conditions could Floyd's algorithm fail to find it?" I would concur. The linked algorithm fails under the guise that eventually the rabbit runs out of real-estate and never accounts for no-cycle. Were you or I to implement it, we would consider that a success-by-null. if f(x) in the linked algorithm returns null when passed null, then it will not fail, but that artifact appears left out (or I didn't see it, quite possible). - WhozCraig

2 Answers

2
votes

Under reasonable assumptions, it won't fail. It will either find a cycle or conclude that there isn't one.

The only failure scenarios I can think of are along the following lines:

  • there's a bug in the implementation;
  • the structure that's being traversed gets modified while the algorithm is in progress.
1
votes

There may not be any possible failure situations for Floyd's cycle finding algorithm.

The only possible failure scenario occurs when it is computationally difficult to find the next node in a dynamically changing linked list.