Coding interviews
Reveal answer and reasoning
The input is a singly linked node graph whose links remain unchanged while searching. A cycle means revisiting the same node object, not seeing the same integer value twice. Return the entry node or null for an acyclic or empty list. The sample deliberately gives two different nodes the value seven so a value-based shortcut would be visibly unsafe. Use names such as a, b and c for node identities while tracing, because two printed sevens cannot identify the entry.
A return type containing only the stored integer would be unable to express which equal-valued node participates in the loop. That limitation is independent of the detection algorithm chosen.
With an unchanged finite reachable structure, the algorithm uses O(n) pointer advances and O(1) auxiliary references. A visited-node set is a valid alternative with O(n) storage and often a simpler first explanation. Returning only Value loses identity information when several nodes share a value. The reachable structure can be described by a finite stem length and a cycle length. Each phase advances only a linear number of links in their sum.
The set-based alternative spends memory remembering identities but can reveal the repeated node directly, which may be a reasonable clarity tradeoff under a bounded input size.
What a strong answer covers
- The input is a singly linked node graph whose links remain unchanged while searching.
- Once a meeting exists, the distance from the head to the entry and the meeting offset around the cycle align modulo the cycle length.
- With an unchanged finite reachable structure, the algorithm uses O(n) pointer advances and O(1) auxiliary references.
Common pitfall
Overriding value equality on a node type can make == or an ordinary equality-based set unsuitable for identity detection. ReferenceEquals states the contract directly. Concurrent link mutation invalidates the usual proof, and this sample provides neither synchronization nor a snapshot of a shared list.
Follow-up questions
- Add a self-loop and a cycle whose entry is the head. Hint: test the returned object with ReferenceEquals rather than checking its Value. Keep a repeated-value acyclic fixture to catch accidental equality-based detection.
- Which assumption fails if another thread rewires Next during cycle detection?
Self-review
Choose what to revisit. These marks are your own assessment and are separate from lesson completion.