P-7.6 Timed Practice: Recursion, Sorting and First Dynamic Programming

What this is and why it exists

This is the third area, and the one where being honest about depth matters most.

A services screening asks whether you can recognise a repeated subproblem, remember an answer instead of recomputing it, and say which sort is stable. A product interview asks you to design the table order and argue the cost.

Both sit on the recursion, sorting and dynamic programming topics in the algorithms module, and neither is repeated here. This is that material against a clock, with the introductory half named as introductory rather than dressed up as the whole subject.

The vocabulary

• Repeated subproblem — the same call appearing many times in one recursion.
• Remembering answers — storing each result the first time it is computed.
• Table order — the sequence in which a table is filled.
• Stable sort — equal items keep their original relative order.
• In place sort — sorting without significant extra memory.
• Searching over an answer — halving the range of possible answers, with no array.

The mental model

Start by writing a plain recursion and noticing the repeated call. Remembering answers to calls you have already made is the whole of the first step. It usually turns exponential work into linear work with about three added lines. The part that needs practice is recognising the repeat, not the storing.

Rewriting the same solution as a table is what an interviewer usually asks for next. The difficulty there is the order, not the arithmetic. Write the fill order down before filling anything in — an order that never needs a value it has not computed yet. That is the working method, and skipping it is why table versions go wrong.

Sorting facts come up as short questions. Know which sorts are stable and which are in place, and when either matters. Stability decides whether sorting by one field and then another gives the result you intended. It is a favourite question precisely because it separates people who have used sorting from people who have only read about it.

Then the reframing worth one deliberate practice question. When a question asks for the smallest value that works, the answers themselves are the sorted range to search. No array is involved. This turns several hard-looking questions into about ten lines, and it is missed under time unless you have met it once on purpose.

Finish with a full timed set mixing all three areas. Mixed sets are harder than single-area ones. Recognising the shape is now part of the work, rather than given to you by the section heading. The honest weak list at the end is what makes the next session worth sitting.

What you should now be able to explain or do

Write a recursion, spot the repeated subproblem, and remember its answers. Rewrite it as a table and choose a fill order before filling anything. Say which sorts are stable and in place, and when each property decides correctness. Recognise a question that should be searched over its answer. Work a mixed timed set and write an honest weak list.

Check yourself