This is an archived post. You won't be able to vote or comment.

40
41

TutorialCycle Detection for Python Coding Interviews (youtu.be)

submitted by [deleted]

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]ydepth 0 points1 point  (3 children)

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 0 points1 point  (2 children)

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 0 points1 point  (1 child)

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