Learn the vocabulary of two differently paced pointers detecting a loop in a linked list using constant memory.
0 / 5 completed
1 / 5
At standup, a dev mentions using two pointers moving through a linked list at different speeds, one step at a time and two steps at a time, to detect whether the list loops back on itself, using only constant extra memory. What is this technique called?
Cycle detection, via Floyd's tortoise and hare technique, is exactly this: it uses two pointers moving through a linked list at different speeds, one step at a time and two steps at a time, and if the list contains a cycle, the faster pointer eventually laps the slower one and they meet, detecting the loop using only constant extra memory. A hash collision is an unrelated hash-table concept about two keys sharing a bucket. This two-speeds-meet-if-a-loop-exists approach is exactly why cycle detection can find a loop without needing to store every visited node in a separate set.
2 / 5
During a design review, the team uses Floyd's tortoise-and-hare technique to detect a cycle in a linked list, specifically because it needs only two pointers and no auxiliary storage, unlike tracking every visited node in a separate set. Which capability does this provide?
The tortoise-and-hare technique here provides cycle detection in constant extra memory, since only two pointers are needed regardless of how long the list is, instead of storing every visited node in a separate set whose memory grows with the list's length. Storing every visited node in a separate set uses memory proportional to the list's length just to detect whether a cycle exists. This two-pointers-only, constant-space behavior is exactly why the tortoise-and-hare technique is favored when memory is a concern.
3 / 5
In a code review, a dev notices a linked-list cycle-detection function stores every visited node in a separate hash set and checks each new node against that set, instead of using the constant-space tortoise-and-hare technique with two differently paced pointers. What does this represent?
This is a missed cycle-detection-algorithm opportunity, since the tortoise-and-hare technique would detect the same cycle using only two pointers instead of a hash set whose memory grows with the list's length. A cache eviction policy is an unrelated concept about discarded cache entries. This hash-set-based-cycle-detection pattern is exactly the kind of unnecessary memory use a reviewer flags once the list can grow arbitrarily long.
4 / 5
An incident report shows a service ran out of memory while checking an extremely long linked list for a cycle, because the cycle-detection function stored every visited node in a hash set whose memory grew with the list's length instead of using the constant-space tortoise-and-hare technique. What practice would prevent this?
Switching to the tortoise-and-hare cycle-detection technique uses only two pointers and constant extra memory regardless of how long the list grows. Continuing to store every visited node in a hash set regardless of how long the list grows or how much memory that consumes is exactly what caused the out-of-memory issue described in this incident. This constant-space technique is the standard fix once a linked list is confirmed capable of growing extremely long.
5 / 5
During a PR review, a teammate asks why the team uses the tortoise-and-hare technique instead of simply storing every visited node in a hash set to detect a cycle, given that the hash-set approach is simpler to reason about. What is the reasoning?
The tortoise-and-hare technique detects a cycle using only constant extra memory regardless of the list's length, while the hash-set approach is simpler to reason about but uses memory proportional to the list's length just to track every visited node. This is exactly why the tortoise-and-hare technique is preferred when memory efficiency matters, while a hash set remains an easier-to-understand alternative when memory is not a concern.