Capstone: solving problems efficiently

Rosa has asked Jordan for a dispatch assistant for the wholesale business. Every morning it must take the day's orders and the delivery network, decide the order in which to pack, find the quickest drive to each customer, answer questions such as how many bags went to the Alder Hotel last month, and flag coffees that will run out before the next roast. The data is growing quickly: thousands of orders a month, dozens of customers and a year of sales history. The first version Jordan wrote, a pile of nested loops, took most of a minute on a laptop. This capstone rebuilds it with the structures from this course.

Rather than introduce new structures, this lesson shows how to choose among the ones you know. It starts with a method for turning requirements into a choice of structure, applies it to each feature of the dispatch assistant, measures the difference with step counts, and ends with a checklist you can use on any program that has become slow.

A method for choosing structures

Most performance problems in business code are not solved by clever tricks but by choosing a structure whose cheap operations match what the program does most. Four questions lead to the choice. First, list the operations the program performs: lookups by key, insertions, removals of the smallest item, range queries, ordered listings, connections between things. Second, estimate how often each runs and how big the data will become. Third, find the structure that makes the frequent operations cheap, using the costs from this course. Fourth, measure before and after, and keep the simpler solution when the difference does not matter.

Step 1: indexing customers and orders

Jordan's first version stored orders in one long list and, for every report, looped over the list looking for matching customers or coffees. Each report was O(n), and the morning summary ran dozens of reports, each scanning thousands of orders. The fix is to build indexes once, as the data is loaded, so later questions become dictionary lookups. A dictionary from customer to their orders, and another from coffee to bags sold, replace almost every scan.

from collections import defaultdict, Counter

orders = [
    {"id": 2001, "day": "2026-10-02", "customer": "Alder Hotel", "sku": "RC-101", "bags": 12, "priority": 1},
    {"id": 2002, "day": "2026-10-02", "customer": "Bayside Bakery", "sku": "RC-104", "bags": 6, "priority": 2},
    {"id": 2003, "day": "2026-10-09", "customer": "Alder Hotel", "sku": "RC-106", "bags": 8, "priority": 0},
    {"id": 2004, "day": "2026-10-15", "customer": "Lakeview Cafe", "sku": "RC-101", "bags": 20, "priority": 2},
    {"id": 2005, "day": "2026-10-23", "customer": "Alder Hotel", "sku": "RC-101", "bags": 10, "priority": 1},
    {"id": 2006, "day": "2026-11-02", "customer": "Hilltop Market", "sku": "RC-102", "bags": 5, "priority": 2},
]

by_customer = defaultdict(list)
bags_by_sku = Counter()
for o in orders:                                   # one pass builds both indexes
    by_customer[o["customer"]].append(o)
    bags_by_sku[o["sku"]] += o["bags"]

print("Alder Hotel orders:", [o["id"] for o in by_customer["Alder Hotel"]])
print("Alder Hotel bags:", sum(o["bags"] for o in by_customer["Alder Hotel"]))
print("best sellers:", bags_by_sku.most_common(2))

Alder Hotel orders: [2001, 2003, 2005]
Alder Hotel bags: 30
best sellers: [('RC-101', 42), ('RC-106', 8)]

The indexes cost one pass and some memory, O(n), and then each question costs only the size of its answer. This is the trade from lesson 1 of space for time, and it is almost always worth making for data that is queried repeatedly.

Step 2: date ranges with binary search

Anita's questions are usually about periods: bags sold to the Alder Hotel in October, or every order in the last two weeks. Because orders are recorded in time order, the list of days is already sorted, and the binary search range technique from lesson 7 finds the start and end of any period in O(log n). For per-customer periods, each customer's order list is also in time order, so the same technique works on it.

from bisect import bisect_left, bisect_right

days = ["2026-10-02", "2026-10-02", "2026-10-09", "2026-10-15", "2026-10-23", "2026-11-02"]
bags = [12, 6, 8, 20, 10, 5]

def bags_between(first, last):
    lo, hi = bisect_left(days, first), bisect_right(days, last)
    return sum(bags[lo:hi]), hi - lo

print("October:", bags_between("2026-10-01", "2026-10-31"))
print("first half of October:", bags_between("2026-10-01", "2026-10-15"))
print("December:", bags_between("2026-12-01", "2026-12-31"))

October: (56, 5)
first half of October: (46, 4)
December: (0, 0)

If Anita needed many range totals over a large, unchanging history, a further refinement would store running totals (the prefix sums you built in lesson 2's exercise) so that each total is a subtraction of two running totals instead of a sum over the slice: O(log n) per question regardless of the period's length.

class DailyTotals:
    def __init__(self, days, bags):
        self.days, self.bags = days, bags

    def between(self, first, last):
        return sum(b for d, b in zip(self.days, self.bags) if first < d < last)

t = DailyTotals(['2026-10-02', '2026-10-09', '2026-10-15'], [12, 8, 20])
print(t.between('2026-10-05', '2026-10-31'))

Step 3: packing by priority

Each morning's orders must be packed most urgent first: priority 0 for wholesale orders due today, 1 for express and 2 for standard, with ties in arrival order. Jordan's first version sorted the whole list every time an order arrived, O(n log n) per arrival. A heap, from lesson 10, makes each arrival and each packing step O(log n), and a counter breaks ties so equal priorities stay first come, first served.

import heapq, itertools

class PackingQueue:
    def __init__(self):
        self.heap, self.seq = [], itertools.count()
    def add(self, order):
        heapq.heappush(self.heap, (order["priority"], next(self.seq), order["id"]))
    def next(self):
        return heapq.heappop(self.heap)[2] if self.heap else None

q = PackingQueue()
for o in [{"id": 2101, "priority": 2}, {"id": 2102, "priority": 1},
          {"id": 2103, "priority": 2}, {"id": 2104, "priority": 0}]:
    q.add(o)
print([q.next() for _ in range(5)])

[2104, 2102, 2101, 2103, None]

Step 4: drive times

The van's route needs drive times from the roastery to every customer. Running Dijkstra's algorithm, from lesson 11, once from the roastery gives the quickest time to every place at once, so there is no need to search separately for each customer. Those times then feed a simple rule: deliver to customers in order of drive time from the roastery, a reasonable plan for a small van, though choosing the truly best order of many stops is a famously hard problem (the traveling salesperson problem) that real delivery companies tackle with specialized optimization tools.

import heapq

def drive_times(graph, start):
    best = {start: 0}
    heap = [(0, start)]
    while heap:
        t, place = heapq.heappop(heap)
        if t > best[place]:
            continue
        for nxt, minutes in graph[place].items():
            if t + minutes < best.get(nxt, float("inf")):
                best[nxt] = t + minutes
                heapq.heappush(heap, (t + minutes, nxt))
    return best

roads = {
    "Roastery": {"Cafe": 6, "Warehouse": 9}, "Cafe": {"Roastery": 6, "Lakeview Cafe": 12, "Warehouse": 5},
    "Warehouse": {"Roastery": 9, "Cafe": 5, "Bayside Bakery": 7, "Pine St Deli": 14},
    "Lakeview Cafe": {"Cafe": 12, "Alder Hotel": 15}, "Bayside Bakery": {"Warehouse": 7, "Alder Hotel": 10},
    "Alder Hotel": {"Lakeview Cafe": 15, "Bayside Bakery": 10},
    "Pine St Deli": {"Warehouse": 14, "Hilltop Market": 8}, "Hilltop Market": {"Pine St Deli": 8},
}
times = drive_times(roads, "Roastery")
customers = ["Alder Hotel", "Bayside Bakery", "Hilltop Market", "Lakeview Cafe"]
for c in sorted(customers, key=times.get):
    print(f"{c:<15} {times[c]:>3} min")

Bayside Bakery   16 min
Lakeview Cafe    18 min
Alder Hotel      26 min
Hilltop Market   31 min

def nearest_open(times, open_now):
    return min(open_now)

print(nearest_open(times, {'Alder Hotel', 'Lakeview Cafe'}))

Step 5: stock alerts

Kai needs to know which coffees will run out before the next roast in three days. A sliding window from lesson 3 gives the average daily sales over the last week for each coffee in O(1) per new day, and comparing stock with three days of average sales flags the coffees at risk. A heap's nsmallest then lists the coffees with the fewest days of stock left, so Kai sees the most urgent first.

import heapq
from collections import deque

stock = {"RC-101": 30, "RC-102": 40, "RC-104": 9, "RC-106": 16}
daily = {                                       # bags sold on each of the last 9 days
    "RC-101": [9, 11, 8, 12, 10, 9, 13, 11, 12],
    "RC-102": [2, 1, 3, 2, 2, 1, 2, 3, 2],
    "RC-104": [3, 2, 4, 3, 3, 4, 3, 2, 4],
    "RC-106": [4, 5, 3, 6, 4, 5, 4, 6, 5],
}

def weekly_average(sales, days=7):
    window, total = deque(maxlen=days), 0
    for s in sales:
        if len(window) == days:
            total -= window[0]
        window.append(s)
        total += s
    return total / len(window)

days_left = {sku: stock[sku] / weekly_average(daily[sku]) for sku in stock}
at_risk = [sku for sku, d in days_left.items() if d < 3]
print("at risk before the next roast:", sorted(at_risk))
print("most urgent:", [(s, round(days_left[s], 1)) for s in heapq.nsmallest(3, days_left, key=days_left.get)])

at risk before the next roast: ['RC-101', 'RC-104']
most urgent: [('RC-104', 2.7), ('RC-101', 2.8), ('RC-106', 3.4)]

Measuring the improvement

How much faster is the new version? Counting the basic operations each version performs gives an answer that does not depend on the computer. The listing models the morning workload of Jordan's first version and of the new one for growing numbers of orders. The old version scanned every order for each of the c customers and re-sorted the waiting orders at every arrival; the new one indexes the orders once and uses a heap.

import math

def old_steps(n, customers=40):
    scans = customers * n                           # one full scan per customer report
    resorts = sum(k * math.log2(k) for k in range(2, n + 1))   # sort on every arrival
    return scans + resorts

def new_steps(n, customers=40):
    index = n                                       # one pass builds the indexes
    reports = n                                     # each order appears in one customer's list
    heap = n * math.log2(n)                         # push and pop each order once
    return index + reports + heap

print(f"{'orders':>8} {'old steps':>16} {'new steps':>12} {'times faster':>13}")
for n in [100, 1_000, 10_000]:
    o, w = old_steps(n), new_steps(n)
    print(f"{n:>8,} {o:>16,.0f} {w:>12,.0f} {o / w:>13,.0f}")

  orders        old steps    new steps  times faster
     100           33,946          864            39
   1,000        4,667,202       11,966           390
  10,000      628,784,683      152,877         4,113

The model is rough, since real costs depend on constants the counts ignore, but the trend is unmistakable and matches what Jordan measured: the old version's cost grows roughly with n² log n because of the repeated sorting, while the new version grows with n log n. At ten thousand orders the gap is a factor of thousands. Timing the real program with the methods from lesson 1, on realistic data, confirms the estimate before anyone relies on it.

def top_coffee_by_day(sales):
    result = {}
    for day, sku, bags in sales:
        result[day] = sku
    return result

print(top_coffee_by_day([('10-02', 'RC-101', 12), ('10-02', 'RC-104', 6), ('10-02', 'RC-104', 9)]))

A checklist for slow programs

The same reasoning applies to any program that has become slow as its data grew. Work through these steps in order, and stop as soon as the program is fast enough; simpler code is easier to trust.

• Measure first. Time the program on realistic data, and find which part is slow before changing anything.
• Look for hidden loops: in on a list, list.remove, list.insert(0, x), list.pop(0), slicing in a loop, and sorting inside a loop.
• Replace repeated searches with an index built once: a dict, a set, a Counter or a defaultdict.
• Keep data sorted if you search ranges, and use bisect instead of scanning.
• Use the right container for the access pattern: deque for queues, heapq for priorities, a graph for connections.
• Cache expensive results that are requested again, with functools.cache or a dictionary.
• Check correctness after every change by comparing the new output with the old on the same data.