The Professor
Index Course index

Module 1 · Foundations that hold everything up

Lesson 04 — Data structures and algorithms

Complexity and performance with intent: which structure survives the sales peak and which one sinks.

Published
In this lesson
  1. Exercise 1 — List vs set
  2. Exercise 2 — Group and count
  3. Exercise 3 — Top-K of expirations
  4. Exercise 4 — The contiguous block
  5. Exercise 5 — Your API's complexity
  6. Exercise 6 — Critical reading of the serializer
  7. Professor's summary

Measurement rules. If your numbers don't match these, run with bigger sizes and you will see the shape of the curve.

Exercise 1 — List vs set

1-2. Typical results: with the list ~2-4 s (1000 lookups × O(100,000) comparisons = ~10⁸ operations); with the set ~0.0002-0.0005 s. Speedup: ×10,000. Semantically the same code, two worlds of cost.

  1. Building the set costs O(n) time and O(n) extra memory. If you look up once, the list wins (you don't pay the construction). Approximate break-even: more than 2-3 lookups and the set already amortizes. In APIs, the practical rule: if the collection lives in a request and is consulted more than once, it is a set.

Exercise 2 — Group and count

python
from collections import defaultdict, Counter

by_sector = defaultdict(list)
for s in seats:
    by_sector[s["sector"]].append(s)
sector_count = {sector: len(its) for sector, its in by_sector.items()}

type_count = Counter(s["type"] for s in seats)
  1. For "the smallest gap per sector", min(by_sector["A"], key=lambda s: s["number"]) is O(n) per sector and the most readable option. heapq shines when you need top-K repeatedly or over a growing stream; here you only ask for one minimum per group: the heap would be over-engineering (and its O(n log n) build cost is worse than an O(n) min). Cross-cutting criterion of the lesson: the right structure is the one that solves the problem at exactly the right cost, not the most sophisticated one.

Exercise 3 — Top-K of expirations

  1. heapq.nsmallest(10, reservations, key=lambda r: r["expires_at"]) — O(n log k) with k=10.
  2. sorted(...)[:10] is O(n log n). With n=10,000 and k=10, nsmallest wins (typically ×3-5) but both take milliseconds. The heap is only worth it if n is huge or it repeats every second. Worth knowing, rarely needed.
  3. The query with order_by("expires_at")[:10] moves the cost into the DB: with 00b's (status, expires_at) index it is an index scan returning 10 rows — no process memory, no 10,000 rows over the wire. The cost lives in the DB (which already paid it with the index) instead of the Python process (which would pay it in RAM and GC). In backend, the best-Big-O answer is often "none": let the DB hand you only what you need.

Exercise 4 — The contiguous block

python
def best_block(free_numbers: list[int], k: int) -> list[int] | None:
    """First block of k consecutive numbers in a single pass (O(n))."""
    start = 0
    for i, number in enumerate(free_numbers):
        if i > 0 and number != free_numbers[i - 1] + 1:
            start = i                      # the streak breaks: new window
        if number - free_numbers[start] == k - 1:
            return free_numbers[start:start + k]
    return None
  1. [20, 21, 22, 23] and None, respectively.
  2. With "best = most centered": walk all the blocks (same pass), score each candidate by distance to the row's center and return the minimum-scoring one. Still O(n) — contiguous blocks are detected in the same sweep. The variant changes the selection criterion, not the algorithmic pattern.

Exercise 5 — Your API's complexity

  1. With the 00b solution (subquery/exclude with Q), the function runs 1 query no matter how many events: the filtering happens in the DB in one SELECT.
  2. If you counted n queries (one per event or per seat), the fix is prefetch_related("reservation_items__reservation") (for the reverse relation) or the subquery. Typical measurement: from ~500 queries and seconds, to 1 query and tens of ms. That is exactly Lesson 09 previewed.
  3. GROUP BY in SQL: aggregation happens next to the data and only the aggregated result (few rows) travels the network. Grouping in Python forces fetching all rows (or several queries). For API responses: aggregate in SQL, group/transform in Python only when you need the full row. Bandwidth and memory travel in the opposite direction from junior intuition ("I control it better in Python").

Exercise 6 — Critical reading of the serializer

  1. DRF validates field by field (each validate_<field> once per object) and the global validate() afterwards. Per-object cost is small and linear; the danger is not there but in what you touch inside the validators (do you hit the DB per object?).
  2. to_representation per object + event.organizer.name without select_related = 1 extra query per event (O(n) queries, the same old N+1). With 200 events: 201 queries per request. The rule: in any listing, the cost is not in serializing, it is in what you touch per object.
  3. The rule you already know from 00b and 03: "every in-memory O(1) that accompanies a per-object access must be checked against the DB and the network" — an O(1) that fires a query is a real O(latency).

Professor's summary

  • Pick the structure at the right cost: set for membership, defaultdict for grouping, deque for queues, heap for repeated top-K.
  • In backend, the Big-O that hurts is the one multiplying DB round trips, not the one multiplying CPU cycles.
  • "A B-tree index is your persistent heap": delegate ordering and filtering to the DB whenever you can.
  • Always measure (Lesson 37 systematizes it). Performance intuition lies elegantly.

When you submit, we close Lesson 04 and open Lesson 05 — Linux and the terminal: everything you just measured, from the console where processes live.

^ top