3

Recently I attended an interview and came accross the following question which I am not able to figure out.

Question-1:

As per the proof which I read Tortoise moves 1 step and Hare moves 2 steps at a time. I understood this and they will meet at some point since Hare moves twice the speed of Tortoise. Can't they have any random values like 2 and 3 or 3 and 5 or 2 and 4. If so, will they ever figure out the cycle? What is the condition for choosing the Tortoise and Hare values? Can we choose any random values?

Question-2:

Is there any condition for Tortoise and Hare to enter into the loop? Suppose if Tortoise and Hare have following values say 2 and 4 resp. And the linked list is like 

            3   
          /   \
    1 -  2     4
          \   /
            5

If Tortoise enters in to loop at node 3 and Hare enters loop at node 2 then they both never meet each other inside the loop. So is there a condition for Tortoise and Hare to enter the loop?

Are there any confined values that should be choosen such that they meet each other?

Amarnath
  • 8,736
  • 10
  • 54
  • 81
  • Please explain in more detail what _"Should the Tortoise and Hare have values only 1 and 2. Can't they have any random values like 2 and 3 or 3 and 5 or 2 and 4."_ is supposed to mean. – Codor Feb 03 '16 at 07:50
  • @Codor Updated the question, point is "Can we choose any values for Tortoise and hare if so will they satisfy the condition for entering into the loop" – Amarnath Feb 03 '16 at 08:02

3 Answers3

3

RE Q1: the greatest common divisor of tortoise and hare speeds must not be a divisor (other than 1) of loop length. So e.g. if gcd(vTortoise, vHare)=2, it will detect loops of odd lengths, but may fail for loops of even length. Q2 relates to the cases where it fails.

RE Q2: to detect a loop when the above restriction does not hold, i.e. when loop length is evenly divisible by M = gcd(vTortoise, vHare), loop will not be detected if tortoise and hare enter the loop at positions with different modulo M from the beginning of the loop. So in the above example, M=2 and loop will be detected if both hare and tortoise enter at positions with equal modulo M, e.g. 0 and 2, 0 and 4, 2 and 4, 1 and 3, etc. But loop will not be detected (thus tortoise and hare will travel infinitely) if they enter the loop e.g. at positions 0 and 1, or 0 and and 3, 1 and 2, etc.

Serge Rogatch
  • 13,865
  • 7
  • 86
  • 158
2

Say tortoise start at point numbered T and take steps St and Hare start at H and take steps Sh.

The necessary and sufficient condition for them to meet is

|T - H| = k X gcd (St , Sh)

i.e. the difference in their starting position should be the multiple of gcd of their steps.

Shashwat Kumar
  • 5,159
  • 2
  • 30
  • 66
1

The movement rates for the two must be relatively prime, in order to catch cycles of any length. I think that's a sufficient condition.

Sneftel
  • 40,271
  • 12
  • 71
  • 104
  • What about the second question? Is there any condition for them to enter into the loop? – Amarnath Feb 03 '16 at 08:05
  • Yes, this somehow makes sense, but the relative primality is unrelated to the graph, which I understood to be part of the input. Is the graph part of the input or is it fixed? – Codor Feb 03 '16 at 08:05
  • @Codor It is the fixed input. The input shown above is fixed. – Amarnath Feb 03 '16 at 08:06
  • Tortoise and hare is one example of Floyd's cycle detection algorithm https://en.wikipedia.org/wiki/Cycle_detection – saurav Feb 03 '16 at 08:12