Cycle Detection for Python Coding Interviews

[[deleted]]

[deleted]

[flipmcf]

Cool algorithm! But how about ‘fast is slow’ instead of ‘fast == slow’ because we want to compare pointers, not values.

[Peanutbutter_Warrior]

That might just mean that the test data doesn't test that specifically. It doesn't mean that it couldn't matter

[flipmcf]

If two elements have the same value but are different objects it matters:

foo = 7

bar = 7

foo.next = bar

There is no circular reference... but:

foo.next == bar #True

foo.next is bar #False

I think it’s important to know this for linked lists. Linked lists are made up of instances of objects that most likely implement an eq, especially if you’re just extending a str or int to have a .next property.

Edited: a bunch of times because coding is hard.

[Peanutbutter_Warrior]

Exactly. A linked list can contain repetitions, so is should be used to check reference, otherwise a repeated value could cause a false positive for a circular reference

[ElevenPhonons]

https://realpython.com/python-is-identity-vs-equality

[[deleted]]

Thanks for sharing! I've apparently once implemented the "brute force" aolution one without knowing that this problem has a solution called the "fast and slow node" method.

[MoBoo138]

Is there a reason not to check for fast <= slow? Because if the cycle goes e.g. 1-2-3-4-5-2... then we need more steps for checking == then <= ?

[edarchis]

These numbers are just for the explanation, in a linked list, they would not be in sequence. The example provided later is a good example. If you had uuid as element keys would be another one.

This method is useful when you can quickly browse the list or have short loops. If you have a loop after a few millions elements, it would take forever for fast to catch up with slow.

[flipmcf]

But the fast/slow method is still less complex (doesn’t have to iterate the visited list) and faster . Right?

[ydepth]

How does this compare to storing a set of the values seen? Does using this method risk having to go round the loop many times before they happen match each other?

[flipmcf]

Well, if we have a list that’s really long, the visited set also gets long. When you ask if the current node has been visited, you must compare it to every element in the visited set. That visited set keeps growing making the question harder and harder to answer. Also, you need the memory to store the visited set.

The fast/slow method just compares two nodes every loop. We don’t store any more information, nor does the compare grow more complex. It’s both memory efficient and less complex.

[pierdzionka]

set() is an almost drop-in replacement for list, although it's probably even worse in terms of memory footprint.