What does a one-pass gap-pointer walk to the kth-from-last node buy over counting the length first?
answer
- count the sweeps, not the big-O
- both versions are linear
- a fixed gap between two references
- what if the walk cannot be repeated
- similar constants, not a different class
basics
~20 sNot asymptotic speed — both are O(n) and both perform roughly 2n advances. One pass buys a single sweep from the head, which matters when re-walking is expensive or the cursor cannot be restarted. Counting first is usually the clearer code.
solid answer
~50 sThe gap technique advances a leading reference k nodes, then moves leader and trailer together until the leader falls off the end; the gap is invariant, so the trailer lands k from the end. Compared with counting the length and then walking `n - k` links, the complexity class is identical — O(n) time, O(1) space — and the total advances are about the same, roughly 2n either way. What changes is the number of sweeps from the head. That matters when a second traversal is genuinely costly or impossible: a forward-only cursor that cannot be reset, a chain being mutated under you, an adapter that fetches pages on demand. It does not matter on an in-memory chain you can walk freely, where the two-loop version is easier to read and gets the `k` greater than length check for free from the count.
go deeper
Know the shape: move one reference k records ahead, then move both one at a time until the leader runs out, and the trailing reference is the answer.
State the invariant that makes it work — the two references stay exactly k apart — and explain why the trailer lands k from the end at the moment the leader falls off.
Argue the tradeoff in sweeps and constant factors rather than complexity classes, and say what your code does when k exceeds the record count.
Own the rule for when single-sweep discipline is worth its fragility: reserve it for sources that genuinely cannot be re-read, and default to the obvious two-loop version where a second walk is free.
### The setup You hold the head of a capture chain of packet records of unknown length and need the record k from the end — say the 50th-from-last record before a fault was logged. Two approaches are standard, and the interesting part of the question is not how to write either one but how to argue between them. **Count then walk.** Sweep once, counting records to get n. Sweep again from the head, following `n - k` links. Two loops, both obvious, and the count gives you a free validity check: if k exceeds n, say so and stop. **Gap pointers.** Advance a leading reference k links from the head. Then advance the leader and a trailing reference one link at a time until the leader falls off the end. Because the gap between them never changes, the trailer is exactly k records behind the leader at every moment, so when the leader is past the last record the trailer is on the kth from the end. ### The invariant, stated properly After initialisation the leader is k links ahead of the trailer. Every subsequent step advances both by one, which preserves the difference. Termination is when the leader has walked off the end, i.e. it has covered n links; the trailer has therefore covered `n - k`, which is the kth record counting the last as one. The invariant is the whole proof, and it is what you should say out loud rather than describing pointer motion. ### The cost comparison, done honestly This is where candidates overclaim. Count-then-walk performs n advances in the first loop and `n - k` in the second: up to 2n. The gap walk performs k advances to open the gap, then `n - k` more with two references moving each time: also about 2n. **Both are O(n) time and O(1) extra space, and the constant factors are close to equal.** The one-pass version is not asymptotically faster, and it does not halve the work. Saying it does is the single most common wrong answer here, and it is the kind of overclaim an interviewer will push on. The difference is the number of sweeps *from the head*, and that is only sometimes worth anything: - **When it is worth a lot.** The source cannot be restarted — a forward-only cursor, a chain handed to you by a callback that will not give you the head again. Or re-walking is expensive: the records are fetched or faulted in on demand, so a second pass pays real I/O for data the first pass already saw. Or the chain is being mutated concurrently and a second pass would see a different structure than the first, making n stale by the time you use it. - **When it is worth nothing.** An ordinary in-memory chain, small enough that both sweeps are trivial, and the surrounding code needs the length anyway. Here the two-loop version wins on readability: two loops with obvious termination beat one loop plus a gap invariant a reviewer must verify. ### The honest caveat about streams One pass does not mean *streamable*. The gap walk works because earlier records stay reachable — the trailer is reading nodes the leader already passed. If the source truly consumes records as they are read, and old records are gone, no pair of references can help; you need a ring buffer holding the last k records, at O(k) memory. Knowing that boundary is what separates a senior answer from a memorised template. ### The two edges that break implementations **k greater than the record count.** The leader runs off the end during the initial k advances, before the gap is even established. The code must detect that inside the initialisation loop and report *no such record* — not return the head, not fall through to the main loop, not read past the end. Count-then-walk gets this check for free, which is a genuine point in its favour. **The off-by-one in the gap.** Is k the number of records to skip, or a one-based position from the end? Advancing the leader k times and stopping when it becomes nothing puts the trailer on the kth record counting the last as one; advancing it `k + 1` times and stopping when the leader is on the last record puts the trailer one earlier. Both are defensible. Neither is discoverable by a caller from the signature. A single off-by-one here is the most common defect in this technique, and the fix is to write the contract down and test `k = 1` and `k = n` explicitly. ### What a strong answer sounds like State the invariant. Give both costs as O(n) with similar constants and refuse to claim a speedup that is not there. Then name the condition under which one pass actually pays — an unrepeatable or expensive traversal — and say that absent that condition you would write the two-loop version because it is easier to review and validates k for free. That is a judgment answer rather than a trick answer, and it is what the question is really testing.
- What should happen when k exceeds the number of records?It has to be detected during the initial k advances, before the gap exists: the leader runs off the end, and the code must report no such record rather than returning the head or reading past the end. The counting version gets this check for free, since it already knows the length — a real argument in its favour.
- Is k a number of records to skip, or a one-based position from the end?Write it into the contract. Advancing the leader k times and stopping when it becomes nothing leaves the trailer on the kth record counting the last as one; advancing k + 1 times leaves it one earlier. Both are defensible and neither is visible from the signature, so test k = 1 and k = n explicitly.
- When would you deliberately choose the two-loop version?When the chain is in memory, stable, walkable twice, and the surrounding code needs the length anyway. The second sweep costs a constant factor, the code reads as two obvious loops, the validity check on k comes for free, and there is no gap invariant for a reviewer to verify.
- Does the gap trick work on a source that discards records as they are read?No. It relies on earlier records staying reachable, because the trailer reads nodes the leader already passed. If the source genuinely consumes as it goes, you need a ring buffer holding the last k records — O(k) memory — and the two-reference version does not apply.
Two people walk a corridor of doors fifty apart. The moment the leader steps out of the far end, the follower is standing at the fiftieth door from the end — nobody had to count the doors.
saying these in an interview costs you the question
- Claims the one-pass version is asymptotically faster
- Says two traversals make the algorithm quadratic
- Ignores the case where k exceeds the record count
- Cannot state whether k counts the last node as one
- Assumes any chain can always be walked a second time
- Thinks two references make the walk work on a consume-once source