"Count the number of ways to fill a rota" — what must your written plan name before you code?
answer
- counting, not optimising
- one sentence defining a single entry
- how a bigger entry is built from smaller
- dependencies must already be filled
- states times work per state
basics
~20 sA counting statement points at a table-filling plan, and that plan names four things: what one entry counts, how an entry is built from smaller ones, the base cases, and a fill order that computes dependencies first.
solid answer
~50 s"Number of ways" says the answer is a count of arrangements, so the transition **sums** contributions rather than taking a best value. Before coding I write four lines. The state: one full sentence saying what a single entry counts, naming every index it ranges over — for example, the number of valid ways to staff days `0..d` with day `d` assigned slot `s`. The transition: how that entry is built from smaller ones, here the sum over the previous day's compatible slots. The base cases: the smallest days, set directly. The order: increasing day index, so every entry a transition reads is already filled. Then I add the cost line — number of states times work per state, in time and space — and check the state cannot produce the same arrangement twice, because a double-counting state definition is the failure this plan is meant to catch.
code
pseudocode · 13 lines// state: ways[d][s] = number of valid ways to staff days 0..d
// with day d assigned slot s
for s in 0..S-1
ways[0][s] = 1 // base cases
for d in 1..D-1 // fill order: day increasing
for s in 0..S-1
ways[d][s] = 0
for p in 0..S-1 // transition: sum, not max
if compatible(p, s)
ways[d][s] = ways[d][s] + ways[d-1][p]
answer = 0
for s in 0..S-1
answer = answer + ways[D-1][s] // answer locationgo deeper
Be ready to recognise that "number of ways" means the answer is a count, so contributions are added rather than compared, and that the count starts from base cases you set directly.
Explain the four plan lines and derive them out loud: the state as a full sentence with its indices, the transition as a sum over compatible predecessors, the base cases, and a fill order that respects dependencies. Add the states-times-work cost.
Show the double-counting check as a deliberate step, and the retention decision — full table versus rolling layers — argued from the memory budget rather than habit. Say what you lose when you drop to rolling layers.
Own the call on when this formulation is worth its maintenance cost at all: a table nobody on the team can re-derive is a liability, and a simpler approach with a worse class can be the right long-lived choice under a known input bound.
## Reading the cue without skipping the plan A statement that asks for *the number of* valid arrangements, rather than the best one or whether one exists, is asking you to count. Counting problems over sequences of decisions are usually solved by defining a quantity over prefixes of the decision sequence and building it up. The cue is easy; the failure is what happens next. The weak answer is "that's dynamic programming, I'll memoise it" followed by immediate typing, and it fails because memoisation is a caching technique, not a formulation. Without a state definition there is nothing to cache. ## The four lines of the plan | Line | What it must say | Failure if skipped | |---|---|---| | State | What one entry counts, with every index named | Nothing to fill; recursion wanders | | Transition | How an entry is built from strictly smaller ones | Recurrence invented while coding | | Base cases | The smallest entries, set directly | Off-by-one at the boundary | | Order | The sequence in which entries are filled | Reads uncomputed entries | **State.** Write it as a sentence, not a symbol: *ways[d][s] is the number of distinct valid ways to staff days 0 through d such that day d is assigned slot s.* Every index that appears on the left must be justified — the second index exists precisely because the compatibility rule looks back at yesterday's slot, so the count is not well defined without it. Dropping an index the transition needs is the single most common formulation bug, and it shows up as a recurrence you cannot write down. **Transition.** Because the answer is a count, contributions are added: an entry equals the sum of the previous day's entries whose slot is compatible with today's. If the statement had asked for the *cheapest* rota, the same state would take a minimum instead. Same state, different combining operator — which is why the plan writes the operator down rather than assuming it. **Base cases.** The first day has no predecessor, so each slot starts at one way. Getting this wrong by initialising to zero produces a total of zero and a long debugging session. **Order.** Increasing day index, and within a day any order, because an entry only reads the previous day. The rule generalises: fill so that every entry a transition reads has already been computed. If no such order exists, the dependencies are cyclic and the formulation, not the code, needs fixing. ## Cost, and the space line The cost is *number of states multiplied by the work done per state*. With D days and S slots and a compatibility check per predecessor, that is D·S states and up to S work each, so D·S² time and D·S space if the whole table is kept. The plan should then note that each entry reads only the previous day, so a rolling pair of layers reduces space to S — a change to the plan, not to the recurrence. Writing the cost line before coding is what lets you notice, while it is still cheap, that a state you defined is too large to hold. ## Double counting: the defect the plan exists to catch Counting is fragile in a way optimisation is not. If two different paths through the table can produce the same arrangement, the total is wrong, and the code will be perfectly correct with respect to a wrong formulation. The check is a sentence: *can one arrangement be generated by more than one sequence of decisions?* Fixing it usually means imposing an order on the decisions — decide days strictly left to right, or fix a canonical order among interchangeable choices — so that each arrangement corresponds to exactly one path. Do this check on the plan, not on the output, because output-level debugging of a double count on small inputs frequently looks correct. ## When the plan says stop Sometimes the honest plan reveals the formulation is unusable: the state needs to remember an arbitrary subset of what came before, so the number of states explodes, or the count exceeds any bound the statement permits and must be reported under a modulus. Both are conclusions you reach from the four lines in under a minute, and both are far cheaper to discover on paper than after twenty minutes of implementation.
- Your state lets two different decision sequences produce the same rota. What does that break?The total, silently. Counting requires a bijection between arrangements and paths through the table; if one arrangement is reachable twice, it is counted twice and the code is correct against a wrong formulation. The fix is at the plan level: impose a canonical decision order, or add the index that distinguishes the paths, so each arrangement is produced exactly once.
- The table is days by slots and the memory budget is tight. What changes in the plan, not the recurrence?Only the retention line. Each entry reads the previous day alone, so the plan keeps two layers instead of the full table and states that the answer is read from the final layer. The recurrence, the base cases and the fill order are untouched. Note in the plan that any later requirement to reconstruct an example rota would need the full table back.
- When does a counting cue not lead to a table you can fill?When the state must remember something unbounded — an arbitrary subset of prior choices rather than a fixed summary — so the number of states is not manageable, or when the dependencies are mutually recursive and no fill order exists. Both show up while writing the four lines, which is the point of writing them before coding rather than after.
saying these in an interview costs you the question
- Says it is dynamic programming and starts typing
- Never writes what one table entry counts
- Takes a maximum where the statement says count
- Fills in an order the dependencies forbid
- Counts the same arrangement under two decision orders
- Skips the states-times-work cost line