Debrief, and what to do from here

Which unit each problem came from, how to read your own result, and how to keep this from decaying.

Key idea

Round one

The circular stretch was Unit 16's running-value argument applied twice. A wrapping selection is exactly the complement of a non-wrapping one, so the best wrapping total is the overall total minus the smallest contiguous stretch, and the answer is the better of that and the ordinary non-wrapping best. The trap is an input where every value is negative: the smallest stretch is then the whole sequence, so the formula returns zero, and zero means selecting nothing, which the problem forbids. The fallback in that case is the ordinary best, which is the largest single value.

The connection pool was Unit 6's overlap question answered with Unit 9's structure. Requests arrive in start order, so the only thing worth tracking is the set of end times currently held, and the earliest of those is the only one that can be released next. That is a min-heap: pop while the smallest end time has already passed, then accept if what remains is under the limit. The wrinkle is that a rejected request must never be pushed, which means each decision changes what later requests see and rules out anything that classifies all the requests up front.

Key idea

Round two

Trading with a fee was Unit 15's state machine. Two states, holding and not holding, with the transitions between them, and the fee charged on exactly one of the two crossings. Charging it on both, or on neither because you meant to subtract it later, is the usual way to lose it. Which crossing you pick does not matter as long as you pick one and stay consistent.

The two-source count was a search rather than a table walk, which is the part that catches people. Because characters may be skipped in either source, the source positions do not advance in lockstep with the target the way they do in Interleaving String. A state has to say where in each source you may next look, how much of the target is left, and whether each source has been used at all, since that last part is the only thing that can enforce the at-least-one-from-each rule. Memoize on the whole tuple. Both source positions have to be in it for the same reason they do in Unit 15: two different sets of chosen indices are two different ways, even when they spell the same target.

That is the course

One hundred and fifty problems, in an order built so that each one arrived after the ideas it needed and never after a solution to it.

If anything outlasts the details, make it the three questions rather than any particular algorithm. What is this recomputing. What has to be remembered. Why is this choice safe.

Quick check· 5 min

The guard in the wrapping problem

The best wrapping total equals the overall total minus the smallest contiguous stretch. Why does that formula need a guard?

When every value is negative the smallest stretch is the whole sequence, so the formula returns zero, which corresponds to selecting nothingBecause the overall total can overflow on long sequencesBecause the complement of a wrapping selection is not contiguousNo guard is needed; the formula is correct on every input

Select all that apply· 5 min

What is worth continuing

Select the practices most likely to keep this skill from decaying over the next few months.

Running the spaced review queue for around twenty minutes a dayRebuilding one already-solved problem a week from nothing, explaining it aloudMock interviews with another personSolving as many new problems as possible, as fast as possibleRereading the solutions to problems you have already solved

That is the course

One hundred and fifty problems, in an order built so that each one arrived after the ideas it needed and never after a solution to it.

If anything outlasts the details, make it the three questions rather than any particular algorithm. What is this recomputing. What has to be remembered. Why is this choice safe.