PythonAdvanced~5h

Interview: Dynamic Programming

Recognition first, then the table

Plenty of people can recite the coin-change solution and still not see that a new problem is the same shape. This drills the two steps that actually decide it — whether a table applies at all, and what one cell means — and only then the transitions, the base rows and the single rolled row.

Start this project See the modules

Modules: 5
Drills: 12
Build steps: 6
Time: ~5h

Walk out able to

Take an unseen problem, say whether a table applies and why, define a state you can write a transition for, and compute any cell by hand.

What you drill

Recognise it

Table, greedy, divide and conquer, or none of them.

Design the state

What a cell means, how many there are, what that costs.

Fill it and read it

Transitions, base rows, fill order, where the answer sits.

Shrink it

Which rows it still reads, and which way to sweep.

The pitch

What you practise, and what you leave with

A memoised coin solver, a knapsack in a single row, and an edit script recovered by walking the table backwards.

You will practise

Table, greedy, or divide and conquer
State design, and counting the states
Transitions, base rows and fill order
Rolling a table down to one row

Afterwards you can

Decide whether a table applies, and say why
Define a state you can write a transition for
Compute any cell of a table by hand
Roll a table down to the rows it reads

Modules

5 modules, 27 items

Lessons explain one idea. Drills repeat it until it sticks. Build steps make something that exists afterwards.

1
Tell it from its costume
~42 min
Decide whether an unseen problem wants a table, a greedy rule, or neither.
- LessonThe step before the table6 min
- LessonAsk the two questions10 min
- DrillSort the problem by method14 min
- DrillBeat the greedy answer12 min
2
Design the state
~51 min
Say what one cell means, count how many there are, and price the table.
- LessonDecide what one cell means9 min
- LessonPrice a design before you build it7 min
- DrillPick a state you can extend13 min
- DrillCount the states11 min
- DrillPrice the table11 min
3
Write the transition
~1h
Compute any cell from the recurrence, fill in a legal order, and read the answer out.
- LessonWrite down the choice at one cell9 min
- LessonFour places a table goes wrong5 min
- DrillUnroll a recurrence by hand10 min
- DrillCompute one cell of the table16 min
- DrillGet the base row right12 min
- DrillFill it in a legal order12 min
- DrillFind the answer in the table13 min
4
Shrink the table
~39 min
Keep only the rows the transition still reads, and sweep them the right way.
- LessonKeep only the rows you read6 min
- LessonThe direction decides the problem8 min
- DrillSize the rolled table11 min
- DrillRead the sweep direction14 min
5
Under interview conditions
~1h
Write three of them against fixed input, then say the state out loud before coding.
- Build stepMemoise before you tabulate12 min
- Build stepTake the cache away and count8 min
- Build stepRoll a knapsack into one row12 min
- Build stepSweep it the other way8 min
- Build stepBuild four tables and check them10 min
- Build stepReconstruct the edit script12 min
- LessonSay the state before you code12 min