Module 4: Hash Tables

6. Dict and Set — Usage Patterns in Backend

Lesson overview

In the previous lessons you built a hash table from scratch and understood collisions, chaining, open addressing and load factor. Now comes the part you'll use every single day as a backend developer: the usage patterns of dict and set that Python hands you as high-level abstractions over that very same structure.

Python's dict isn't "just a dictionary" — it's the backbone of all backend code. JSON responses are dicts. Parsed config files are dicts. Database rows turned into objects are, internally, dicts (__dict__). And a set isn't "a list without duplicates" — it's a hash table that gives you O(1) membership testing, O(n) set operations, and instant deduplication.

In this lesson you'll master the advanced patterns: defaultdict to auto-initialize, Counter to count frequencies, set operations to cross-reference data, and real backend patterns like in-memory caches, tracking processed IDs, inverted indexes and rate limiting. All with runnable code you can copy straight into your projects.

Dict as the backbone of Python backends

Before we get to the advanced patterns, let's see why dict is everywhere in backend:

import json

response = {"status": "success", "data": {"user_id": 42, "username": "mike_dev"}}
config = json.loads('{"database": {"host": "localhost", "port": 5432}}')
row_from_db = {"id": 1, "email": "user@example.com", "is_active": True}

print(response["data"]["username"])   # mike_dev
print(config["database"]["host"])     # localhost
print(list(row_from_db.keys()))       # ['id', 'email', 'is_active']

JSON responses, parsed configs, database rows — everything is a dict. Mastering its advanced patterns isn't optional, it's fundamental.

`dict.get()` vs `dict[key]` — avoiding KeyError

The most common mistake when starting out with dicts: accessing a key that doesn't exist.

user = {"name": "Ana", "role": "admin"}

print(user["name"])
# Output: Ana

try:
    print(user["email"])
except KeyError as e:
    print(f"KeyError: {e}")
# Output: KeyError: 'email'

The solution: `dict.get(key, default)`

user = {"name": "Ana", "role": "admin"}

email = user.get("email", "no-email@default.com")
print(email)
# Output: no-email@default.com

role = user.get("role", "viewer")
print(role)
# Output: admin

age = user.get("age")
print(age)
# Output: None

Without a second argument, .get() returns None instead of raising KeyError. Crucial in backend, where data can arrive incomplete (webhooks, API responses, user input).

`dict.setdefault()` — insert if missing

user_sessions = {}

user_sessions.setdefault("user_42", []).append("session_abc")
user_sessions.setdefault("user_42", []).append("session_def")
user_sessions.setdefault("user_99", []).append("session_xyz")

print(user_sessions)
# Output: {'user_42': ['session_abc', 'session_def'], 'user_99': ['session_xyz']}

setdefault(key, default) returns the existing value if the key is already there, or inserts default and returns it if not. It's atomic: check + insert in a single operation.

Dict comprehensions

You know list comprehensions from Module 1. Dicts have their own version:

words = ["hello", "world", "python", "backend", "api"]
word_lengths = {word: len(word) for word in words}

print(word_lengths)
# Output: {'hello': 5, 'world': 5, 'python': 6, 'backend': 7, 'api': 3}

Filtering with a condition

scores = {"ana": 85, "bob": 42, "carlos": 91, "diana": 67, "elena": 95}
passed = {name: score for name, score in scores.items() if score >= 70}

print(passed)
# Output: {'ana': 85, 'carlos': 91, 'elena': 95}

Inverting a dict

status_codes = {200: "OK", 404: "Not Found", 500: "Internal Server Error"}
name_to_code = {name: code for code, name in status_codes.items()}

print(name_to_code)
# Output: {'OK': 200, 'Not Found': 404, 'Internal Server Error': 500}

print(name_to_code["Not Found"])
# Output: 404

Transforming data from an API

api_users = [
    {"id": 1, "name": "Ana", "active": True},
    {"id": 2, "name": "Bob", "active": False},
    {"id": 3, "name": "Carlos", "active": True},
]

user_lookup = {u["id"]: u["name"] for u in api_users}
print(user_lookup)
# Output: {1: 'Ana', 2: 'Bob', 3: 'Carlos'}

active_lookup = {u["id"]: u["name"] for u in api_users if u["active"]}
print(active_lookup)
# Output: {1: 'Ana', 3: 'Carlos'}

`collections.defaultdict` — auto-initialize missing keys

setdefault works, but there's something better for repetitive patterns: defaultdict.

Counting with `defaultdict(int)`

from collections import defaultdict

words = ["api", "backend", "api", "database", "backend", "api", "cache"]

word_count = defaultdict(int)
for word in words:
    word_count[word] += 1

print(dict(word_count))
# Output: {'api': 3, 'backend': 2, 'database': 1, 'cache': 1}

When you access a key that doesn't exist in a defaultdict(int), it automatically creates the key with value 0 (the default from int()). So word_count["api"] += 1 works from the very first time, with no need to check whether the key exists.

Grouping with `defaultdict(list)`

from collections import defaultdict

logs = [
    {"level": "ERROR", "message": "Connection timeout"},
    {"level": "INFO", "message": "Server started"},
    {"level": "ERROR", "message": "Disk full"},
    {"level": "WARNING", "message": "High memory usage"},
    {"level": "INFO", "message": "Request processed"},
    {"level": "ERROR", "message": "Auth failed"},
]

logs_by_level = defaultdict(list)
for log in logs:
    logs_by_level[log["level"]].append(log["message"])

for level, messages in logs_by_level.items():
    print(f"{level}: {messages}")
# Output:
# ERROR: ['Connection timeout', 'Disk full', 'Auth failed']
# INFO: ['Server started', 'Request processed']
# WARNING: ['High memory usage']

You can also use defaultdict(set) to group without duplicates — each value gets added with .add() instead of .append().

When `defaultdict` vs `setdefault` vs `.get()`?

Pattern	Use	Example
Read with a fallback	`.get(key, default)`	`config.get("timeout", 30)`
Insert once if missing	`.setdefault(key, default)`	`cache.setdefault(url, fetch(url))`
Accumulate many values	`defaultdict(list/set/int)`	Counts, groupings, indexes

`collections.Counter` — frequency counting

Counter is a dict specialized for counting things. It's what you'd use instead of writing the manual loop with defaultdict(int):

from collections import Counter

words = ["api", "backend", "api", "database", "backend", "api", "cache"]
counter = Counter(words)

print(counter)
# Output: Counter({'api': 3, 'backend': 2, 'database': 1, 'cache': 1})

print(counter["api"])
# Output: 3

print(counter["nonexistent"])
# Output: 0  (it doesn't raise KeyError!)

`.most_common(n)` — the most frequent ones

from collections import Counter

log_levels = ["ERROR", "INFO", "INFO", "WARNING", "ERROR", "INFO",
              "ERROR", "ERROR", "INFO", "DEBUG", "INFO", "ERROR"]

counter = Counter(log_levels)
print(counter.most_common(3))
# Output: [('ERROR', 5), ('INFO', 5), ('WARNING', 1)]

print(counter.most_common(1)[0])
# Output: ('ERROR', 5)

Counter from strings

from collections import Counter

password = "aabbccddee"
char_freq = Counter(password)
print(char_freq)
# Output: Counter({'a': 2, 'b': 2, 'c': 2, 'd': 2, 'e': 2})

word = "mississippi"
print(Counter(word))
# Output: Counter({'s': 4, 'i': 4, 'p': 2, 'm': 1})

print(Counter(word).most_common(2))
# Output: [('s', 4), ('i', 4)]

Set — much more than "a list without duplicates"

A set in Python is a hash table that only stores keys (no values). That gives you:

O(1) membership testing: x in my_set is instant
Automatic deduplication: there can't be repeated elements
Set operations: union, intersection, difference in O(n)

Membership testing: O(1) vs O(n)

import time

data_list = list(range(1_000_000))
data_set = set(data_list)
target = 999_999

start = time.perf_counter()
for _ in range(1000):
    _ = target in data_list
list_time = (time.perf_counter() - start) * 1000

start = time.perf_counter()
for _ in range(1000):
    _ = target in data_set
set_time = (time.perf_counter() - start) * 1000

print(f"list: {list_time:.2f} ms | set: {set_time:.4f} ms | speedup: {list_time/set_time:.0f}x")
# Typical output: list: 8523.41 ms | set: 0.0400 ms | speedup: 213085x

The difference is enormous. With a million items, the set is ~200,000x faster.

Set operations

backend_devs = {"ana", "bob", "carlos", "diana"}
python_devs = {"bob", "carlos", "elena", "frank"}

print(backend_devs | python_devs)
# Output: {'ana', 'bob', 'carlos', 'diana', 'elena', 'frank'}

print(backend_devs & python_devs)
# Output: {'bob', 'carlos'}

print(backend_devs - python_devs)
# Output: {'ana', 'diana'}

print(backend_devs ^ python_devs)
# Output: {'ana', 'diana', 'elena', 'frank'}

Operation	Symbol	Method	Description
Union	`a \| b`	`a.union(b)`	Every element from both
Intersection	`a & b`	`a.intersection(b)`	Only the ones in both
Difference	`a - b`	`a.difference(b)`	The ones in `a` that aren't in `b`
Symmetric difference	`a ^ b`	`a.symmetric_difference(b)`	The ones in one but not in both

Set comprehensions

numbers = [1, 2, 2, 3, 3, 3, 4, 4, 5]
unique_squares = {x**2 for x in numbers}

print(unique_squares)
# Output: {1, 4, 9, 16, 25}

emails = ["Ana@test.com", "bob@test.com", "ANA@TEST.COM", "BOB@test.com"]
unique_emails = {e.lower() for e in emails}

print(unique_emails)
# Output: {'ana@test.com', 'bob@test.com'}

`frozenset` — immutable, hashable sets

A regular set can't be a dict key or an element of another set (because it's mutable). frozenset solves that:

permissions_a = frozenset({"read", "write"})
permissions_b = frozenset({"read"})

role_permissions = {
    permissions_a: "editor",
    permissions_b: "viewer",
    frozenset({"read", "write", "delete"}): "admin"
}

user_perms = frozenset({"read", "write"})
print(role_permissions[user_perms])
# Output: editor

frozenset supports every set operation (union, intersection, etc.) but doesn't allow add() or remove() — it's immutable.

Backend patterns with real code

Pattern 1: In-memory result cache

from typing import Any

class InMemoryCache:
    """Simple cache using a dict. O(1) get/set."""
    
    def __init__(self):
        self._store: dict[str, Any] = {}
        self._hits = 0
        self._misses = 0
    
    def get(self, key: str) -> Any | None:
        if key in self._store:
            self._hits += 1
            return self._store[key]
        self._misses += 1
        return None
    
    def set(self, key: str, value: Any) -> None:
        self._store[key] = value
    
    def delete(self, key: str) -> bool:
        if key in self._store:
            del self._store[key]
            return True
        return False
    
    def stats(self) -> dict:
        total = self._hits + self._misses
        hit_rate = (self._hits / total * 100) if total > 0 else 0
        return {
            "hits": self._hits,
            "misses": self._misses,
            "hit_rate": f"{hit_rate:.1f}%",
            "size": len(self._store)
        }


def expensive_db_query(user_id: int) -> dict:
    """Simulates an expensive database query."""
    return {"user_id": user_id, "name": f"User_{user_id}", "score": user_id * 10}


cache = InMemoryCache()

for user_id in [1, 2, 3, 1, 2, 1, 1, 4, 1]:
    cache_key = f"user:{user_id}"
    result = cache.get(cache_key)
    
    if result is None:
        result = expensive_db_query(user_id)
        cache.set(cache_key, result)

print(cache.stats())
# Output: {'hits': 5, 'misses': 4, 'hit_rate': '55.6%', 'size': 4}

Pattern 2: Tracking processed IDs (deduplication)

def process_data_pipeline(events: list[dict]) -> dict:
    """
    Processes events, deduplicating by ID.
    Set for an O(1) membership check.
    """
    processed_ids: set[str] = set()
    results = []
    duplicates = 0
    
    for event in events:
        event_id = event["id"]
        
        if event_id in processed_ids:
            duplicates += 1
            continue
        
        processed_ids.add(event_id)
        results.append({
            "id": event_id,
            "processed": True,
            "data": event["data"]
        })
    
    return {
        "processed": len(results),
        "duplicates": duplicates,
        "results": results
    }


events = [
    {"id": "evt_1", "data": "payment_received"},
    {"id": "evt_2", "data": "user_signup"},
    {"id": "evt_1", "data": "payment_received"},  # duplicate
    {"id": "evt_3", "data": "order_placed"},
    {"id": "evt_2", "data": "user_signup"},         # duplicate
    {"id": "evt_4", "data": "item_shipped"},
    {"id": "evt_1", "data": "payment_received"},    # duplicate
]

result = process_data_pipeline(events)
print(f"Processed: {result['processed']}, Duplicates: {result['duplicates']}")
# Output: Processed: 4, Duplicates: 3

Pattern 3: Inverted index with `defaultdict(list)`

from collections import defaultdict

def build_inverted_index(documents: dict[str, str]) -> dict[str, list[str]]:
    """
    Builds an inverted index: word → list of documents.
    Exactly how search engines work.
    """
    index = defaultdict(list)
    
    for doc_id, content in documents.items():
        words = set(content.lower().split())
        for word in words:
            cleaned = word.strip(".,;:!?")
            if cleaned:
                index[cleaned].append(doc_id)
    
    return dict(index)


def search(index: dict[str, list[str]], query: str) -> list[str]:
    """Finds documents containing ALL the words in the query."""
    words = query.lower().split()
    if not words:
        return []
    
    result_sets = [set(index.get(word, [])) for word in words]
    return sorted(set.intersection(*result_sets)) if result_sets else []


documents = {
    "doc1": "Python is a programming language for backend",
    "doc2": "FastAPI is a Python framework for APIs",
    "doc3": "Django is another Python framework for backend",
    "doc4": "JavaScript is used for frontend and backend",
}

index = build_inverted_index(documents)
print(f"'python' appears in: {index.get('python', [])}")
# Output: 'python' appears in: ['doc1', 'doc2', 'doc3']

print(f"'backend' appears in: {index.get('backend', [])}")
# Output: 'backend' appears in: ['doc1', 'doc3', 'doc4']

print(f"Search 'python backend': {search(index, 'python backend')}")
# Output: Search 'python backend': ['doc1', 'doc3']

print(f"Search 'framework python': {search(index, 'framework python')}")
# Output: Search 'framework python': ['doc2', 'doc3']

Pattern 4: Rate limiting with a dict

import time

class RateLimiter:
    """Rate limiter: at most N requests per time window. Dict maps IP → timestamps."""
    
    def __init__(self, max_requests: int, window_seconds: float):
        self.max_requests = max_requests
        self.window_seconds = window_seconds
        self._requests: dict[str, list[float]] = {}
    
    def is_allowed(self, client_ip: str) -> bool:
        now = time.time()
        if client_ip not in self._requests:
            self._requests[client_ip] = []
        self._requests[client_ip] = [
            ts for ts in self._requests[client_ip] if now - ts < self.window_seconds
        ]
        if len(self._requests[client_ip]) >= self.max_requests:
            return False
        self._requests[client_ip].append(now)
        return True


limiter = RateLimiter(max_requests=3, window_seconds=10.0)
for i in range(5):
    allowed = limiter.is_allowed("192.168.1.1")
    print(f"Request {i+1}: {'✓' if allowed else '✗'}")
# Output:
# Request 1: ✓
# Request 2: ✓
# Request 3: ✓
# Request 4: ✗
# Request 5: ✗

Pattern 5: Merging data from multiple sources

db_data = {"id": 1, "name": "Ana", "email": "ana@db.com"}
cache_data = {"id": 1, "last_login": "2025-01-15", "email": "ana@updated.com"}
auth_data = {"id": 1, "roles": ["admin"], "token_expires": "2025-02-15"}

user = {}
for source in [db_data, cache_data, auth_data]:
    user.update(source)

print(user)
# Output: {'id': 1, 'name': 'Ana', 'email': 'ana@updated.com',
#          'last_login': '2025-01-15', 'roles': ['admin'], 'token_expires': '2025-02-15'}

dict.update() does a shallow merge — later sources overwrite fields from earlier ones. For nested dicts (like configs), you'd need a recursive deep merge.

`collections.OrderedDict` — when order matters

Since Python 3.7+, regular dicts keep insertion order. So why does OrderedDict still exist?

`move_to_end()` and `popitem()` — the basis of LRU caches

from collections import OrderedDict

class SimpleLRU:
    """LRU Cache using OrderedDict. O(1) for every operation."""
    
    def __init__(self, capacity: int):
        self.capacity = capacity
        self._cache = OrderedDict()
    
    def get(self, key: str):
        if key not in self._cache:
            return None
        self._cache.move_to_end(key)
        return self._cache[key]
    
    def put(self, key: str, value) -> None:
        if key in self._cache:
            self._cache.move_to_end(key)
        self._cache[key] = value
        if len(self._cache) > self.capacity:
            self._cache.popitem(last=False)
    
    def __repr__(self):
        return f"LRU({list(self._cache.keys())})"


lru = SimpleLRU(capacity=3)
for k, v in [("a",1), ("b",2), ("c",3)]:
    lru.put(k, v)
print(lru)           # LRU(['a', 'b', 'c'])

lru.put("d", 4)
print(lru)           # LRU(['b', 'c', 'd'])  — 'a' was evicted

lru.get("b")
lru.put("e", 5)
print(lru)           # LRU(['d', 'b', 'e'])  — 'c' was evicted

What you implemented with linked lists in Module 2 you now see abstracted away inside OrderedDict — dict + linked list in O(1).

When to use `OrderedDict` vs a regular `dict`?

Use a regular dict for almost everything (Python 3.7+ keeps order). Use OrderedDict only when you need move_to_end(), popitem(last=False), or to compare dicts taking order into account (OrderedDict == compares order, dict == doesn't).

Performance: when should you convert a list to a set?

Building a set from a list costs O(n). Each lookup in the set is O(1) vs O(n) in the list. So:

A single lookup: not worth converting (O(n) for the conversion > O(n) for one linear scan)
2-3+ lookups: the conversion pays for itself

import time

data = list(range(100_000))
data_set = set(data)
target = 99_999

start = time.perf_counter()
for _ in range(100):
    _ = target in data
list_time = (time.perf_counter() - start) * 1000

start = time.perf_counter()
temp_set = set(data)
for _ in range(100):
    _ = target in temp_set
set_time = (time.perf_counter() - start) * 1000

print(f"100 lookups → list: {list_time:.2f} ms | set (incl. conversion): {set_time:.2f} ms")
# Typical output: 100 lookups → list: 852.34 ms | set (incl. conversion): 5.33 ms

Practical rule: If you're going to do more than 2-3 lookups over the same collection, convert it to a set.

Exercises

Exercise 1: Word frequency counter with Counter (Basic)

Implement analyze_text(text) that takes a string and returns a dict with: the 5 most frequent words, the total word count, and the total number of unique words. Use Counter.

text = """
Python is a programming language. Python is used for backend.
Python is popular for APIs. The backend with Python is efficient.
APIs in Python are fast. Python dominates the backend.
"""

result = analyze_text(text)
# It should return something like:
# {
#     "top_5": [("python", 6), ("is", 4), ("backend", 3), ...],
#     "total_words": X,
#     "unique_words": Y
# }

See solution

from collections import Counter
import re

def analyze_text(text: str) -> dict:
    words = re.findall(r'[a-záéíóúñü]+', text.lower())
    counter = Counter(words)
    
    return {
        "top_5": counter.most_common(5),
        "total_words": len(words),
        "unique_words": len(counter)
    }


text = """
Python is a programming language. Python is used for backend.
Python is popular for APIs. The backend with Python is efficient.
APIs in Python are fast. Python dominates the backend.
"""

result = analyze_text(text)
print(f"Top 5: {result['top_5']}")
print(f"Total words: {result['total_words']}")
print(f"Unique words: {result['unique_words']}")
# Output:
# Top 5: [('python', 6), ('is', 4), ('backend', 3), ('for', 2), ('apis', 2)]
# Total words: 30
# Unique words: 17

assert result["top_5"][0][0] == "python"
assert result["top_5"][0][1] == 6
assert result["unique_words"] <= result["total_words"]
print("✓ analyze_text works correctly")

Explanation: re.findall pulls out letters only (accents included), Counter does the counting automatically, and most_common(5) returns the 5 most frequent. In production you'd use something like this for content analytics.

Exercise 2: Cache with TTL (Intermediate)

Implement TTLCache — a cache where each entry expires after a given time (Time To Live). Use a dict to store values and timestamps.

cache = TTLCache(default_ttl=5.0)  # 5-second TTL
cache.set("key1", "value1")
cache.get("key1")  # → "value1"
# ... after 5 seconds ...
cache.get("key1")  # → None (expired)

See solution

import time
from typing import Any

class TTLCache:
    """Cache with a per-entry Time-To-Live."""
    
    def __init__(self, default_ttl: float = 60.0):
        self.default_ttl = default_ttl
        self._store: dict[str, tuple[Any, float]] = {}
    
    def set(self, key: str, value: Any, ttl: float | None = None) -> None:
        expires_at = time.time() + (ttl if ttl is not None else self.default_ttl)
        self._store[key] = (value, expires_at)
    
    def get(self, key: str) -> Any | None:
        if key not in self._store:
            return None
        value, expires_at = self._store[key]
        if time.time() > expires_at:
            del self._store[key]
            return None
        return value
    
    def cleanup(self) -> int:
        """Removes expired entries. Returns how many it removed."""
        now = time.time()
        expired = [k for k, (_, exp) in self._store.items() if now > exp]
        for k in expired:
            del self._store[k]
        return len(expired)
    
    def __len__(self):
        return len(self._store)
    
    def __repr__(self):
        return f"TTLCache(entries={len(self._store)}, ttl={self.default_ttl}s)"


cache = TTLCache(default_ttl=0.5)
cache.set("fast", "value_fast", ttl=0.1)
cache.set("slow", "value_slow", ttl=2.0)

assert cache.get("fast") == "value_fast"
assert cache.get("slow") == "value_slow"

time.sleep(0.15)
assert cache.get("fast") is None
assert cache.get("slow") == "value_slow"

print(f"Cache: {cache}")
print(f"Entries after expiry: {len(cache)}")
# Output:
# Cache: TTLCache(entries=1, ttl=0.5s)
# Entries after expiry: 1

print("✓ TTLCache works correctly")

Explanation: Each entry is stored as (value, expires_at). On get, we check whether the current timestamp is past expires_at. If it is, the entry is deleted and None is returned. cleanup() walks the whole store to drop expired entries — in production you'd do this with a periodic timer.

Exercise 3: Common elements across multiple lists (Basic-Intermediate)

Implement find_common(*lists) to find the elements present in all the lists using set operations. Also implement find_in_at_least(lists, n) to find elements present in at least n lists.

find_common([1,2,3], [2,3,4], [3,4,5])     # → {3}
find_in_at_least([[1,2,3], [2,3,4], [3,4,5]], 2)  # → {2, 3, 4}

See solution

from collections import Counter

def find_common(*lists: list) -> set:
    """Finds the elements present in ALL the lists."""
    if not lists:
        return set()
    result = set(lists[0])
    for lst in lists[1:]:
        result &= set(lst)
    return result


def find_in_at_least(lists: list[list], n: int) -> set:
    """Finds the elements present in at least n lists."""
    presence_count = Counter()
    for lst in lists:
        presence_count.update(set(lst))
    return {elem for elem, count in presence_count.items() if count >= n}


assert find_common([1,2,3], [2,3,4], [3,4,5]) == {3}
assert find_common([1,2], [3,4]) == set()
assert find_common([1,2,3]) == {1, 2, 3}

assert find_in_at_least([[1,2,3], [2,3,4], [3,4,5]], 2) == {2, 3, 4}
assert find_in_at_least([[1,2,3], [2,3,4], [3,4,5]], 3) == {3}
assert find_in_at_least([[1,2,3], [2,3,4], [3,4,5]], 1) == {1, 2, 3, 4, 5}

print("✓ find_common and find_in_at_least work correctly")

Explanation: find_common uses successive intersection (&=), which is O(min(len(sets))). find_in_at_least converts each list to a set (to deduplicate within the list) and uses Counter to count how many lists each element shows up in.

Exercise 4: Inverted index for text search (Intermediate-Hard)

Implement SearchEngine with the following features:

add_document(doc_id, content) — indexes a document
search(query) — finds documents containing ALL the words
search_any(query) — finds documents containing ANY of the words
get_stats() — returns index statistics

engine = SearchEngine()
engine.add_document("doc1", "Python backend API REST")
engine.add_document("doc2", "Python frontend React")
engine.add_document("doc3", "Java backend microservices")

engine.search("python backend")    # → ["doc1"]
engine.search_any("python backend") # → ["doc1", "doc2", "doc3"]

See solution

from collections import defaultdict

class SearchEngine:
    """Simple search engine with an inverted index."""
    
    def __init__(self):
        self._index: dict[str, set[str]] = defaultdict(set)
        self._documents: dict[str, str] = {}
    
    def add_document(self, doc_id: str, content: str) -> None:
        self._documents[doc_id] = content
        for word in set(content.lower().split()):
            self._index[word].add(doc_id)
    
    def search(self, query: str) -> list[str]:
        """Returns the docs containing ALL the words in the query."""
        words = query.lower().split()
        if not words:
            return []
        result = set(self._index.get(words[0], set()))
        for word in words[1:]:
            result &= self._index.get(word, set())
        return sorted(result)
    
    def search_any(self, query: str) -> list[str]:
        """Returns the docs containing ANY of the words in the query."""
        result: set[str] = set()
        for word in query.lower().split():
            result |= self._index.get(word, set())
        return sorted(result)


engine = SearchEngine()
engine.add_document("doc1", "Python backend API REST")
engine.add_document("doc2", "Python frontend React")
engine.add_document("doc3", "Java backend microservices")
engine.add_document("doc4", "Python backend microservices Docker")

assert engine.search("python backend") == ["doc1", "doc4"]
assert engine.search("python") == ["doc1", "doc2", "doc4"]
assert engine.search_any("python java") == ["doc1", "doc2", "doc3", "doc4"]

print("✓ SearchEngine works correctly")

Explanation: The inverted index maps each word to a set of doc_ids. An AND search uses intersection (&=), an OR search uses union (|=). This is the basic principle behind Elasticsearch and Lucene.

Troubleshooting

"I'm using a dict but I get a KeyError when accessing a key"

Cause: You're using dict[key] instead of dict.get(key).

data = {"name": "Ana"}

# WRONG — raises KeyError if the key doesn't exist
try:
    print(data["email"])
except KeyError:
    print("KeyError!")
# Output: KeyError!

# RIGHT — returns None or a default
print(data.get("email"))
# Output: None

print(data.get("email", "no-email"))
# Output: no-email

Rule: Use dict[key] only when you're sure the key exists. With external data (APIs, user input, databases), always use .get().

"My defaultdict creates entries I don't want"

Cause: Merely accessing a key creates the entry with the default:

from collections import defaultdict

dd = defaultdict(list)
print(dd["missing_key"])
# Output: []

print(dict(dd))
# Output: {'missing_key': []}  ← the key got created!

Solution: Use key in dd before accessing, or use .get():

from collections import defaultdict

dd = defaultdict(list)

if "key" in dd:
    print(dd["key"])

value = dd.get("key", "not found")
print(value)
# Output: not found

print(dict(dd))
# Output: {}

"I want to use a list as a dict key and I get a TypeError"

Cause: Lists are mutable → they're not hashable → they can't be keys:

try:
    d = {[1, 2, 3]: "value"}
except TypeError as e:
    print(f"Error: {e}")
# Output: Error: unhashable type: 'list'

Solution: Convert it to a tuple (immutable → hashable):

d = {(1, 2, 3): "value"}
print(d[(1, 2, 3)])
# Output: value

coordinates = {}
coordinates[(40.7, -74.0)] = "New York"
coordinates[(34.0, -118.2)] = "Los Angeles"
print(coordinates[(40.7, -74.0)])
# Output: New York

"Sets don't keep insertion order"

Cause: Sets are hash tables — they guarantee no order:

s = {3, 1, 4, 1, 5, 9, 2, 6}
print(s)
# Output: {1, 2, 3, 4, 5, 6, 9}  (order not guaranteed)

Solution: If you need order + uniqueness, use dict.fromkeys():

items = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
unique_ordered = list(dict.fromkeys(items))
print(unique_ordered)
# Output: [3, 1, 4, 5, 9, 2, 6]

"Counter returns 0 for keys that don't exist — is that a bug?"

It's not a bug, it's a feature. Counter overrides __missing__ to return 0 instead of raising KeyError. "z" in counter still returns False — only direct access counter["z"] returns 0.

Summary

In this lesson you covered the dict and set patterns you'll use daily as a backend developer:

dict.get(key, default) avoids KeyError on external data. Rule: .get() for uncertain data, dict[key] for guaranteed data.
defaultdict auto-initializes missing values: int for counts, list for grouping, set for grouping without duplicates. It kills the verbose "check if key exists, create if not" pattern.
Counter does frequency counting in one line. most_common(n), arithmetic between counters, and it returns 0 for missing keys.
set for O(1) membership testing — with a million items, it's ~200,000x faster than a list. Set operations (|, &, -, ^) to cross-reference data.
frozenset when you need a set as a dict key or as an element of another set.
OrderedDict for move_to_end() and popitem(last=False) — the basis of LRU caches.
Backend patterns: in-memory cache, deduplication with a set, inverted index with defaultdict, rate limiting with a dict, merging data from multiple sources.

What's coming next: In lesson 07 you'll apply all of this to solve classic technical-interview problems: two-sum, anagrams, first non-repeating character. They all get solved with dict/set, turning brute-force O(n²) into O(n) solutions.

6. Dict and Set — Usage Patterns in Backend

Lesson overview

Dict as the backbone of Python backends

dict.get() vs dict[key] — avoiding KeyError

The solution: dict.get(key, default)

dict.setdefault() — insert if missing

Dict comprehensions

Filtering with a condition

Inverting a dict

Transforming data from an API

collections.defaultdict — auto-initialize missing keys

Counting with defaultdict(int)

Grouping with defaultdict(list)

When defaultdict vs setdefault vs .get()?

collections.Counter — frequency counting

.most_common(n) — the most frequent ones

Counter from strings

Set — much more than "a list without duplicates"

Membership testing: O(1) vs O(n)

Set operations

Set comprehensions

frozenset — immutable, hashable sets

Backend patterns with real code

Pattern 1: In-memory result cache

Pattern 2: Tracking processed IDs (deduplication)

Pattern 3: Inverted index with defaultdict(list)

Pattern 4: Rate limiting with a dict

Pattern 5: Merging data from multiple sources

collections.OrderedDict — when order matters

move_to_end() and popitem() — the basis of LRU caches

When to use OrderedDict vs a regular dict?

Performance: when should you convert a list to a set?

Exercises

Exercise 1: Word frequency counter with Counter (Basic)

Exercise 2: Cache with TTL (Intermediate)

Exercise 3: Common elements across multiple lists (Basic-Intermediate)

Exercise 4: Inverted index for text search (Intermediate-Hard)

Troubleshooting

"I'm using a dict but I get a KeyError when accessing a key"

"My defaultdict creates entries I don't want"

"I want to use a list as a dict key and I get a TypeError"

"Sets don't keep insertion order"

"Counter returns 0 for keys that don't exist — is that a bug?"

Summary

Further reading

`dict.get()` vs `dict[key]` — avoiding KeyError

The solution: `dict.get(key, default)`

`dict.setdefault()` — insert if missing

`collections.defaultdict` — auto-initialize missing keys

Counting with `defaultdict(int)`

Grouping with `defaultdict(list)`

When `defaultdict` vs `setdefault` vs `.get()`?

`collections.Counter` — frequency counting

`.most_common(n)` — the most frequent ones

`frozenset` — immutable, hashable sets

Pattern 3: Inverted index with `defaultdict(list)`

`collections.OrderedDict` — when order matters

`move_to_end()` and `popitem()` — the basis of LRU caches

When to use `OrderedDict` vs a regular `dict`?