Two-speed detection or a visited set for a traversal job hung on a looping escalation chain?

## The situation A workflow engine stores an escalation chain as records, each holding the identifier of the next approver's record; the chain ends at a record with no successor. A bad edit repointed one record at an earlier one, and the nightly traversal job that walks each chain now hangs on that chain — burning a worker, emitting nothing. You need a detector in the job, and you have two candidates. ## Candidate A: the constant-space two-speed walk Two cursors over the chain, one advancing a record per step and one advancing two; a collision proves a loop, and a second phase (reset one cursor to the chain head, advance both singly) yields the **entry record** — the first record that is part of the loop. - Extra memory: **O(1)**, independent of chain length. - Record visits: the fast cursor covers twice the distance of the slow one, and the second phase adds another pass over the tail, so expect **on the order of two to three times as many hops** as a single pass. - What you learn: a yes/no answer and the entry record. Nothing about the records you passed on the way. ## Candidate B: remember what you have seen Walk once, inserting each record's identity into a set (or a map from identity to the position at which you first saw it). The first identity already present is a repeat — and, in a chain where every record has exactly one successor, that first repeat **is** the entry record. - Extra memory: **O(n)** in the chain length, plus the per-entry overhead of the structure. - Record visits: exactly one per record. - What you learn: the loop, the entry, *and* the full ordered path you walked — which records led in, which are on the loop, and in what order. ## The comparison that matters | | Two-speed walk | Remembered path | |---|---|---| | Extra memory | O(1) | O(n) in chain length | | Record hops | ~2-3x a single pass | 1x | | Yields the entry | Yes (second phase) | Yes (first repeat) | | Yields the whole path | No | Yes | | Tolerates a mutating chain | Poorly (two passes over a moving target) | Poorly, but detects in one pass | ## How to decide, out loud **Ask how big a chain can get.** If a chain can be millions of records and the job runs on a memory-capped worker alongside other work, `O(n)` per chain is the thing that takes the box down, and the constant-space walk is the default. If chains are bounded at a few hundred approvers by the product itself — and escalation chains usually are — the memory argument is theoretical and should not drive the design. **Ask what a hop costs.** If following a link means a remote fetch rather than a dereference, hop count dominates everything. Two to three times as many hops is two to three times the round trips and the load on the store, and the remembered path already caches every record you fetched. This is the case where the asymptotically thriftier algorithm is the wrong call, and being able to say why is the point of the question. **Ask what the incident needs.** "There is a loop" closes nothing. Whoever repairs the data wants the offending records: the path in, the members of the loop, and ideally the record whose successor link was edited — which is the record *inside the loop whose successor is the entry*. The two-speed walk can get there too (walk the loop from the entry until you find the record pointing back at it), but the remembered path hands you the whole picture from one pass, already in memory. **Ask whether the chain holds still.** Neither technique is sound against concurrent edits; both assume a stable successor for the duration. The two-speed walk is the more fragile of the two because it reads the same records repeatedly and its correctness argument assumes those reads agree. If you cannot snapshot or freeze writes, that is a bigger problem than either algorithm and you should say so rather than pick a detector. ## A defensible answer Ship the constant-space walk in the *scanning* job that touches every chain in the system, because that is where unbounded memory bites and where you only need a yes/no plus an entry record. Then, for the small number of chains it flags, run the remembered-path walk once per flagged chain to produce the full incident record. You pay `O(n)` memory only on the handful of chains that are actually broken, and you get the diagnostics where they matter. Cap the remembered path with a maximum size so a pathological chain degrades to an alert rather than an out-of-memory failure. ## What a weak answer sounds like "Always the two-pointer version, it's O(1) space." That is a reflex, not a decision: it ignores hop cost, ignores what the operator needs to see, and ignores that a bounded chain makes the memory difference irrelevant. The mirror-image error — "just use a set, lookups are O(1)" — confuses lookup *time* with the *space* the set occupies, which is exactly the resource under pressure.