Coding interviews
using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;
var a = new Node(7); var b = new Node(7); var c = new Node(9); a.Next = b; b.Next = c; c.Next = b;
Console.WriteLine("entry:" + (Entry(a)?.Value.ToString(CultureInfo.InvariantCulture) ?? "none"));
Console.WriteLine("acyclic:" + (Entry(new Node(7) { Next = new Node(7) }) is null).ToString().ToLowerInvariant());
Console.WriteLine("empty:" + (Entry(null) is null).ToString().ToLowerInvariant());
static Node? Entry(Node? head) {
Node? slow = head, fast = head;
while (fast?.Next is not null) {
slow = slow!.Next; fast = fast.Next.Next;
if (ReferenceEquals(slow, fast)) { Node? cursor = head; while (!ReferenceEquals(cursor, slow)) { cursor = cursor!.Next; slow = slow!.Next; } return cursor; }
}
return null;
}
sealed class Node(int value) { public int Value { get; } = value; public Node? Next { get; set; } }
Reveal answer and reasoning
The output lines, in order, are “entry:7”; “acyclic:true”; “empty:true”. The first node leads to a second seven and then nine, whose Next returns to that second node. Slow advances once and fast twice until they meet. Moving one cursor from the head and the meeting cursor one link at a time finds the shared entry. A separate two-node list with equal values remains acyclic, and null input returns null.
Once a meeting exists, the distance from the head to the entry and the meeting offset around the cycle align modulo the cycle length. Advancing both cursors one step preserves that alignment until they meet at the entry. Explain the distance relation rather than treating the reset-to-head step as a memorized trick.
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. 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.
What a strong answer covers
- Exact output: entry:7 | acyclic:true | empty:true
- The first node leads to a second seven and then nine, whose Next returns to that second node.
- Overriding value equality on a node type can make == or an ordinary equality-based set unsuitable for identity detection.
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.