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 — The list vs set test
  2. Exercise 2 — Group and count (your availability)
  3. Exercise 3 — Top-K of expirations
  4. Exercise 4 — The contiguous block (two pointers)
  5. Exercise 5 — The hidden complexity of your API
  6. Exercise 6 — Big-O analysis of your serializer (critical reading)
  7. Submit

Exercises 1-4 run in a loose script (structures_lab.py); 5-6 go inside your TicketFlow. Do not look at solutions.md before submitting.

Setup:

bash
cd ~/dev/ticketflow && source .venv/bin/activate

Exercise 1 — The list vs set test

  1. Build a list of 100,000 IDs and measure:
python
import time, random

ids = list(range(100_000))
target = random.sample(ids, 1000)

t0 = time.perf_counter()
found = [x for x in target if x in ids]        # O(?) per lookup
t1 = time.perf_counter()
print(f"list: {t1 - t0:.4f}s")
  1. Repeat with ids_set = set(ids). Write down both times and the speedup.
  2. When does the set NOT pay off? (hint: building the set is O(n); how many lookups do you need to amortize it?)

Exercise 2 — Group and count (your availability)

Given this list of simulated seats:

python
seats = [
    {"sector": "A", "row": "1", "number": n, "type": "VIP" if n < 5 else "GENERAL"}
    for n in range(1, 51)
] + [
    {"sector": "B", "row": "1", "number": n, "type": "GENERAL"}
    for n in range(1, 31)
]
  1. Group by sector with defaultdict(list) and return {sector: count}.
  2. Count by type with Counter.
  3. Compute each sector's lowest-numbered free seat... then sort the sectors by "smallest gap" (hint: heapq or min + sorted; which is cleaner here and why?)

Exercise 3 — Top-K of expirations

  1. Generate 10,000 reservations with random expires_at. With heapq, extract the 10 that expire soonest in O(n log k).
  2. Compare with sorted(reservations, key=...)[:10] and time both. Does the heap win? Is the difference worth the reading complexity?
  3. Now write the equivalent SQL/Django query (Reservation.objects.filter(status=...).order_by("expires_at")[:10]) and compare approaches: where does each cost live (process memory vs DB + network)?

Exercise 4 — The contiguous block (two pointers)

A user wants 4 seats together in row "A" of section "B". The row's free seats are: [3, 4, 5, 6, 12, 13, 20, 21, 22, 23, 24].

  1. Write a function best_block(free_numbers: list[int], k: int) -> list[int] | None that returns the first block of k consecutive seats (or None). It must be O(n) — two pointers or a single pass; the double loop is forbidden.
  2. Test it: best_block([3,4,5,6,12,13,20,21,22,23,24], 4) → [20,21,22,23] and best_block([3,4,20], 3) → None.
  3. What changes if "best" means "the most centered in the row" rather than "the first"?

Exercise 5 — The hidden complexity of your API

Open your available_seats(event_id) (you wrote it in 00b):

  1. Count how many queries it runs with 3 events, 500 seats each. Is it 1, n or n²? (hint: from django.db import connection; print(len(connection.queries))).
  2. If it does N+1, fix it with select_related/prefetch_related or with the subquery you saw in the 00b solutions. Measure before and after.
  3. The response groups by sector (Exercise 2): where would grouping be more expensive, in Python or in SQL (GROUP BY)? Justify with the expected response size and bandwidth.

Exercise 6 — Big-O analysis of your serializer (critical reading)

Take any DRF serializer from your project (or write one that validates 10 fields):

  1. How many times is each field validated? What is the cost of the global validate()?
  2. DRF runs to_representation per object: if a listing serializes 200 events and each accesses event.organizer.name without select_related, what is the query complexity of the whole response?
  3. Write the rule you will use from today on: "every in-memory O(n) that accompanies a per-object access must be checked against ___".

Submit

Paste results, measurements and diffs in the chat. With the correction we close Lesson 04 and move to Lesson 05 — Linux and the terminal: the processes you just multiplied in Gunicorn, from the console that operates them.

^ top