Lab: algorithm practice
Three guided problems — most-common word, pair sums, and anagram check — each asking you to pick the right data structure and apply the patterns you have learned.
- Apply the count pattern to find the most common word in a list
- Apply the dict-lookup pattern to find all pairs summing to a target
- Use counting to check whether two strings are anagrams
This is an optional lab. Work through it when you want to practise the patterns from the module on fresh problems before moving on. Each checkpoint has a "think first" prompt — spend at least thirty seconds with it before reading the starter code.
Three problems. Each has a think-first question, a starter function with a comment skeleton, and automated checks. The patterns are the same ones you have already seen — the challenge is recognising which one to reach for.
Checkpoint 1 — most common word
Think first. You have a list of words. You need the one that appears the most often. Which data structure lets you count cheaply? What do you do after building the count?
Write most_common(words) returning the word that appears most often in the list. If the list is empty, return None. Break ties by returning the first word that reaches the highest count.
most_common(["cat", "dog", "cat", "bird", "cat"]) → "cat"most_common([]) → NoneThe count pattern is O(n) — one pass to build the dict, one pass to find the maximum. Compare that to the brute-force approach: for each unique word, count its occurrences by scanning the whole list — O(n²).
Checkpoint 2 — all pairs summing to a target
Think first. You have a list of integers and a target. You want every pair
of indices (i, j) where i < j and nums[i] + nums[j] == target. The
brute-force nested loop works but is O(n²). Can a dict eliminate the inner scan?
Write pair_sums(nums, target) returning a list of (i, j) tuples where nums[i] + nums[j] == target and i < j. Each pair appears once, with the smaller index first.
pair_sums([2, 7, 4, 1, 3], 5) → [(0, 4), (2, 3)]pair_sums([1, 2, 3], 10) → []The seen dict stores value → list of indices so you can handle duplicate
values (multiple positions holding the same number). Each lookup is O(1), so
the whole function stays O(n) for inputs with few duplicates per value.
Checkpoint 3 — anagram check
Think first. Two strings are anagrams if they contain the same letters with the same frequencies — just in a different order. "listen" and "silent" are anagrams; "hello" and "world" are not. How can you use counting to check this without sorting?
Write is_anagram(a, b) returning True if a and b are anagrams of each other (same letters, same frequencies, case-sensitive), False otherwise.
is_anagram("listen", "silent") → Trueis_anagram("hello", "world") → FalseThe early-exit length check eliminates a large class of non-anagrams in O(1). Building each count dict is O(n). Comparing two dicts is O(k) where k is the number of distinct characters — at most O(n). Total: O(n). Sorting both strings would also work but at O(n log n).
Done?
Three green checkpoints. You have applied count, dict-lookup, and count-then-compare to real problems. The next module — Recursion and Search — introduces a completely different problem-solving shape: functions that call themselves.
Measuring speed
Use time.perf_counter() to time two duplicate-detection algorithms and watch O(n) vs O(n²) diverge on growing inputs.
Recursion concepts
Understand recursion as a function calling itself on a smaller sub-problem, and learn to identify the base case and recursive case that every correct recursive function needs.