Pattern Practice Checkpoint
A review of this module. Skip it if you feel confident; the next module does not need it.
Fix the mistakes
The slips that cost marks in this module. Spot each one, then check the fix.
This checkpoint mixes hashing, two pointers, windows, prefix sums, binary search, backtracking and bits on shipping, billing and log data. Name the pattern first, then write its template.
Name the pattern before you write
Triage means sorting problems by their likely pattern before you write any code. You read the limits and wording, name a pattern, and only then choose a template.
A shipping, billing or logging story hides one of a few patterns. Say the pattern in one phrase first, then write only that template.
problems = [ ("two items that add up to a price", "hash map"), ("longest stretch with at most k faults", "sliding window"), ("smallest speed that finishes in time", "binary search on the answer"), ("print every valid code", "backtracking"),]for text, pattern in problems: print(f"{pattern:30} <- {text}")Example 1 · Hashing: two prices that meet a total
prices = [14, 3, 9, 20, 11]target = 23seen = {}for i, p in enumerate(prices): if target - p in seen: print(seen[target - p], i) break seen[p] = i0 2
What this code does
- The dictionary remembers each price and its position, so each new price needs one lookup.
- This is one pass: O(n) time and O(n) space.
Writing the pattern next to the statement forces a decision. If you cannot name one, go back to the limits and the brute force.
One short template for each pattern
A feasibility test is a function that answers yes or no for one candidate value, such as 'can everything ship in D days with capacity c?'. If it is monotonic, binary search finds the first yes.
Keep a small, tested template for each pattern. Binary search on the answer is the one most students forget: find the first value for which a yes or no test is true.
def first_true(lo, hi, ok): while lo < hi: mid = (lo + hi) // 2 if ok(mid): hi = mid else: lo = mid + 1 return lo
print(first_true(1, 100, lambda x: x * x >= 50))Example 2 · Binary search on the answer: capacity
weights = [4, 2, 7, 3, 5, 6]days = 3
def ok(cap): count, load = 1, 0 for w in weights: if load + w > cap: count += 1 load = 0 load += w return count <= days
lo, hi = max(weights), sum(weights)while lo < hi: mid = (lo + hi) // 2 if ok(mid): hi = mid else: lo = mid + 1print(lo)11
What this code does
- ok(cap) is monotonic: if a capacity works, every larger one works.
- About log of the total weight tests run, each costing one pass.
ok(mid) true means the answer is mid or smaller, so hi = mid. False means it is bigger, so lo = mid + 1. The loop ends with lo == hi.
Check before you submit
End every problem the same way: run the samples, then the borders, then a comparison with the brute force on small random cases.
def agree(fast, slow, cases): return all(fast(*case) == slow(*case) for case in cases)
cases = [([3, 1, 2],), ([5],), ([-1, -2],)]print(agree(max, lambda a: sorted(a)[-1], cases))Example 3 · Backtracking checked against itertools
from itertools import combinations
nums = [1, 2, 3, 4]results = []path = []
def build(start): if len(path) == 2: results.append(path[:]) return for j in range(start, len(nums)): path.append(nums[j]) build(j + 1) path.pop()
build(0)print(results)print(results == [list(c) for c in combinations(nums, 2)])[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] True
What this code does
- The recursion picks 2 of 4 values in increasing position, saving a copy of the path.
- Comparing with
combinationsis a quick brute-force check. In an interview, the hand-written version is what is expected.
Here max stands for the fast version and sorting for the slow one. In real use, one is your idea and the other is a brute force you trust.
Module quiz
Questions from the whole module. Your first answer is your score.
Problems
Graded easy to hard, using everything from this module.
Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.
Exercise 1· Easy
Using a set, print Yes if any two different positions of [8, 3, 5, 1] add up to 9, else No.
Yes
Exercise 2· Easy
Print the code that has no partner in [4, 9, 4, 7, 9] using XOR.
7
Exercise 3· Medium
Print the length of the longest part of "pwwkew" with no repeated character, using a window and the last position of each character.
3
Exercise 4· Medium
With sales [5, -2, 7, 3, -4, 6] answer the 1-based ranges (1, 4), (3, 6) and (2, 2) using prefix sums. Print one total per line.
13 12 -2
Exercise 5· Medium
Use first_true style binary search to find the smallest whole n between 1 and 1000 with n * n * n >= 1000. Print n.
10
Exercise 6· Hard
For [1, 0, 1, 1, 0, 1, 0, 1, 1] and k = 2 repairs, print the longest run of 1s after changing at most 2 zeros, using a sliding window.
7
Exercise 7· Hard
Generate every valid bracket code with 3 pairs by backtracking and print how many there are and the codes on one line separated by spaces.
5 ((())) (()()) (())() ()(()) ()()()
Exercise 8· Hard
Count the non-empty runs of [3, -3, 2, -2, 1, -1] whose total is 0, using prefix sums and a dictionary. Print the count.
6
Interview questions
Questions interviewers ask on this topic.
Finish up
Mark complete & continue
Next: Must-do problems: Pattern Practice