Lesson 04 — Data structures and algorithms

Stack: Django + DRF · Project: TicketFlow Status: Published — taught after Lesson 03 is corrected Prerequisite: Lesson 03 — Concurrency

Objectives

By the end of this lesson you will be able to:

1. Analyze an algorithm's cost with Big-O and, more importantly, know when Big-O does not matter.
2. Choose the right data structure for each domain problem (cart, availability, seat map).
3. Recognize the hidden costs of Python's collections (lists, sets, dicts, defaultdict, Counter).
4. Translate in-memory structures into database indexes — and understand why Lesson 09 is this lesson's natural continuation.

1. Big-O without panic (and without fanaticism)

Big-O describes how cost grows as the input grows. The orders you will use:

Two uncomfortable truths juniors don't know:

1. Big-O does not tell you the real time. An O(n) with n=50 can beat an O(1) that makes a DB query. The constant matters until n is large; and in backend, "large" is usually n>10,000.
2. Your bottleneck is almost never the algorithm: it is the I/O. An in-memory O(n²) with n=1000 is milliseconds; an O(n) making 1000 DB queries is seconds. The O(N+1) (Lesson 09) is API killer number one, and its full name is "n+1 round trips over the network".

Key: measure first (Lesson 37), then optimize the right algorithm. But choose the right structure from day one, because that decision doesn't show up in the profiler: it shows up in the code's readability.

2. The Python structures you will use every week

Costs that surprise everyone:

• x in lista is O(n); x in set is O(1) average. The most common junior-backend performance bug is searching inside lists within loops.
• Concatenating strings with += in a loop is O(n²) worst case; ''.join(pieces) is O(n).
• list.pop(0) is O(n); deque.popleft() is O(1). A growing queue is a deque, not a list.
• Copying large lists inside loops is a silent memory killer.

3. Choosing structures: TicketFlow's real problems

Problem A — "Is this set of seats free?" (shopping cart)

The user selects [A-12, B-3, C-9] and you want to know whether ALL of them are free before reserving.

# O(k · n): for each chosen seat (k), search the free list (n)
for seat in requested_seats:
    if seat not in available_list:   # O(n) per iteration → O(k·n)
        return conflict(seat)

# O(k): turn the free seats into a set once, ask k times at O(1)
available_set = set(available_seats)          # O(n)
missing = [s for s in requested_seats if s not in available_set]  # O(k)
if missing:
    return conflict(missing)

With n=20,000 seats and k=6, the difference is invisible on your laptop. It shows up on concert day, at 200 requests per second, where CPU cycles multiply by the worker's queue latency.

Problem B — "Group seats by section" (availability response)

# Less efficient: walk seats and sections (nested)
# Efficient: one pass with defaultdict
from collections import defaultdict

by_sector = defaultdict(list)
for seat in seats:                    # O(n)
    by_sector[seat.sector].append(seat)   # O(1) per seat

Problem C — "The 10 reservations that expire soonest" (expiration job)

For a top-K of minimums, a heap (or simply ORDER BY expires_at LIMIT 10 in SQL — with the (status, expires_at) index you already created in 00b). The "right" structure in backend is often a well-chosen index: the B-tree is your persistent, ordered, transactional heap, shared across processes. That is why the senior backend's priority order is:

1. Let the DB sort/filter (indexes, LIMIT).
2. If it must be processed in memory, pick the structure with the right cost.
3. Measure. The rest is superstition.

4. Complexity hiding in "normal" code

Big fish you will see in reviews:

# 1. N+1: O(n) queries — the classic (Lesson 09 kills it with select_related)
for reservation in reservations:
    print(reservation.user.email)     # 1 query per reservation

# 2. Double loop where a dict suffices: O(n²) → O(n)
for a in asientos:
    for r in reservas:
        if r.seat_id == a.id: ...

seats_by_id = {a.id: a for a in asientos}   # O(n) once
for r in reservas:
    a = seats_by_id.get(r.seat_id)          # O(1) per lookup

# 3. "Is it in the list?" inside a loop: O(n·m)
if user.id in lista_de_ids_vip:  # list → set()

# 4. Building strings in a loop: O(n²)
html = ""
for fila in filas:
    html += f"<tr>{fila}</tr>"    # use list + "".join()

And the rule that ties it all together: each of these mistakes is invisible with development data and explosive with production data. Not because the algorithm changes; because n changes.

5. Concrete algorithms you will actually know by heart

• Binary search: over sorted lists, O(log n). PostgreSQL's B-tree index uses it every time you filter. Understanding it is understanding EXPLAIN (Lesson 09).
• Merge / stable sort: Django order_by and rankings; know that sorting is O(n log n) and that sorting twice (by two fields) can be one call with tuples.
• BFS/DFS (graph traversal): shows up computing "contiguous available sections" or dependency relations. You won't implement them daily, but recognizing the "dependency graph" pattern will save you in Module 12 (resilience: dependencies between services).
• Sliding window / two pointers: for "best contiguous block of seats" (the user wants 4 together): pointers over the sorted row of seats, O(n) instead of O(n²).

Self-assessment (answer me in the chat)

1. An endpoint takes 800 ms: the algorithm is O(n) over 500 elements. What would you do first, and why is Big-O not (yet) in the way?
2. Why is seat in free_list inside a loop the most common bug? Rewrite it and name the cost before and after.
3. Which structure would you use for "top 10 events by sales in the last 2 hours" in memory? And if the source is SQL? Why does the answer change?
4. "Best contiguous block of 4 seats in a row" — which algorithmic pattern do you apply and what would its cost be?
5. Why do we say "a B-tree index is a persistent, shared heap"? What does it gain and lose against an in-process heapq?

Continue with the exercises. The solutions only after trying it yourself.