Checkpoint: midpoint mock round

Debrief: read your own results

What the different failure modes mean, and what to do about each.

Key idea

Four ways a timed round goes wrong

You did not know what to do. That is recognition, and the fix is the naming habit: thirty seconds at the start naming the pattern and why, before any code.

You knew what to do and could not write it. That is fluency in one specific technique, and the fix is that unit's lab rather than more problems.

You wrote it and it was wrong on an edge case. That is the pre-coding edge check from Unit 0, which almost everyone drops under time pressure. It costs thirty seconds and catches most of these.

You ran out of time while still exploring. That is time allocation. Decide on an approach by the one-third mark and commit, even to an imperfect one. A working brute force beats an unfinished optimum in every real interview.

Tip

What each problem was checking

The segment reversal wanted the four references named before rewiring, which is exactly what U7 said would decide the group-reversal problem.

The cousins problem needed both directions of information flow at once: depth from above and identity of the parent from above, with the answer assembled at the top.

The matrix flatten was a k-way merge, and noticing that column sortedness does not help beyond it is part of the answer.

The running medians was the two-heap arrangement, and the give-away was that the naive approach re-sorts on every arrival.

Why it works

Where you are

Half the course is behind you and it is the half that everything else stands on. Backtracking is U8's recursion with undo. Graphs are U8's traversals on a messier structure, with U9's heap for the weighted versions. Dynamic programming is recursion plus memory.

If U8 felt shaky, spend the time now rather than discovering it in U14. That is the single highest-value use of a day at this point in the course.

Keep the notes

Write down which of the four failure modes you hit and on which problem. That page is worth more than any individual solution, because the same mode will recur and you will recognize it faster.

Time allocation

Twenty minutes into a 45 minute problem you have a correct O(n squared) approach and a vague sense that an O(n log n) one exists. What is the best move?

Say the quadratic approach and its cost out loud, start writing it, and mention that a better bound probably existsKeep thinking about the faster approach, since a quadratic solution will not passWrite the quadratic one silently and only mention the faster idea if it finishes earlyAsk for a hint toward the faster approach before writing anything

Which units carry the second half?

Select every unit whose material the remaining units depend on directly.

Recursion and trees, since backtracking and memoized recursion are both built on itHeaps, since the weighted graph algorithms need a priority queueArrays and hashing, since visited sets and memo tables are hash structuresIntervals, since graph traversal is an interval problemBinary search, since every dynamic programming table is searched