Heaps and Tries 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 heaps, two-heap medians and tries. Read the clue in each problem first, then choose the structure and say its cost.
Best few of many: a heap
The clue is the k largest, the k smallest, the next urgent task, or merging sorted streams. Keep a heap of size k, or one front value per stream. Cost is O(n log k), not the O(n log n) of a full sort.
import heapq
sales = [120, 45, 300, 80, 210, 95]print(heapq.nlargest(3, sales))print(heapq.nsmallest(2, sales))Example 1 · Most frequent words
import heapqfrom collections import Counter
words = "red blue red green blue red yellow blue".split()counts = Counter(words)heap = [(-n, word) for word, n in counts.items()]heapq.heapify(heap)for _ in range(2): n, word = heapq.heappop(heap) print(word, -n)blue 3 red 3
What this code does
- Counts are negated so the biggest count comes out first, and equal counts come out in alphabetical order.
- Counting costs O(n). Each pop costs O(log m) for m different words.
For a max heap, store negated numbers. For tuples that may tie, put a counter before the item.
The middle of a stream: two heaps
The clue is a median that changes as values arrive. Keep the smaller half in a max-heap and the larger half in a min-heap, sizes equal or the lower one larger by one. The tops give the median.
import heapq
low, high = [], []for x in [5, 1, 9]: heapq.heappush(low, -x) heapq.heappush(high, -heapq.heappop(low)) if len(high) > len(low): heapq.heappush(low, -heapq.heappop(high))print(-low[0])Example 2 · Running median of response times
import heapq
low, high = [], []for x in [30, 10, 20, 40]: heapq.heappush(low, -x) heapq.heappush(high, -heapq.heappop(low)) if len(high) > len(low): heapq.heappush(low, -heapq.heappop(high)) print(-low[0] if len(low) > len(high) else (-low[0] + high[0]) / 2)30 20.0 20 25.0
What this code does
- After 1 value the median is 30. After 2 it is the average of 10 and 30. After 3 it is 20, and after 4 it is 25.0.
- Only the top of each heap is read, so reading is O(1).
Add costs O(log n) and reading the median costs O(1). The version with a sorted list costs O(n) per insert.
Words and prefixes: a trie
The clue is many questions about the start of words: does any word start with this, how many, list them. A trie answers each in O(L) for a prefix of length L. For exact words only, a set is enough.
root = {}for word in ["ten", "tea", "to"]: node = root for ch in word: node = node.setdefault(ch, {}) node["end"] = Trueprint(sorted(root["t"]))Example 3 · Count words by prefix
root = {}for word in ["tea", "ten", "to", "tea"]: node = root for ch in word: node = node.setdefault(ch, {"count": 0}) node["count"] += 1
def count_prefix(prefix): node = root for ch in prefix: if ch not in node: return 0 node = node[ch] return node["count"]
print(count_prefix("te"), count_prefix("to"), count_prefix("x"))3 1 0
What this code does
- The counter
countlives inside each node dictionary. Letters are keys, so the key "count" never clashes with a letter. - Duplicate words are counted every time they are inserted.
Search needs the end mark on the last node. A prefix check only needs the walk to succeed. For a fixed sorted list, bisect can find a block of words with a prefix.
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
Print the three smallest values of [14, 3, 9, 27, 1, 8].
[1, 3, 8]
Exercise 2· Easy
Use a heap of negated values to print the largest value of [17, 42, 8, 30].
42
Exercise 3· Easy
Print the 2nd largest value of [6, 1, 9, 4, 8] using a min-heap of size 2.
8
Exercise 4· Medium
Merge [1, 4, 7], [2, 5] and [3, 6, 9] with heapq.merge and print the result as a list.
[1, 2, 3, 4, 5, 6, 7, 9]
Exercise 5· Medium
Print the two most common words of a b a c b a d as word count lines, ties by the smaller word.
a 3 b 2
Exercise 6· Medium
Print the median after each value of [8, 2, 6, 4] using two heaps, one per line.
8 5.0 6 5.0
Exercise 7· Medium
Build a trie from ['code', 'cod', 'cot', 'dot'] using node objects and print True or False for the prefixes co, cob, do, one per line.
True False True
Exercise 8· Hard
Print the list of words with the prefix de in alphabetical order from ['deal', 'dear', 'debt', 'do', 'deer'] by building a trie and searching below the prefix node.
['deal', 'dear', 'debt', 'deer']
Interview questions
Questions interviewers ask on this topic.
Finish up
Mark complete & continue
Next: Must-do problems: Heaps and Tries