Time to consolidate. In this module you have built a hash table from scratch (05-01 and 05-02) and learned to squeeze dict and set with the professional patterns of 05-03: indexing, grouping, counting, inverting. This lesson introduces no new theory: it's six progressive exercises, all with a TaskFlow flavor, covering the uses you'll run into most often at work (and in technical interviews): detecting duplicates, grouping by derived key, searching by tags, caching expensive results, solving the classic two-sum and extending your own HashTable. Try to solve each one before peeking at the solution; the statement always hints at which structure to use — the skill you're training is seeing why.

1. Exercise 1: the first duplicate id (and what not using a hash costs)
2. Exercise 2: grouping anagram titles
3. Exercise 3: AND/OR tag search
4. Exercise 4: a project cost cache (memoization)
5. Exercise 5: two-sum over hour estimates
6. Exercise 6: extending the HashTable from 05-02
7. Common mistakes, solutions and module wrap-up

A bulk import has slipped repeated ids into TaskFlow. Write two versions of first_duplicate(ids), returning the first id that appears for the second time (or None): one without a hash table (only element-to-element comparisons, O(n²)) and one with a set of seen ids (O(n)). Then measure them with timeit (as in 01-02) for n = 1,000, 10,000 and 20,000 ids with the duplicate at the end (worst case). Note the improvement factor at each n: does it grow or stay flat? Why?

Editorial quality control: we want to detect task titles that are anagrams of each other (same letters, different order — typical of duplicates with reshuffled words, like "Plan web" and "Web plan"). Write group_anagrams(titles) returning the groups of anagram titles. The module's central hint: grouping is a matter of choosing the right canonical key — one that is identical for every member of the group and hashable. Ignore case and spaces.

Package the inverted index from 05-03 into a TagSearch class with three methods: index(task) (registers the task in the inverted index and in the id index), search_and(*tags) and search_or(*tags), which return titles sorted by id. Requirements: a nonexistent tag must not break anything (in AND it collapses the result to empty; in OR it simply contributes nothing), and tasks without a tags field must be indexable without error.

TaskFlow models composite projects: each project has its own hours and a list of subprojects (which can repeat and be shared across projects). The total cost is recursive (module 3): own hours + the sum of the subprojects' costs.

Write a direct recursive cost(name), with a global call counter. Then write cached_cost(name), which uses a dict as a cache (the memoization pattern): before computing, check whether the result is already there; after computing, store it. Compare the call counts of both for "p0". Both must return the same total.

An absolute classic, TaskFlow edition: you have pairs (id, estimated_hours) and a workday of 8 hours. Write full_day_pair(tasks, workday=8) returning the ids of two distinct tasks whose hours add up to exactly the workday, or None. Test data: [("T-01", 3), ("T-02", 7), ("T-03", 2), ("T-04", 5), ("T-05", 6)]. The obvious version compares every pair (O(n²)); the good one makes a single pass with a dict. Hint: when you look at a task of h hours, the exact question is "have I already seen one of workday - h hours?" — and answering "have I already seen...?" in O(1) is this module's specialty.

Two assignments on your own chaining table. (a) Add the method keys(), returning a list of all stored keys (walk the buckets; remember the LinkedList is iterable and each item is a [key, value] pair). (b) Check the automatic resizing experimentally: insert the pairs (i, str(i)) for i from 0 to 99 starting from capacity 8, and verify three things — that the final capacity is the expected one (compute it by hand first: at which insertions does 0.75 get exceeded?), that the final load factor sits below the threshold, and that after all the resizes no key has been lost (all 100 retrievable with get, and keys() complete).

Solution 1: first duplicate, with measurement

Results on a reference machine (yours will vary in absolute value, not in shape):

Commentary: the improvement factor grows with n — from ×277 to ×3,322 — and it had to: O(n²) versus O(n) means the advantage is proportional to n, not a constant. Doubling n (10,000 → 20,000) quadruples the quadratic version's time (1.86 → 7.55 s: ×4.05, the exact signature of the O(n²) you learned in 01-04) and merely doubles the set version's. With the million records of the 01-02 experiment, the quadratic version would need hours; the set, a fraction of a second. It's the same verdict as that experiment, but now you understand the full mechanism: every in seen is a bucket computation, not a walk.

Solution 2: anagrams by canonical key

Commentary: all the intelligence lives in anagram_key. Two titles are anagrams if and only if, after normalizing (lowercase, no spaces) and sorting their letters, they produce the same sequence: "least" and "steal" both become ('a','e','l','s','t'). That canonical form meets the two requirements of a good grouping key: it is identical for the whole group and it is hashable (a tuple of characters — a bare sorted list would fail with TypeError, exercise 1 of 05-03). The rest is the defaultdict(list) grouping pattern from 05-03, in O(n · k log k) with k = title length. Fine point: this is exactly the defect that made sum_hash bad in 05-02 (ignoring order), used here on purpose — when you want anagrams to match, an order-insensitive key is the right tool. The same property is a virtue or a defect depending on the contract you need.

Solution 3: AND/OR search

Commentary: the class gathers the loose pieces of 05-03 into an object whose indexes are always in sync — index touches both, honoring the maintenance rule we stated there. _ids centralizes the get(..., set()) defense: the unknown tag behaves as an empty set, which is neutral in OR (| with empty adds nothing) and annihilating in AND (& with empty gives empty) — exactly the requested semantics, without a single special-case if. Task 9, tagless, is indexed without error thanks to t.get("tags", []) and simply never shows up in searches. Each query costs O(sum of the sizes of the sets involved), independent of the total number of indexed tasks.

Solution 4: memoization with a dict

Commentary: same result (10,235 hours), but 2,047 calls versus 11. The direct version explodes because each project uses the next one twice: p0 triggers 2 computations of p1, 4 of p2... 1024 of p10 — total 2¹¹−1 = 2047, exponential growth. The cache defuses it: each project is computed exactly once (11 projects, 11 calls); repeated appearances resolve with an O(1) dict lookup. The pattern is called memoization and its recipe is always the same: is it in the cache? return it; compute; store; return. Non-negotiable requirement: the cache key must be hashable and identify the input completely (here the name suffices because the cost depends only on the project). This recursive-function-plus-cache duo will reappear with tree traversals (module 6) and graphs (module 7), where "never redo work already done" is the difference between the instantaneous and the intractable. Python ships it prepackaged as functools.lru_cache, which you can explore on your own: it is exactly this dict, as a decorator.

Solution 5: two-sum in one pass

Commentary: the O(n²) version would try all 10 pairs; this one makes a single pass with one O(1) lookup per task. The mental pivot is what matters: instead of asking "which pair adds up to 8?" (a question about pairs: quadratic), for each task we ask "does my exact complement already exist?" (a question about one key: the hash's specialty). The trace: T-01 (3 h) looks for 5 — not there — and registers itself; T-02 (7) looks for 1 — no; T-03 (2) looks for 6 — no; T-04 (5) looks for 3 — yes, it's T-01 → ('T-01', 'T-04'). Fine details: registering the task after looking prevents pairing it with itself (with a workday of 8, a 4-hour task can only match another 4-hour one, and so it does); and if several valid answers exist, it returns the first reachable one, with both of its members as early as possible. This complement trick solves a whole family of problems ("two elements with difference d?", "two tags that cover the filter?") and is probably the most-asked hash table exercise in interviews.

Solution 6: keys() and the resizing, audited

Commentary: (a) keys() walks the bucket array and, inside each one, the LinkedList (its __iter__ from module 2 yields each pair; we keep pair[0]). The O(n + capacity) cost has its nuance: with a very empty table, the capacity term dominates — visiting 256 buckets for 3 keys. That's why the real dict maintains extra structure to iterate only what's occupied. (b) The final capacity can be predicted by hand with the rule "after inserting, if n/capacity > 0.75, double": it is exceeded at n = 7 (7/8 = 0.875 → 16), n = 13 (→ 32), n = 25 (→ 64), n = 49 (→ 128) and n = 97 (→ 256). Five resizes, final capacity 256 and factor 0.39 — and the three checks come out True: each rehashing reinserted the pairs at the new capacity without losing any. Notice the elegance of the last line: get works after every key has changed buckets up to five times, because storing and looking up always share the same _index. Your table, built with the module 2 LinkedList, passes the same audit a dict would.

• Choosing unhashable grouping keys (exercise 2): sorted(text) returns a list — wrap it in tuple before using it as a key. It is the most repeated stumble in derived-key grouping.
• Caching functions that depend on more than the key says (exercise 4): if cost also depended on a mutable global rate, the cache would return stale results after changing it. The memoization key must capture the entire input — or the cache must be invalidated when the context changes.
• In two-sum, registering before looking (exercise 5): it allows a task to pair with itself (a 4-hour one "finding itself" to add up to 8). The look-then-register order is not style: it is correctness.
• Measuring with data that hides the worst case (exercise 1): with the duplicate at the beginning, both versions look instantaneous and the measurement teaches nothing. When comparing algorithms, build the input that forces the maximum work — as we did by placing it at the end.
• Forgetting the defensive copy when intersecting (exercise 3): starting the AND with result = self._ids(tags[0]) without copying and then using &=... mutates the index's set, corrupting it for future queries. set(...) first, operate after.
• The module's closing tip: keep the TagSearch and the memoization cache; both return in the module 8 projects, and the "have I seen it already?" pattern from exercise 1 is literally the visited set of the module 7 BFS.

End of module 5 — and of a debt we had been dragging since lesson 01-02. You no longer merely know that the dict is O(1): you know why (key → hash → bucket, on top of the array's direct access from 01-05), you know what threatens it (collisions, bad hash functions, a runaway load factor) and you know what defends it (chaining, a uniform hash, resizing) — to the point of having built and audited your own HashTable. In these exercises the hash proved its rank: it turned an O(n²) into O(n) twice (duplicates and two-sum), an exponential cost into linear (memoization), and gave TaskFlow a tag search and an anagram detector in a handful of lines. But don't forget the frontier we drew in 05-03: all this power answers questions about an exact key. Ask your index for "the tasks sorted by id" or "all those with priority between 1 and 3" and the hash goes mute — its keys are scattered on purpose, with no notion of neighborhood or order. Answering that requires a structure that keeps the keys hierarchically organized, where each step discards half of the space: trees, the protagonists of module 6. There, moreover, a pending promise from module 4 awaits us: finally opening the heapq black box and seeing the heap from the inside (06-07). See you among the trees.