Lab: optimize it
Replace quadratic work with the right structure, and cache results with a closure.
- Use a Set to make deduplication linear
- Implement memoization with a Map and a closure
- Keep correctness while cutting cost
Optional lab. Apply the performance lessons: find the quadratic cost, swap in the right structure, and cache repeated work. Graded on correctness.
Feel the cost
This dedupes an array the naive way — includes re-scans the result for every
element (O(n²)). Run it and note the time:
A Set gives O(1) membership, turning the whole thing linear.
Checkpoint 1 — fast dedupe
Write dedupe to remove duplicates while preserving first-seen order, using a
Set.
Write dedupe(arr) returning a new array with duplicates removed, keeping the first occurrence order. Use a Set for O(n).
dedupe([1,2,2,3,1]) → [1,2,3]The shortest correct answer is [...new Set(arr)] — Set already keeps insertion
order. Knowing why that's O(n) is the point.
Checkpoint 2 — memoize
Write memoize(fn): return a wrapped function that caches results so repeated
calls with the same argument don't recompute. Use a Map held in a closure.
Write memoize(fn) that returns a function with the same behaviour as fn, but caches results by argument (assume a single primitive argument). Repeated calls with the same argument must not re-run fn.
memoize(fn)(3) then (3) → fn runs onceThe Map lives in the closure (the closures lesson), so each memoized function
keeps its own private cache — caching trades memory for speed, exactly the
trade-off from the caching lesson.
Done?
Both green? You cut quadratic work to linear and added caching — the two highest- leverage performance moves, both grounded in choosing the right structure.