Drills
Four drills, four translations. For each: name the hot operation FIRST, then reach into the toolbox. Everything you need was built in units 1 through 9.
Drill 1. A form validator gets a list of usernames and must report the first one that appears twice (or None). The hot operation is "have I seen this before?", asked once per name. That question wants O(1) membership, and membership-without-values is exactly the set from lesson 6-3.
Code exercise · python
Drill 1, your turn: implement `first_repeated(words)`. Walk the list once with a `seen` set: return the first word already in the set, add each new word, and return None if the walk finishes clean. O(n) total.
Drill 2. An analytics page needs the k busiest pages from a raw visit log. Two hot operations, chained: "count per page" (the dict tally, lesson 6-3) and "largest k of the counts" (the heap's top-k, lesson 8-2).
This time use the shortcut Python ships: heapq.nlargest(k, items, key=...) runs the size-k heap pattern for you. Real solutions are usually such compositions: two structures, each doing the one thing it is best at.
Code exercise · python
Drill 2, your turn: implement `busiest_pages(visits, k)`. Tally visits into a dict, then return `heapq.nlargest(k, counts.items(), key=lambda item: item[1])`, the k (page, count) pairs with the biggest counts.
Drill 3. An editor needs undo AND redo. Undo takes back the most recent action, redo re-applies the most recently undone one. Both are "newest first": two stacks (lesson 5-1). Undo pops done onto undone. Redo pops undone back onto done. A brand-new action clears undone, because history has forked and the undone future no longer applies.
Code exercise · python
Drill 3, your turn: implement `undo_redo(actions)` with two stacks (plain lists). Process the action strings: "UNDO" moves the top of `done` to `undone` (if any), "REDO" moves it back (if any), anything else appends to `done` AND clears `undone`. Return `done`.
Drill 4. An API rate limiter must answer, for a stream of request timestamps: "has this client already made 3 requests in the last 60 seconds?" Hot operations, once per request: throw out timestamps older than 60 seconds (they expire from the oldest end) and record the new request (it arrives at the newest end). Evict-oldest plus append-newest is both ends of one line, and O(1) at both ends is the deque (5-2) — a sliding window (3-3) over time instead of over positions. In a real server this deque lives inside a dict keyed by API key (6-3): one more composition.
Code exercise · python
Drill 4, your turn: implement `rate_limit(times, limit, window)`. For each timestamp t (sorted, in seconds): first popleft every stored time ≤ t − window (expired), then if fewer than `limit` remain, append t and record "ok", else record "blocked" (and do NOT store t: blocked requests don't count against the client).
Quiz
Where this course hands off to Algorithms: which of these did we USE repeatedly but never look inside?
Problem
Final translation. A ride-share app must always dispatch the CLOSEST idle driver, with drivers constantly becoming idle (inserted) and dispatched (removed). Hot operations: insert a driver with a distance, extract the minimum distance. Which structure from this course is this?