Lab: make it fast and correct
Turn slow, naive code into efficient code by choosing the right structure — and prove it still works.
- Replace an O(n^2) approach with an O(n) one
- Use a set or dict to collapse a nested loop
- Keep correctness while improving speed
Optional lab. The advanced performance lessons said the biggest wins are algorithmic. Here you'll feel it and do it: take a naive approach, see it crawl, then make it fast with the right structure — graded on correctness, not luck.
Feel the cost of O(n²)
This finds whether any two numbers sum to a target, the naive way — a loop inside a loop. Run it and watch the time grow with the input:
That's O(n²): double the input, quadruple the work. There's an O(n) way using a
set — for each number, ask "have I already seen target - n?"
Checkpoint 1 — the fast version
Write has_pair_summing to do it in a single pass with a set.
Write has_pair_summing(nums, target) returning True if any two distinct positions sum to target. Use a set for O(n) — one pass, no nested loop.
has_pair_summing([1, 2, 3, 9], 12) → TrueCheckpoint 2 — most common element
Counting "which appears most" naively re-scans the list per element (O(n²)). Do it in one pass with a dict of counts.
Write most_common(items) returning the element that appears most often. On a tie, return the one that reaches the top count first. Assume items is non-empty.
most_common([1, 1, 2, 1, 3]) → 1Done?
Both green? You replaced quadratic work with linear by reaching for a set and a dict — the data-structures and complexity lessons paying off in raw speed. Remember the order: make it work, make it right, then make it fast — and measure.