skip to content

In permutation generation with a used-marker array, what breaks if the marker is never cleared?

level: middleimportance: must knowfreq 65%

answer

  1. What must be true when a call returns?
  2. Two things changed on the way down
  3. The path shrinks back — does anything else?
  4. Sibling branches see a stale marker
  5. Every later branch finds everything taken

basics

~20 s

You get exactly one ordering — the first — and then the search silently dies. Each marker stays set after its first use, so every later branch finds every item taken and returns without emitting anything. No error, just missing output.

solid answer

~50 s

The marker array and the partial ordering are two halves of one piece of state, and both must be restored on the way back up. Descending, you set `used[i] = true` and append the item; returning, you must remove the item *and* clear `used[i]`. If you only shrink the path, the marker leaks into sibling branches: after the first complete ordering is emitted, every remaining candidate at every level looks unavailable, so each loop falls through and returns. For three distinct tracks you print one ordering instead of six. The failure mode is what makes this nasty in review — nothing throws, nothing loops forever, the run just under-reports. The invariant to state out loud is that on entry and on exit of a call, the marker set and the partial ordering describe exactly the same placed items.

code

pseudocode · 12 lines
pseudocode
build(path):
    if length(path) == n:
        output(path)
        return
    for i in 0..n-1:
        if used[i]:
            continue
        used[i] = true
        append(path, a[i])
        build(path)
        removeLast(path)
        // used[i] is never set back to false

go deeper

for a junior

Know that state changed on the way down must be changed back on the way up, and that the marker and the partial ordering are two separate changes. Be able to trace three items by hand and count how many results actually come out.

for a middle

Explain the invariant — markers and path describe the same placed items at entry and exit — and show why the broken version silently under-reports instead of failing loudly. Name the mirror bug too.

for a senior

Talk about how you catch this in real work: a test that asserts the result count, not just that the first result is plausible, plus the copy-instead-of-mutate formulation as the safer default when the search is small and the code is shared.

for a principal

Frame it as a state-ownership choice. Mutable shared state with manual undo is the fast option and the one that fails silently; deciding when a team pays a linear copy per node to make a whole class of bug impossible is the call you own.

## What the marker is for When you enumerate the play orders of `n` distinct tracks, the search fills positions one at a time and each position may take any track that is not already placed. "Not already placed" has to be represented somewhere. The usual representation is a parallel array of booleans, `used[0..n-1]`, where `used[i]` is true exactly when track `i` sits somewhere in the partial ordering you are currently building. That gives a two-part mutable state: the ordering being built, and the marker array. The **invariant** that makes the search correct is that these two always agree — on entry to a recursive call and on exit from it, the set of true markers is exactly the set of tracks in the path. Every mutation on the way down must have a matching undo on the way back up, or the invariant breaks for every sibling branch that runs afterwards. ## Tracing the bug Take three tracks A, B, C. The buggy version sets `used[i] = true`, appends, recurses, and then removes the last element but never clears the marker. - Position 0 takes A. Markers: A true. - Position 1 takes B. Markers: A, B true. - Position 2 takes C. Markers: all true. Length is 3, so **A B C is emitted**. - Return to position 2's loop: it has already tried every index, so it returns. - Return to position 1's loop: it continues to C, but C's marker is still true, so it skips. Loop ends, return. - Return to position 0's loop: it continues to B and then C, both still marked. Both skipped. Done. One output instead of six, no exception, no hang. The search terminated "successfully". This is why the bug survives a casual test with a single small input where someone only checks that the first result looks right. ## The symmetric failure The mirror-image mistake is clearing the marker but forgetting to shrink the ordering. Now the ordering grows monotonically while the markers come and go, the two fall out of sync, and the length test stops identifying complete orderings — you emit garbage, or nothing at all after the first result. Both bugs come from the same root cause: treating the descent as one action and the return as a partial undo. Whatever you changed, change all of it back. ## Why a marker at all A reasonable question is why the search does not just scan the partial ordering to check whether a track is already in it. Two reasons. First, cost. A marker lookup is constant time; a scan is linear in the current path length, which turns each level from `n` candidate checks into `n` times `k` work and adds a factor to the whole search — on a space that is already n! that is not where you want to spend. Second, and more subtly, correctness under repeats. If two tracks carry the same value, a membership-by-value scan cannot tell one twin from the other: it sees the value already present and wrongly refuses to place the second copy. The marker is indexed by *position in the candidate list*, not by value, so it distinguishes the twins correctly. Deduplication of identical items is a separate concern layered on top, and it needs the marker to be identity-based to work at all. ## The swap-based alternative There is a second classic formulation that carries no marker array: at depth `k`, swap the candidate at index `i` into slot `k`, recurse on `k+1`, then swap back. Availability is encoded in the array itself — everything from index `k` onward is still free. It uses no extra array and it is a genuinely different way to think about the state. It does not, however, remove the restore obligation. The swap-back *is* the undo, and forgetting it corrupts the candidate list for every sibling branch, with the same silent-wrong-output signature. It also gives up a property the marker version has for free: with a sorted candidate list, the marker version emits orderings in lexicographic order, while swapping scrambles that order. If the interviewer asks for sorted output, that is a real reason to prefer the marker. ## The copy-instead-of-mutate alternative A third option removes the problem by removing the mutation: pass a freshly built path and a freshly built availability set down to each child instead of mutating shared state. Now nothing needs undoing, and the code is much harder to get wrong. The price is a linear-size copy at every node, which multiplies the total work by a factor of `n`. On small inputs that is a fine trade for clarity; on a search you actually intend to run to n = 10, the mutate-and-restore version is what you write, and the invariant above is what you check. ## What to say in the interview State the invariant before you write the loop: markers and path agree, on entry and on exit. Then the undo block is not something you remember, it is something the invariant forces. When asked what the missing clear costs, do not say "it is slower" — say it under-reports silently, and give the count: one ordering instead of n!.

  • Why keep a separate marker instead of checking whether the item is already in the partial ordering?
    Cost and correctness. A marker check is constant time while a scan is linear in the path length, adding a whole factor to an already factorial search. More importantly, a membership test by value cannot distinguish two items that happen to be equal, so it would refuse to place a legitimate second copy. The marker is indexed by candidate position, so it does not have that confusion.
  • Does the swap-based formulation avoid the restore obligation?
    No. Swapping the chosen item into the current slot and swapping back on return is exactly the same undo, just encoded in the candidate list instead of a marker array. Skip the swap-back and every sibling branch sees a corrupted list, with the same silent-wrong-output signature. It also loses lexicographic output order, which the marker version preserves on sorted input.
  • What breaks if you clear the marker but forget to shrink the partial ordering?
    The mirror bug. The path keeps growing while markers come and go, so the two representations disagree about what has been placed. The length test no longer identifies a complete ordering, and after the first result you emit wrong output or none. Same root cause: an incomplete undo of a two-part state change.

saying these in an interview costs you the question

  • Says the missing clear only makes the search slower
  • Thinks restoring the path also restores the marker
  • Expects duplicate output rather than missing output
  • Assumes the bug raises an error rather than under-reporting
  • Believes swap-based generation needs no undo

context

resolving links…