Drills
Four drills, four translations. For each one, name the hot operation first, then reach into the toolbox, because everything needed was built in units 1 through 9.
Drill 1. A form validator receives 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 with no values attached, which is exactly the set from lesson 6-3.
Note what the problem does not need. It never asks how many times a name appeared, so a counting dict would carry information nobody reads.
first_repeated
One pass with a seen set.
def first_repeated(words): seen = set() for w in words: if w in seen: return w seen.add(w) return None print(first_repeated(["red", "blue", "green", "blue", "red"])) print(first_repeated(["a", "b", "c"]))
Output
blue None
The check has to come before the add, the same ordering rule as two_sum in lesson 6-3. Adding first would put every word in the set immediately, so every word would look repeated.
The answer is blue rather than red, and the distinction is the point of the word first. Blue repeats at index 3 while red repeats at index 4, so the earlier repetition wins, and returning on the first hit gets that for free.
A function with no explicit return already gives None, but writing return None states the no-duplicates case deliberately.
The whole thing is O(n) time and O(n) memory, against the O(n²) of comparing every pair, which is the set replacing an inner loop once again.
Drill 2. An analytics page needs the k busiest pages from a raw visit log.
Two hot operations chain together here. Counting per page is the dict tally from lesson 6-3, and taking the largest k of those counts is the heap's top-k from lesson 8-2.
Python ships a shortcut for the second half, heapq.nlargest(k, items, key=...), which runs the size-k heap pattern internally.
Real solutions are usually such compositions, two structures each doing the one thing it is best at. A single structure that both counted and ranked would be worse at both.
busiest_pages
A dict tally, then a heap selection.
import heapq def busiest_pages(visits, k): counts = {} for page in visits: counts[page] = counts.get(page, 0) + 1 return heapq.nlargest(k, counts.items(), key=lambda item: item[1]) visits = ["/home", "/dsa", "/home", "/learn", "/dsa", "/home", "/billing"] print(busiest_pages(visits, 2)) print(busiest_pages(visits, 1))
Output
[('/home', 3), ('/dsa', 2)] [('/home', 3)]
The tally line is counts[page] = counts.get(page, 0) + 1, identical to lesson 6-3's vote counter, with get's default handling the first sighting of each page.
counts.items() yields (page, count) pairs, and key=lambda item: item[1] ranks them by the count while keeping the page name attached to the answer. Without the key the pairs would sort by URL.
The costs are worth separating. The tally is O(n) over the raw log, and the selection is O(n log k) over the distinct pages.
Fully sorting the tally would be O(m log m) for m distinct pages, which is more work for the same top k, and that gap widens as the site grows while k stays at 10.
Drill 3. An editor needs undo and redo. Undo takes back the most recent action, and redo re-applies the most recently undone one.
Both are newest-first, so both are stacks, which means two stacks from lesson 5-1. Undo pops from done onto undone, and redo pops from undone back onto done.
The third rule is the one that carries the real logic. A brand-new action clears undone, because history has forked and the undone future no longer applies.
That is the same behavior as a browser's forward button dying the moment you navigate somewhere new, and it is a good example of a data-structure choice encoding a product rule.
undo_redo
Two plain lists used as stacks.
def undo_redo(actions): done = [] undone = [] for a in actions: if a == "UNDO": if done: undone.append(done.pop()) elif a == "REDO": if undone: done.append(undone.pop()) else: done.append(a) undone.clear() return done print(undo_redo(["type a", "type b", "UNDO", "type c"])) print(undo_redo(["type a", "UNDO", "UNDO", "REDO"]))
Output
['type a', 'type c'] ['type a']
Both moves are guarded, if done: before an undo pop and if undone: before a redo pop, so extra UNDOs against an empty stack do nothing instead of raising an error.
The undone.clear() on a new action is what implements the forked history. In case 1, typing c after undoing b discards b permanently, which is why the result holds a and c rather than offering b back.
Case 2 exercises every branch. Typing a, undoing it, undoing again with nothing left, then redoing brings a back, so the result is ['type a'].
Every operation here is O(1), and the two stacks together never hold more than the number of actions, which is what makes this cheap enough to run on every keystroke.
Drill 4. An API rate limiter must answer, for a stream of request timestamps, whether a client has already made 3 requests in the last 60 seconds.
Two hot operations run once per request. Timestamps older than 60 seconds get thrown out, and they expire from the oldest end, while the new request is recorded at the newest end.
Evict-oldest plus append-newest is both ends of one line, and O(1) at both ends is the deque from lesson 5-2.
Structurally this is the sliding window from lesson 3-3 with time as the axis instead of positions. The window's edges move by clock reading rather than by index, but items still enter once and leave once.
In a real server the deque lives inside a dict keyed by API key, which is one more composition of the kind drill 2 used.
rate_limit
Expire from the front, then decide.
from collections import deque def rate_limit(times, limit, window): recent = deque() verdicts = [] for t in times: while recent and recent[0] <= t - window: recent.popleft() if len(recent) < limit: recent.append(t) verdicts.append("ok") else: verdicts.append("blocked") return verdicts times = [0, 1, 2, 3, 61, 62, 63] for t, v in zip(times, rate_limit(times, 3, 60)): print(t, v)
Output
0 ok 1 ok 2 ok 3 blocked 61 ok 62 ok 63 ok
Timestamps arrive in increasing order, so the oldest stored time is always at the front, which is what makes the expiry a popleft loop rather than a scan.
A blocked request is deliberately not stored. Rejected attempts do not count against the client, so appending them would let a burst of blocked requests extend the penalty.
The t = 61 case shows the window sliding. Times 0 and 1 have expired since both are ≤ 1, while 2 has not, so one slot stays taken, which still leaves room within the limit of 3 and the verdict is ok.
Using a list here would reintroduce the pop(0) trap from lesson 2-3, and this code runs on every request a server takes, so an O(n) expiry would be the most-executed slow path in the system.
The tool used constantly but never opened up is sorted(), and the O(n log n) cost of sorting.
You called it in lessons 3-2, 6-3, and 8-2, and each time the cost was taken on faith with no account of how the sorting actually happens.
The Algorithms course opens that box. Merge sort and quicksort are the two designs worth knowing, and there is a proof that n log n is the floor for any comparison-based sort, which explains why no library ships something faster in the general case.
From there it builds directly on the structures you now own. BFS and DFS on graphs become shortest-path and scheduling algorithms, BST balancing gets its rotations, and dynamic programming works over the arrays from unit 2.
That is the honest division of labor between the two courses. This one was about where data lives, and the next is about what you do to it.
This is a min-heap, a priority queue keyed by distance.
Idle drivers go in with heappush and dispatch takes the closest with heappop, both O(log n), which is exactly the pairing named by the two hot operations.
Always take the smallest with ongoing inserts was a whole unit, and unit 8 is where that phrase was turned into a structure with O(log n) push and pop and an O(1) peek at the minimum.
The alternatives each fail on one of the two operations. A sorted list keeps the minimum handy but pays O(n) per insert, a dict finds a known driver instantly but has no notion of a minimum, and a queue serves by arrival time rather than distance.
Naming the hot operations first is what made the choice automatic, which is the habit this course was built to leave you with.