Micro-questions over the fast & slow pointers pattern. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The idea
1. Give the hallway analogy.
Answer
One person walks normally, another runs twice as fast. If there is a loop, the faster person eventually catches the slower one; if there is not, the faster person reaches the end first.
2. State the pattern.
Answer
Walk two pointers through a structure at different speeds — one step versus two steps.
3. What is it formally called?
Answer
Floyd’s Tortoise and Hare algorithm.
4. What is lapping?
Answer
The fast pointer overtaking the slow one inside the cycle — the faster runner lapping the slower on a circular track.
B. Cycle detection
5. Write the loop.
Answer
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False6. Why is the guard while fast and fast.next?
Answer
The fast pointer takes two steps, so both the current node and its successor must exist before moving. Checking only fast crashes on the last node.
7. Why must they meet if a cycle exists?
Answer
Once both are inside the cycle, the gap between them shrinks by exactly one node every step, so it must eventually hit zero.
8. Trace 1→3→5→7→9→5.
Answer
slow: 1, 3, 5, 7, 9, 5…; fast: 1, 5, 9, 7, 5… After 3 steps both are at node 5 — cycle detected.
C. Versus a hash set
9. What is the hash-set alternative?
Answer
Keep a set of visited nodes — if node in visited: return True. Simpler to reason about.
10. Why is the pointer version worth knowing anyway?
Answer
Same time with space instead of — which is the entire reason this pattern exists rather than always reaching for a set.
D. Beyond linked lists
11. What does the pattern generalise to?
Answer
Any sequence generated by repeatedly applying a function to a value — anywhere you can compute the next element deterministically.
12. How does happy number use it?
Answer
get_next is the sum of the squares of the digits. Run slow one step and fast two until they meet; the number is happy iff the meeting value is 1.
13. How does find-the-duplicate use it?
Answer
An array of length with values in — treat array values as implicit next pointers. A duplicate value means two indices point at the same place, which is a cycle.
14. How do you find the cycle’s entrance?
Answer
After the meeting, reset one pointer to the start and advance both one step at a time. They meet at the entrance.
15. Why does that work?
Answer
By the distance algebra of the meeting point: the distance from the head to the entrance equals the distance from the meeting point to the entrance, going around the cycle.
E. Trade-offs
16. What does the basic algorithm not tell you?
Answer
Where the cycle starts — only whether one exists. The entrance needs the extra phase above.
17. What is the precondition?
Answer
A well-defined, deterministic “next” function.
18. When is the hash set preferable?
Answer
For small inputs, or when memory is not a concern — it is clearer to reason about and easier to get right.
19. What are the costs?
Answer
time, space.
20. Summarise the pattern in one sentence.
Answer
Run two pointers at different speeds and let the faster one lap the slower — cycle detection in constant space, on anything with a next function.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Fast & Slow Pointers — the pattern
- Linked Lists — Question Bank
- Linked List Reversal — Question Bank
Software engineering
Infrastructure & security
Computer science
Hardware & engineering