Dictionaries

Before coding the exercises, make sure you are comfortable with the four core operations.

A dictionary literal looks like {key: value, key: value, ...}.

d = {"apple": 3, "banana": 1, "cherry": 5}
d["apple"]    # 3
d["banana"]   # 1

Task: Create a dictionary scores with three student names and their exam scores. Then print the score for one student.

You can add a new key or update an existing one with d[key] = value.

Task: Starting from an empty dict, add three entries one at a time. Then update one of them (increase the value by 10).

Verify that len(d) == 3 after adding, and that the updated value is correct.

• key in d — True if key exists
• d.get(key, default) — returns default instead of raising KeyError if key is missing

Task: Write a function safe_lookup(d, key) that returns the value if the key exists, or the string "not found" if it does not.

safe_lookup({"a": 1}, "a")   # 1
safe_lookup({"a": 1}, "b")   # "not found"

Write count_items(items) that takes a list and returns a dictionary where each key is an item and the value is how many times it appears.

Before you code:

• Loop over the list.
• For each item, if it is not yet in the dict, add it with count 1.
• If it already exists, increment its count.

count_items(["a", "b", "a", "c", "b", "a"])  # {"a": 3, "b": 2, "c": 1}
count_items([1, 2, 1, 1, 3])                 # {1: 3, 2: 1, 3: 1}
count_items([])                              # {}

Now apply count_items to text: split a string into words, then count each word.

Write word_count(text) that:

1. Splits text into words using text.split().
2. Counts how many times each word appears.
3. Returns the dictionary.

word_count("hello world hello")
# {"hello": 2, "world": 1}

word_count("apple orange apple banana orange")
# {"apple": 2, "orange": 2, "banana": 1}

word_count("")
# {}

Hint: This is count_items applied to text.split(). Can you implement it by reusing count_items?

Write most_frequent_word(text) that returns the word with the highest count. If there is a tie, return any one of the tied words.

most_frequent_word("the cat sat on the mat the")  # "the"
most_frequent_word("a b a b c a")                  # "a"

Before you code:

• Use word_count to get the frequency dictionary.
• Loop over the dictionary to find the key with the maximum value. (Or think: can you use max with a custom key argument?)

Write top_n_words(text, n) that returns a list of the n most frequent (word, count) tuples, sorted from highest to lowest count.

top_n_words("the cat sat on the mat the cat", 2)
# [("the", 3), ("cat", 2)]

Hint: Sort the word_count(text).items() by value in descending order, then take the first n.

Try it on a longer passage:

passage = "to be or not to be that is the question to be is to do"
top_n_words(passage, 5)

You used a dictionary to count words. Could you have used a list of [word, count] pairs instead? What would be the main drawback?

A. Lists can't store pairs — only single values

B. It would work identically with no drawback

C. Finding whether a word already exists would require scanning the entire list each time — much slower for large texts

D. Lists can't be sorted

Two words are anagrams of each other if they contain exactly the same letters (in possibly different order).

Examples:

• "listen" and "silent" are anagrams.
• "evil", "vile", "live", "veil" are all anagrams of each other.

Think about it: How could you represent a word so that all its anagrams map to the same key?

Write anagram_key(word) that returns the sorted string of a word's letters. This key will be the same for all anagrams.

anagram_key("listen")  # "eilnst"
anagram_key("silent")  # "eilnst"
anagram_key("evil")    # "eilv"
anagram_key("vile")    # "eilv"

Hint: sorted("abc") gives ["a","b","c"]. Use "".join(...) to get a string.

Write find_anagrams(text) that:

1. Splits text into words.
2. For each word, computes its anagram_key.
3. Groups words with the same key into a list.
4. Returns a dictionary: {key: [word1, word2, ...]}

find_anagrams("listen silent enlist inlets hello world")
# {
#   "eilnst": ["listen", "silent", "enlist", "inlets"],
#   "ehllo":  ["hello"],
#   "dlorw":  ["world"]
# }

find_anagrams("evil vile live veil")
# {"eilv": ["evil", "vile", "live", "veil"]}

You have anagram_key from Exercise 2.1. How would you group all words that share the same key?

find_anagrams returns every word, including words with no anagram partner. Write find_true_anagram_groups(text) that returns only the groups that contain more than one word.

find_true_anagram_groups("listen silent hello world live evil")
# {"eilnst": ["listen", "silent"], "eilv": ["live", "evil"]}
# ("hello" and "world" are excluded — no partners)

A dictionary is a natural fit for tracking totals per category:

{"food": 500, "rent": 1000, "travel": 150}

Keys are expense categories; values are running totals.

Write update_expenses(expense_list, expenses_dict) that:

• Takes a list of (category, amount) tuples and an existing dict.
• For each tuple, adds amount to the running total for category.
• Modifies expenses_dict in place (no return value needed).

expenses = {}
update_expenses([("food", 200), ("rent", 1000)], expenses)
update_expenses([("food", 300), ("travel", 150)], expenses)
# expenses == {"food": 500, "rent": 1000, "travel": 150}

Before you code:

• How do you handle a category that appears for the first time?
• How do you handle one that already exists?

Write print_expenses(expenses_dict) that prints each category and its total, one per line, in the format "category : amount".

print_expenses({"food": 500, "rent": 1000, "travel": 150})
# food : 500
# rent : 1000
# travel : 150

Write top_expense(expenses_dict) that returns the category with the highest total spend as a tuple (category, amount).

top_expense({"food": 500, "rent": 1000, "travel": 150})
# ("rent", 1000)

Write over_budget(expenses_dict, limits) that returns a dictionary containing only the categories where spending exceeds the budget limit.

• limits is a dict of {category: budget}.
• Return {category: (spent, limit)} for each over-budget category.

expenses = {"food": 500, "rent": 1000, "travel": 300}
limits   = {"food": 400, "rent": 1200, "travel": 200}
over_budget(expenses, limits)
# {"food": (500, 400), "travel": (300, 200)}
# ("rent" is under budget: 1000 <= 1200)

In the expense tracker, you used category names as dictionary keys. What would happen if you accidentally used expenses[category] = amount instead of expenses[category] += amount for a category that already exists?

A. Python would throw a KeyError

B. The new amount would be added to the old one automatically

C. The old total would be silently replaced — you'd lose all previous expenses in that category

D. Python would create a list of both amounts

Sometimes you need to look up a key by its value instead of the other way around. Inverting a dictionary swaps keys and values.

Write invert_dict(d) that returns a new dictionary with keys and values swapped. Assume all values in d are unique (otherwise some keys would be lost).

invert_dict({"a": 1, "b": 2, "c": 3})  # {1: "a", 2: "b", 3: "c"}
invert_dict({})                          # {}

Write group_by(items, key_func) that groups items from a list by the result of applying key_func to each item.

This is a generalisation of both find_anagrams and the expense grouping pattern.

group_by(["cat", "car", "bar", "bat"], lambda w: w[0])
# {"c": ["cat", "car"], "b": ["bar", "bat"]}

group_by([1, 2, 3, 4, 5, 6], lambda x: x % 2)
# {1: [1, 3, 5], 0: [2, 4, 6]}

find_anagrams is just group_by with anagram_key as the key function.

def find_anagrams_v2(text):
    return group_by(text.split(), anagram_key)

Verify it gives the same results as your original find_anagrams.

You've used dictionaries all chapter without asking the awkward question: d["banana"] is instant even if d holds a million keys. A list would have to check entries one by one. How does a dict jump straight to the right spot?

The answer is an idea you're about to invent: turn the key into a number, and use that number as a position.

Python exposes each character's numeric code: ord("a") is 97, and chr(97) goes back to "a".

Write letter_position(ch) returning the position of a lowercase letter in the alphabet — "a" → 0, "b" → 1, ... "z" → 25 — using ord (no lookup tables!).

One letter is easy. For a whole string, the simplest recipe: add up the character codes. That gives a big number; to turn it into a position, take the remainder when dividing by the number of slots available.

Write string_hash(s, n_buckets) = (sum of ord of every character) % n_buckets. The result is always a valid index between 0 and n_buckets - 1 — exactly what you need to pick a slot in a list of buckets.

string_hash("a", 10)       # 7  (97 % 10)
string_hash("banana", 10)  # deterministic: same input always gives same output
string_hash("listen", 10)  # 5  (655 % 10)

Run this before reading on:

string_hash("listen", 1000), string_hash("silent", 1000)

Both give 655. Of course — they're anagrams (Part 2 of this chapter!), so they contain the same letters, and addition doesn't care about order. Two different keys landing in the same bucket is called a collision, and a hash that collides for every anagram is a bad hash.

The fix: make position matter. Weight each character by where it sits:

hash(s) = sum of ord(s[i]) * (i + 1), mod n

Write string_hash_v2(s, n_buckets) using the weighted sum (hint: enumerate(s)), and confirm the anagram pair now separates.

string_hash_v2("listen", 1000)  # 292  (2292 % 1000)
string_hash_v2("silent", 1000)  # 299  (2299 % 1000)

You just invented how a dict works inside:

1. Hash the key to a bucket index — one arithmetic step, no searching.
2. Go directly to that bucket.
3. Collisions are unavoidable (infinitely many strings, finitely many buckets), so each bucket keeps a short list to check — a few items, not a million.

That's why d[key] costs the same whether the dict holds ten keys or ten million: this is what O(1) lookup means.

Now zoom out. A big website can't fit a billion users on one database server; it splits them across many. Which server holds user 12345? Same invention: hash the key. With numeric IDs the hash is just the remainder.

Write which_shard(user_id, n_servers) returning user_id % n_servers, then check the test's fairness experiment: hashing 10,000 users across 7 servers should load every server almost equally.

which_shard(12345, 10)  # 5
which_shard(12345, 7)   # 4

Think about it (no code): if you add an 8th server, % 7 becomes % 8 — which users are now on the wrong server? (Almost all of them! Real systems soften this with consistent hashing — worth a web search. Python dicts face the same event when they grow: they resize and re-hash every key.)

You built a hash function that converts a string to a number, then uses modulo to pick a bucket. What happens when two different keys hash to the same bucket (a collision)?

A. The second key silently replaces the first — data is lost

B. Python raises an error and refuses to insert

C. The bucket stores both key-value pairs, and lookup checks each one — O(1) on average if collisions are rare

D. The hash function automatically picks a different bucket

The group_by pattern is one of the most frequently recurring patterns in data processing: collect items into buckets based on a computed property.