Quiz
Warm-up from lesson 9-2: a loop over n items with a DICT lookup inside costs how much in total?
The interview classic
This unit is the bridge from Python fluency to the Data Structures course and to real coding interviews: three patterns, each a direct application of unit 9's cost model, that together crack a large share of easy and medium interview questions.
Two-sum: given a list of numbers and a target, return the indexes of the two numbers that add up to the target.
two_sum([2, 7, 11, 15], 9) # [0, 1] because 2 + 7 == 9
The obvious solution checks every pair with two nested loops, O(n²) as you learned in lesson 9-2. The fluent solution makes one pass with a dict: for each number, compute its complement target - n. If the complement was seen earlier, done. Otherwise record the number's index and move on.
Each step is one O(1) dict lookup plus one O(1) insert, so the whole thing is O(n). The pattern to memorize: trade memory (a dict of what you have seen) for speed (no rescanning).
Code exercise · python
Run this program. Follow the seen dict in your head as each number arrives: 2, then 7 whose complement 2 is already there.
Code exercise · python
Your turn. Write first_unique(text) returning the first character that appears exactly once, or "-" if none exists. Count first with Counter (lesson 6-1), then scan the string in order.
Code exercise · python
Your turn, a simpler cousin. has_pair_with_sum only answers True or False, so you do not need indexes, and a SET of seen values replaces the dict. Same one-pass complement idea: check target - n against seen, then add n.
Quiz
In two_sum, why store seen[n] = i AFTER checking the complement instead of before?