A backtracking enumerator exhausts memory collecting every valid roster — what do you change?
answer
- Separate search cost from output cost
- Search state is only depth-sized
- Ask what the caller truly needs
- Hand out solutions instead of accumulating
- Count, aggregate, sample, or stream
basics
~20 sStop materialising the output. Every arrangement here is valid, so nothing can be cut from the search; the memory goes on the returned collection. Hand each solution to a consumer at the leaf, or fold it into a count or aggregate.
solid answer
~50 sFirst separate the two costs. The search itself runs in memory proportional to depth; the blow-up is the retained collection of solutions, which is exponential in the number of slots. So the fix is at the interface, not in the loop. Change the routine from "return every roster" to "call a consumer with each roster as it completes": at the leaf, hand out the current arrangement, let the caller score or persist it, and retain nothing. If the caller only needs a count, increment at the leaf and skip the copy; if it needs the best roster by some measure, score the live path and keep one snapshot. Streaming leaves total time unchanged — the same leaves are reached — while dropping retained memory from depth times solutions to depth. One contract detail matters: a streamed arrangement is valid only until the consumer returns.
go deeper
Take away the distinction: the search itself only needs memory proportional to the depth, while keeping every answer needs memory proportional to how many answers there are. Those are different costs.
Be able to describe the consumer-per-solution shape and what it changes: retained memory falls to depth-sized, total time is unchanged, and the handed-out arrangement is only valid during the call.
Diagnose first, then fix at the interface. Walk the ladder from count to aggregate to bounded sample to stream, and say which one the caller's real requirement sits on.
Own the requirement itself. An exponential result set is usually a sign the contract is wrong; negotiate the output shape, the early-stop signal and the lifetime rules before anyone tunes code.
## Diagnose before you optimise A backtracking routine that runs out of memory has two suspects, and confusing them wastes the interview. 1. **The search state.** One recursion frame per level plus one shared partial arrangement: `O(d)` for depth `d`. For a weekly roster that is a few dozen entries. This is essentially never the problem. 2. **The materialised output.** One retained snapshot per solution, each of length `d`. If the roster has, say, twelve slots with a handful of eligible workers each, the number of valid complete rosters is easily in the tens of millions, and `d x solutions` is the number that ends the process. So before touching anything, ask how many solutions the caller expects. If the answer is "all of them, and there are a lot", then no reorganisation of the search can help: the output alone does not fit, and any design that returns a fully built collection is dead on arrival. Note that this is true *by construction* here — every arrangement the enumerator produces is valid and wanted, so there is no such thing as a wasted branch to remove. The cost is the answer, not the search. ## The fix: invert the interface Replace "return a collection of all arrangements" with "invoke a consumer once per arrangement". At the base case, hand the current path to the consumer instead of recording it; when the consumer returns, un-choose and carry on. The routine now retains nothing beyond its `O(d)` search state, and the caller decides what is worth keeping — a score, a running maximum, a batch written to storage, the first `k` that satisfy something the caller cares about. The cost profile changes in exactly one dimension: | | Collect all | Stream to consumer | |---|---|---| | Time | nodes explored + `d` x solutions | nodes explored + consumer work x solutions | | Retained memory | `O(d x solutions)` | `O(d)` | | Caller can stop early | no | yes, if the consumer can signal stop | Total time is unchanged in order: the same leaves are reached, because nothing about the traversal changed. What you gained is that nothing accumulates, and — often the bigger win — the caller can abandon the enumeration once it has what it needs, which a collect-everything routine cannot offer since it only returns at the end. ## Pick the weakest output shape the caller can live with Streaming is one point on a ladder; walk it explicitly: - **A count.** Increment at the leaf. No copy, no consumer, constant retained memory. If the caller asked "how many valid rosters are there?", building any of them is pure waste. - **An aggregate.** Cheapest roster, most balanced roster, a histogram of hours per worker. Score the live path at the leaf and keep only the running result — one retained snapshot at most. - **A bounded sample.** The first `k`, or a random `k` by reservoir sampling over the stream. Retained memory `O(k x d)`, chosen by the caller rather than by the input. - **Everything, streamed.** Push each one out to storage or a downstream stage as it appears. - **Everything, retained.** Only defensible when the solution count is known small. Most "we need all of them" requirements are really one of the first three, and the conversation that establishes which is the actual senior contribution here. ## The contract detail that bites When you stream the live path, you are handing out a structure that the search will mutate the moment the consumer returns. That is fine and fast when the consumer reads it and computes — and a silent corruption bug when the consumer stashes it. Document the lifetime as part of the contract: *the arrangement is valid for the duration of the call; copy it if you keep it.* The alternative is to snapshot before every hand-out, which restores the per-solution `O(d)` copy for every consumer, including the ones that only needed to read. Handing out a read-only view is the middle ground when the language of the day supports one. ## What not to say Rewriting the recursion as an explicit stack does not help: it changes where the `O(d)` search state lives, not the size of the output. Neither does compressing the stored arrangements — that buys a constant factor against an exponential. And do not promise that the routine got faster: it did not, it got bounded, and bounded is what keeps the process alive.
- Does streaming instead of collecting make the enumeration asymptotically faster?No. The same decision tree is walked and the same leaves are reached, so total time stays proportional to nodes explored plus per-solution work. What changes is retained memory, from depth times solutions down to depth. The practical speedup, when there is one, comes from letting the consumer stop the enumeration early — an option a collect-everything routine cannot offer.
- What is the lifetime contract for a solution handed to a consumer?It is valid only until the consumer returns; the search then un-chooses and reuses the same structure. A consumer that retains it must copy. Say this in the interface, or hand out a read-only view. Snapshotting on the routine's side instead is safe but reintroduces a per-solution copy for every consumer, including those that merely read and discard.
- The team insists they need every roster persisted. What do you push back on?Ask what is done with them downstream. If they are scored and filtered, fold the scoring into the consumer and persist only survivors. If they are sampled, sample in the stream. If they genuinely must all be stored, the enumeration becomes a producer feeding storage in batches, with backpressure — and the honest conversation is whether an exponential result set is the right output at all.
- Would converting the recursion to an explicit stack solve the memory problem?No. It relocates the depth-proportional search state from the call stack to a structure you manage, which was never the part that overflowed. The exponential term is the retained output. Converting is worth doing when the depth itself is enormous and frames are the constraint — not when the collection of results is what fills memory.
saying these in an interview costs you the question
- Reaches for micro-optimisations inside the loop
- Converts recursion to an explicit stack to save output memory
- Assumes streaming makes the enumeration asymptotically faster
- Hands out the live path without stating its lifetime
- Never asks how many solutions the caller actually needs