Openingloading the content…

Loadingone moment…

Batch

Pure Python Batch Transform Patterns

Use map/filter/reduce-style flows, in-memory joins, aggregations, stateful scans, and sorted-window logic.

⏱ 24 min readTopics chapter readerLevel · Intermediate

01 · Overview

Batch transforms in pure Python

⏱ 5 min · Topic 1 of 19

A batch is a fixed set of rows that you process in one run. A transform turns that set into a new set. Pure Python means no pandas (a popular table library): only dicts, lists and the standard library.

The senior Python round asks for this. You write a clean transform, then you scale it and explain the good and bad sides of each choice. This chapter gives you the patterns for both steps.

Here is the shop again, as Python data. Money is Decimal, as you learned in Types, Time, Nulls & Numeric Correctness. Most examples in this chapter start from these three lists:

The shop as three lists of dictsworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

customers5 rows

customer_id	name	country
1	Asha	IN
2	Ben	GB
3	Carla	US
4	Dev	None
5	Omar	IN

order_items7 rows

order_id	product	qty
101	Pen	2
101	Notebook	1
102	Bag	1
103	Lamp	1
104	Pen	3
106	Chair	1
106	Lamp	1

from decimal import Decimal

orders = [
    {"order_id": 101, "customer_id": 1, "status": "paid",
     "amount": Decimal("40.00"), "order_date": "2026-01-03"},
    {"order_id": 102, "customer_id": 1, "status": "paid",
     "amount": Decimal("25.00"), "order_date": "2026-01-10"},
    {"order_id": 103, "customer_id": 2, "status": "refunded",
     "amount": Decimal("60.00"), "order_date": "2026-01-11"},
    {"order_id": 104, "customer_id": 3, "status": "paid",
     "amount": Decimal("15.50"), "order_date": "2026-01-15"},
    {"order_id": 105, "customer_id": 3, "status": "pending",
     "amount": None, "order_date": "2026-01-20"},
    {"order_id": 106, "customer_id": 4, "status": "paid",
     "amount": Decimal("80.00"), "order_date": "2026-01-21"},
]
customers = [
    {"customer_id": 1, "name": "Asha", "country": "IN"},
    {"customer_id": 2, "name": "Ben", "country": "GB"},
    {"customer_id": 3, "name": "Carla", "country": "US"},
    {"customer_id": 4, "name": "Dev", "country": None},
    {"customer_id": 5, "name": "Omar", "country": "IN"},
]
order_items = [
    {"order_id": 101, "product": "Pen", "qty": 2},
    {"order_id": 101, "product": "Notebook", "qty": 1},
    {"order_id": 102, "product": "Bag", "qty": 1},
    {"order_id": 103, "product": "Lamp", "qty": 1},
    {"order_id": 104, "product": "Pen", "qty": 3},
    {"order_id": 106, "product": "Chair", "qty": 1},
    {"order_id": 106, "product": "Lamp", "qty": 1},
]

print(len(orders), len(customers), len(order_items))
print(orders[0]["order_id"], orders[0]["amount"])

Result · 2 rows

output
6 5 7
101 40.00

Order 105 has no amount yet, and Dev has no country. Omar has no orders. Each of these gaps matters later.

The next sections teach one pattern each, with code and its real output. The last sections cover tests, checks, cost and scale.

02 · The contract

Accept, reject, count

⏱ 6 min · Topic 2 of 19

A good batch transform keeps a count of every row. Each row ends in exactly one place: accepted or rejected. Then the numbers must add up.

This loop splits the orders. An order with no amount is rejected, with a reason:

Split rows and check the countworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

accepted = []
rejected = []
for order in orders:
    if order["amount"] is None:
        rejected.append((order["order_id"], "amount is missing"))
    else:
        accepted.append(order)

print("seen", len(orders), "accepted", len(accepted), "rejected", len(rejected))
print(rejected)
assert len(orders) == len(accepted) + len(rejected)

Result · 2 rows

output
seen 6 accepted 5 rejected 1
[(105, 'amount is missing')]

Order 105 is the only reject. The assert passes because 5 + 1 = 6. If a row were lost, it would stop the job.

You know the reject limit from Validation, Contracts & Error Handling. In a batch, it is a rate: the share of rows rejected.

Here the rate is 1 of 6, about 17 percent. With a limit of 10 percent, the job stops:

Stop when too many rows are rejectedworked example

Python

MAX_REJECT_RATE = 0.10

def split_orders(rows):
    accepted, rejected = [], []
    for row in rows:
        if row["amount"] is None:
            rejected.append((row["order_id"], "amount is missing"))
        else:
            accepted.append(row)
    rate = len(rejected) / len(rows) if rows else 0.0
    if rate > MAX_REJECT_RATE:
        raise ValueError(f"reject rate {rate:.1%} is above {MAX_REJECT_RATE:.0%}")
    return accepted, rejected

try:
    split_orders(orders)
except ValueError as error:
    print(error)

Result · 1 row

output
reject rate 16.7% is above 10%

The function returns both lists. The caller sees the rejects, not only the good rows. An empty batch has rate 0, not a crash.

Watch out

Do not drop a bad row with continue and say nothing. The counts stop adding up, and nobody can explain the missing row.

03 · Row by row

Map and filter

⏱ 6 min · Topic 3 of 19

Filter keeps some rows. Map changes each row. Both work well as list comprehensions.

This one keeps the paid orders:

Filter with a comprehensionworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

paid = [o for o in orders if o["status"] == "paid"]
print([o["order_id"] for o in paid])

summary = [
    {"order_id": o["order_id"], "amount": o["amount"]}
    for o in orders
    if o["status"] == "paid"
]
print(summary[0])
print(sum(o["amount"] for o in paid))

Result · 3 rows

output
[101, 102, 104, 106]
{'order_id': 101, 'amount': Decimal('40.00')}
160.50

Orders 103 and 105 are not paid, so they are out. The second comprehension filters and projects in one step: it keeps two fields only. To project means to keep only some fields of each row.

A map can also change a value. This one builds a label for each order:

Map with a comprehensionworked example

Python

labels = [f'{o["order_id"]}:{o["status"].upper()}' for o in orders]
print(labels)

Result · 1 row

output
['101:PAID', '102:PAID', '103:REFUNDED', '104:PAID', '105:PENDING', '106:PAID']

Every order gives one label. A map never changes the number of rows.

Filter first, project last.

A filter can need a field that the output does not keep. If you project early, that field is gone.

If a comprehension gets hard to read, use a for loop.

04 · Group by

Group with defaultdict

⏱ 5 min · Topic 4 of 19

Group by puts rows into buckets by a key. You know defaultdict and Counter from Records, Collections & Keyed Data. This groups order ids by customer, then counts the statuses:

Buckets and countsworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

from collections import Counter, defaultdict

order_ids_by_customer = defaultdict(list)
for order in orders:
    order_ids_by_customer[order["customer_id"]].append(order["order_id"])
print(dict(order_ids_by_customer))

print(Counter(order["status"] for order in orders))

Result · 2 rows

output
{1: [101, 102], 2: [103], 3: [104, 105], 4: [106]}
Counter({'paid': 4, 'refunded': 1, 'pending': 1})

Customer 5 (Omar) has no orders, so Omar has no bucket. A bucket exists only for a key you saw.

The same pattern can add instead of collect. Use defaultdict(Decimal) to total paid money for each customer:

Total for each keyworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

from collections import defaultdict
from decimal import Decimal

paid_by_customer = defaultdict(Decimal)
for order in orders:
    if order["status"] == "paid":
        paid_by_customer[order["customer_id"]] += order["amount"]
print(dict(paid_by_customer))

Result · 1 row

output
{1: Decimal('65.00'), 3: Decimal('15.50'), 4: Decimal('80.00')}

Asha is 40.00 + 25.00 = 65.00. Ben is missing: Ben’s only order is refunded.

A defaultdict creates a bucket when you only read a key. This changes the number of groups:

Reading a key creates itworked example

Python

from collections import defaultdict

groups = defaultdict(list)
groups[1].append(101)
print(len(groups))
print(groups[5])
print(len(groups))
print(groups.get(6))
print(len(groups))

Result · 5 rows

output
1
[]
2
None
2

Reading groups[5] added a key. The method .get(6) did not. To only look, use .get.

05 · Join

Hash join with a dict

⏱ 11 min · Topic 5 of 19

A hash join has two steps. First, build a dict on the small side, keyed by the join key. Then probe it: for each row of the big side, look up the key.

A dict finds a key by its hash, a number made from the key. That is why this is called a hash join.

The shop has few customers and more orders, so customers is the small side. Every order here has a customer, so all six find a match. Square brackets expect every key to exist.

Later in this section you see what to do when a key is missing. This joins each order to its customer:

Build, then probeworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

customers5 rows

customer_id	name	country
1	Asha	IN
2	Ben	GB
3	Carla	US
4	Dev	None
5	Omar	IN

customer_by_id = {c["customer_id"]: c for c in customers}

joined = []
for order in orders:
    customer = customer_by_id[order["customer_id"]]
    joined.append((order["order_id"], customer["name"], customer["country"]))

for row in joined:
    print(row)

Result · 6 rows

output
(101, 'Asha', 'IN')
(102, 'Asha', 'IN')
(103, 'Ben', 'GB')
(104, 'Carla', 'US')
(105, 'Carla', 'US')
(106, 'Dev', None)

Six orders in, six rows out. Dev has no country, so you get None. Omar has no orders, so Omar is not in the output.

Left join: keep Omar

A left join keeps every row of the left side, even with no match. Here you build on orders, because customers is the side you keep.

Group the orders by customer first. Then use .get with an empty list as the default:

Left join from customersworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

customers5 rows

customer_id	name	country
1	Asha	IN
2	Ben	GB
3	Carla	US
4	Dev	None
5	Omar	IN

from collections import defaultdict

orders_by_customer = defaultdict(list)
for order in orders:
    orders_by_customer[order["customer_id"]].append(order["order_id"])

for customer in customers:
    ids = orders_by_customer.get(customer["customer_id"], [])
    print(customer["name"], ids)

Result · 5 rows

output
Asha [101, 102]
Ben [103]
Carla [104, 105]
Dev [106]
Omar []

Omar stays, with an empty list. In SQL, Omar’s order columns would be NULL.

Unknown keys and repeated keys

Now imagine a new order, 107, for customer 9. Customer 9 is not in customers. Square brackets would raise KeyError.

The method .get lets you choose what to do instead:

An order with an unknown customerworked example

Python

customer_by_id = {c["customer_id"]: c for c in customers}
late_order = {"order_id": 107, "customer_id": 9, "status": "paid",
              "amount": Decimal("12.00"), "order_date": "2026-01-25"}

customer = customer_by_id.get(late_order["customer_id"])
country = customer["country"] if customer else "unknown customer"
print(late_order["order_id"], country)

Result · 1 row

output
107 unknown customer

The order is kept, as in a left join. You could also reject it, as in an inner join. Pick one and write it down.

A dict holds one value for each key. If two customers share an id, the later row silently replaces the earlier one. Guard the build step:

Refuse a repeated keyworked example

Python

def build_index(rows, key):
    index = {}
    for row in rows:
        if row[key] in index:
            raise ValueError(f"duplicate {key}: {row[key]}")
        index[row[key]] = row
    return index

repeated = customers + [{"customer_id": 3, "name": "Carla B", "country": "CA"}]
try:
    build_index(repeated, "customer_id")
except ValueError as error:
    print(error)

Result · 1 row

output
duplicate customer_id: 3

Without the guard, Carla would become "Carla B", and the result would depend on row order.

Interview question

"How would you join these two lists?" Build a dict on the small side and probe it with the big side. Say what a missing key does.

06 · Join bug

The fan-out bug

⏱ 6 min · Topic 6 of 19

You know fan-out from the SQL chapter Joins & Relationship Reasoning. A one-to-many join repeats the one-side row once for each match. If you then sum a one-side column, you count it many times.

Order 101 has two items. Order 106 has two items. This joins paid orders to their items, then sums the order amount:

Join to items, then sum the amountworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

order_items7 rows

order_id	product	qty
101	Pen	2
101	Notebook	1
102	Bag	1
103	Lamp	1
104	Pen	3
106	Chair	1
106	Lamp	1

from collections import defaultdict

items_by_order = defaultdict(list)
for item in order_items:
    items_by_order[item["order_id"]].append(item)

joined = []
for order in orders:
    if order["status"] != "paid":
        continue
    for item in items_by_order.get(order["order_id"], []):
        joined.append({**order, "product": item["product"]})

print(len(joined), "joined rows from", sum(o["status"] == "paid" for o in orders), "paid orders")
print(sum(row["amount"] for row in joined))

Result · 2 rows

output
6 joined rows from 4 paid orders
280.50

Orders 101 and 106 appear twice. So 40.00 and 80.00 are counted twice: 280.50 instead of 160.50.

The right answer sums the amount with one row for each order, before any join. This is called the order grain. A paid order is counted once, so the total is 160.50:

Sum before the joinworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

paid_orders = [o for o in orders if o["status"] == "paid"]
print(sum(o["amount"] for o in paid_orders))

Result · 1 row

output
160.50

40.00 + 25.00 + 15.50 + 80.00 = 160.50.

To catch fan-out in a pipeline, compare the row count before and after a join. If you expected one row per order, the counts must match. This guard fails on the joined list above:

A row-count guardworked example

Python

paid_orders = [o for o in orders if o["status"] == "paid"]

assert len(joined) == len(paid_orders), "join changed the row count"

Result · 1 row

last line of the error
AssertionError: join changed the row count

The guard stops the job at the join. Without it, 280.50 would flow into a report.

07 · Report

Totals by country

⏱ 4 min · Topic 7 of 19

An aggregation turns many rows into a few report rows. First name the grain: one report row for each country. Then choose what to keep for each report row: a running sum and a count.

This joins paid orders to their customer, then totals the money for each country. A missing country becomes "unknown":

Paid revenue by countryworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

customers5 rows

customer_id	name	country
1	Asha	IN
2	Ben	GB
3	Carla	US
4	Dev	None
5	Omar	IN

from collections import defaultdict
from decimal import Decimal

customer_by_id = {c["customer_id"]: c for c in customers}
revenue = defaultdict(Decimal)
order_count = defaultdict(int)

for order in orders:
    if order["status"] != "paid":
        continue
    country = customer_by_id[order["customer_id"]]["country"] or "unknown"
    revenue[country] += order["amount"]
    order_count[country] += 1

report = [
    {"country": country, "orders": order_count[country], "revenue": revenue[country]}
    for country in sorted(revenue)
]
for row in report:
    print(row)

Result · 3 rows

output
{'country': 'IN', 'orders': 2, 'revenue': Decimal('65.00')}
{'country': 'US', 'orders': 1, 'revenue': Decimal('15.50')}
{'country': 'unknown', 'orders': 1, 'revenue': Decimal('80.00')}

IN is Asha (40.00 + 25.00), and US is Carla. Dev has no country, so Dev’s 80.00 is "unknown". The total is 160.50, the same as before.

Sort the report rows. A sorted report gives the same output on every run, so a test can compare it. Check that the report total equals the total you started with.

08 · Reshape

Pivot long to wide

⏱ 6 min · Topic 8 of 19

A pivot turns values of one field into columns. A long table has one row for each fact. A wide table puts facts side by side as columns.

Here the orders are long: one row for each order. The wide table has one row for each customer with orders, and one column for each status.

First count each (customer, status) pair with a Counter. Then build one dict for each customer. The order of the columns comes from your own list, not from the data:

Count orders by customer and statusworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

from collections import Counter

statuses = ["paid", "refunded", "pending"]
counts = Counter((o["customer_id"], o["status"]) for o in orders)
print(counts[(1, "paid")], counts[(1, "refunded")])

wide = []
for customer_id in sorted({o["customer_id"] for o in orders}):
    row = {"customer_id": customer_id}
    for status in statuses:
        row[status] = counts.get((customer_id, status), 0)
    wide.append(row)

for row in wide:
    print(row)

Result · 5 rows

output
2 0
{'customer_id': 1, 'paid': 2, 'refunded': 0, 'pending': 0}
{'customer_id': 2, 'paid': 0, 'refunded': 1, 'pending': 0}
{'customer_id': 3, 'paid': 1, 'refunded': 0, 'pending': 1}
{'customer_id': 4, 'paid': 1, 'refunded': 0, 'pending': 0}

Customer 3 has one paid and one pending order. A pair that never happened, like (1, "refunded"), becomes 0.

A fixed list has a risk. A new status, like "cancelled", has no column, so its rows are lost with no error. Check for statuses you did not expect:

Fail on an unknown statusworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

unknown = {status for (_, status) in counts} - set(statuses)
if unknown:
    raise ValueError(f"unknown statuses: {sorted(unknown)}")
print("no unknown statuses:", sorted(unknown))

Result · 1 row

output
no unknown statuses: []

This continues from the code above. On the shop data it raises nothing, because every status is in the list. A new status would raise the error.

Watch out

Decide what an empty cell means. For counts, 0 is right. For amounts, 0.00 and "no data" are different facts.

09 · Dedupe

Dedupe, keep the latest

⏱ 6 min · Topic 9 of 19

Dedupe keeps one row for each business key. A business key is the id of one real thing, like order_id.

You must choose which row wins. The usual rule is the latest update, with a version number to break ties.

The shop has no repeated orders. So here is a small feed of status changes, called order_updates. Order 105 has three rows, and two of them share one time:

Keep the winner for each orderworked example

Python

Input data

order_updates5 rows

order_id	status	updated_at	version
103	paid	2026-01-11T09:00	1
105	pending	2026-01-20T09:00	1
103	refunded	2026-01-12T14:00	2
105	paid	2026-01-22T10:00	2
105	cancelled	2026-01-22T10:00	3

order_updates = [
    {"order_id": 103, "status": "paid", "updated_at": "2026-01-11T09:00", "version": 1},
    {"order_id": 105, "status": "pending", "updated_at": "2026-01-20T09:00", "version": 1},
    {"order_id": 103, "status": "refunded", "updated_at": "2026-01-12T14:00", "version": 2},
    {"order_id": 105, "status": "paid", "updated_at": "2026-01-22T10:00", "version": 2},
    {"order_id": 105, "status": "cancelled", "updated_at": "2026-01-22T10:00", "version": 3},
]

def latest_per_key(rows, key):
    winners = {}
    for row in rows:
        rank = (row["updated_at"], row["version"])
        current = winners.get(row[key])
        if current is None or rank > (current["updated_at"], current["version"]):
            winners[row[key]] = row
    return winners

winners = latest_per_key(order_updates, "order_id")
for order_id in sorted(winners):
    print(order_id, winners[order_id]["status"])

backwards = latest_per_key(reversed(order_updates), "order_id")
print(backwards == winners)

Result · 3 rows

output
103 refunded
105 cancelled
True

Order 103: the later time wins. Order 105: two rows tie on time, so version 3 wins. The last line shows that reading the rows in reverse gives the same winners.

The rank is a tuple: (updated_at, version). Python compares tuples one part at a time.

Time text like "2026-01-22T10:00" sorts in time order only when every value has the same format and time zone. Otherwise, parse it into a datetime first.

Watch out

If you only compare updated_at, a tie keeps whichever row came first. With this file order, order 105 gets "paid", which is wrong. Read the rows in reverse and you get "cancelled", so the answer depends on file order.

10 · Sort and scan

Sort, then scan once

⏱ 5 min · Topic 10 of 19

Sorting turns many questions into one pass. Sort by the key, then by time. Then walk the rows, and the last row seen for each key is the latest.

This finds the latest order of each customer. The dict is overwritten each time, so the final value is the last row in sorted order:

Latest order for each customerworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

ordered = sorted(orders, key=lambda o: (o["customer_id"], o["order_date"], o["order_id"]))

latest_by_customer = {}
for order in ordered:
    latest_by_customer[order["customer_id"]] = order

for customer_id, order in latest_by_customer.items():
    print(customer_id, order["order_id"], order["order_date"])

Result · 4 rows

output
1 102 2026-01-10
2 103 2026-01-11
3 105 2026-01-20
4 106 2026-01-21

Asha has orders 101 and 102. Order 102 is later, so it wins. Carla's latest is 105, the pending order.

The dedupe loop in the last section solves a similar problem. Use that loop when you need only the winners. Use the sort when other steps also need the order.

For this dict, a sort by date alone also works. Put customer_id first when you need each customer's rows together, for example to write one customer at a time.

Watch out

Two orders of one customer can share a date. Then the winner depends on the input order. Add order_id last in the sort key, so a tie always has the same winner.

11 · Window-like

Running totals and previous row

⏱ 4 min · Topic 11 of 19

A SQL window function looks at nearby rows in an order. In Python, you sort the rows, then carry a little state for each key. State is a value you update as you go.

This prints one line for each paid order. The columns are: order_id, customer_id, row number, previous amount, running total. All three window values are per customer:

Row number, previous amount, running totalworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

from collections import defaultdict
from decimal import Decimal

paid = [o for o in orders if o["status"] == "paid"]
ordered = sorted(paid, key=lambda o: (o["customer_id"], o["order_date"], o["order_id"]))

row_number = defaultdict(int)
running = defaultdict(Decimal)
previous = {}

for order in ordered:
    cid = order["customer_id"]
    row_number[cid] += 1
    running[cid] += order["amount"]
    print(order["order_id"], cid, row_number[cid], previous.get(cid), running[cid])
    previous[cid] = order["amount"]

Result · 4 rows

output
101 1 1 None 40.00
102 1 2 40.00 65.00
104 3 1 None 15.50
106 4 1 None 80.00

Asha's second order, 102, sees the previous amount 40.00. Its running total is 40.00 + 25.00 = 65.00. A customer's first order has previous None.

The state is small: three values for each customer. The rows must be sorted first. If they are not, the running total changes with the input order.

12 · Ordering

Sort keys and tie-breaks

⏱ 6 min · Topic 12 of 19

Python sort is stable: equal rows keep the order they arrived in. But rows from a set, a parallel read or a list of files arrive in no order you chose. So a tie must be broken by the key itself.

Look at the Lamp rows. Two items tie on product. Sort by product alone, then sort the same rows read in reverse:

A tie with no tie-breakworked example

Python

Input data

order_items7 rows

order_id	product	qty
101	Pen	2
101	Notebook	1
102	Bag	1
103	Lamp	1
104	Pen	3
106	Chair	1
106	Lamp	1

by_product = lambda item: item["product"]

as_read = sorted(order_items, key=by_product)
print([(i["product"], i["order_id"]) for i in as_read if i["product"] == "Lamp"])

reread = sorted(reversed(order_items), key=by_product)
print([(i["product"], i["order_id"]) for i in reread if i["product"] == "Lamp"])

Result · 2 rows

output
[('Lamp', 103), ('Lamp', 106)]
[('Lamp', 106), ('Lamp', 103)]

The same data gives two different orders. Nothing failed, but a report built on this would change between runs.

The fix is a tuple key that ends in something unique. To sort one part high-to-low, put a minus sign on a number. This sorts by product, then by qty high-to-low, then by order_id:

A key with no tiesworked example

Python

Input data

order_items7 rows

order_id	product	qty
101	Pen	2
101	Notebook	1
102	Bag	1
103	Lamp	1
104	Pen	3
106	Chair	1
106	Lamp	1

def total_order(item):
    return (item["product"], -item["qty"], item["order_id"])

for seed in (order_items, list(reversed(order_items))):
    ranked = sorted(seed, key=total_order)
    print([(i["product"], i["qty"], i["order_id"]) for i in ranked if i["product"] in ("Lamp", "Pen")])

Result · 2 rows

output
[('Lamp', 1, 103), ('Lamp', 1, 106), ('Pen', 3, 104), ('Pen', 2, 101)]
[('Lamp', 1, 103), ('Lamp', 1, 106), ('Pen', 3, 104), ('Pen', 2, 101)]

Both inputs give the same list. Pen 104 (qty 3) comes before Pen 101 (qty 2) because of the minus sign.

If ids come from a CSV file, they are text, and "10" sorts before "9". Turn them into int in the key, for example int(row["order_id"]).

Watch out

You cannot compare None with a number. Sorting the orders by amount fails on order 105. Filter out None first, or put a flag in the key: (amount is None, amount).

13 · Top k

Top k with a heap

⏱ 6 min · Topic 13 of 19

A heap is a list that keeps its smallest value easy to find. For the top k rows (k is how many rows you want, like 2), you do not need a full sort.

heapq.nlargest keeps only k rows at a time. This finds the two largest paid orders:

Top two paid ordersworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

import heapq

paid = [o for o in orders if o["status"] == "paid"]
top2 = heapq.nlargest(2, paid, key=lambda o: (o["amount"], -o["order_id"]))
print([(o["order_id"], o["amount"]) for o in top2])

Result · 1 row

output
[(106, Decimal('80.00')), (101, Decimal('40.00'))]

The key has an order_id tie-break, so equal amounts also give a fixed result.

You can also keep the heap yourself, as rows stream past. Memory then depends on k, not on the number of rows.

Push each row. When the heap has 2 rows, heappushpop adds the new row and removes the smallest:

A heap of two, over a streamworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

import heapq

top = []
for order in orders:
    if order["status"] != "paid":
        continue
    entry = (order["amount"], order["order_id"])
    if len(top) < 2:
        heapq.heappush(top, entry)
    else:
        heapq.heappushpop(top, entry)

print(sorted(top, reverse=True))
print(len(top))

Result · 2 rows

output
[(Decimal('80.00'), 106), (Decimal('40.00'), 101)]
2

The paid amounts arrive as 40.00, 25.00, 15.50, 80.00. The heap never holds more than 2 rows. Order 102 (25.00) is pushed out by 80.00.

On a tie, this heap keeps the larger order_id. The nlargest call above keeps the smaller one. Use one rule in both places.

The cost is O(n log k), and a full sort costs O(n log n). Here n is the number of rows; the last section explains this notation. When k is small and n is large, the heap is much cheaper, and it fits in memory.

14 · Structure

A pipeline of small functions

⏱ 5 min · Topic 14 of 19

Write each step as a small function. A step takes rows in and gives rows out.

You know generators from Iterators, Generators & Streaming Data. A generator step passes one row at a time to the next step.

This pipeline has three steps: keep paid orders, add the country, total by country. The last function, revenue_by_country, connects the steps:

Three steps and one functionworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

customers5 rows

customer_id	name	country
1	Asha	IN
2	Ben	GB
3	Carla	US
4	Dev	None
5	Omar	IN

from collections import defaultdict
from decimal import Decimal

def only_paid(rows):
    return (row for row in rows if row["status"] == "paid")

def add_country(rows, customer_by_id):
    for row in rows:
        customer = customer_by_id.get(row["customer_id"])
        country = customer["country"] if customer else None
        yield {**row, "country": country or "unknown"}

def total_by_country(rows):
    totals = defaultdict(Decimal)
    for row in rows:
        totals[row["country"]] += row["amount"]
    return dict(sorted(totals.items()))

def revenue_by_country(orders, customers):
    customer_by_id = {c["customer_id"]: c for c in customers}
    return total_by_country(add_country(only_paid(orders), customer_by_id))

print(revenue_by_country(orders, customers))

Result · 1 row

output
{'IN': Decimal('65.00'), 'US': Decimal('15.50'), 'unknown': Decimal('80.00')}

The result matches the report from the totals section. The first two steps are lazy: they read no row until total_by_country asks for it.

Each step has one job and one test. The join table is built once, outside the loop. A generator can be read only once, so do not reuse a step result twice.

15 · Testing

Test with small fixtures

⏱ 5 min · Topic 15 of 19

A fixture is a tiny input you write by hand. You know exactly what the right answer is. Because the transform is a small function, each test needs only a few rows.

Here a fixture means test data, not a pytest fixture.

These tests use revenue_by_country from the last section. They cover a refunded order, an unknown customer and empty input. A test is a function that uses assert:

Three small testsworked example

Python

def make_order(order_id, customer_id, status, amount):
    return {"order_id": order_id, "customer_id": customer_id,
            "status": status, "amount": Decimal(amount)}

def test_only_paid_orders_count():
    rows = [make_order(1, 1, "paid", "10.00"), make_order(2, 1, "refunded", "5.00")]
    people = [{"customer_id": 1, "country": "IN"}]
    assert revenue_by_country(rows, people) == {"IN": Decimal("10.00")}

def test_unknown_customer_goes_to_unknown():
    rows = [make_order(1, 9, "paid", "7.00")]
    assert revenue_by_country(rows, []) == {"unknown": Decimal("7.00")}

def test_empty_input_gives_empty_report():
    assert revenue_by_country([], []) == {}

for test in (test_only_paid_orders_count, test_unknown_customer_goes_to_unknown,
             test_empty_input_gives_empty_report):
    test()
    print("ok", test.__name__)

Result · 3 rows

output
ok test_only_paid_orders_count
ok test_unknown_customer_goes_to_unknown
ok test_empty_input_gives_empty_report

Each test runs on its own rows, not on the whole shop. A failing test points at one rule.

Choose fixtures that hit the edges of the data: an empty batch, a missing key, a repeated key, a None amount.

Compare the whole output with ==. A dict is equal in any order. A list is not, so sort a list first.

16 · Batch checks

Checks that see the whole batch

⏱ 5 min · Topic 16 of 19

Some checks need the whole batch at once: repeated ids, items with no order, customers with no orders. A Counter and set arithmetic do most of the work.

This runs five checks on the shop. Set subtraction a - b gives the values that are in a but not in b:

Five whole-batch checksworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

customers5 rows

customer_id	name	country
1	Asha	IN
2	Ben	GB
3	Carla	US
4	Dev	None
5	Omar	IN

order_items7 rows

order_id	product	qty
101	Pen	2
101	Notebook	1
102	Bag	1
103	Lamp	1
104	Pen	3
106	Chair	1
106	Lamp	1

from collections import Counter

order_counts = Counter(o["order_id"] for o in orders)
repeated_ids = [oid for oid, n in order_counts.items() if n > 1]
print("repeated order ids:", repeated_ids)

order_ids = {o["order_id"] for o in orders}
item_ids = {i["order_id"] for i in order_items}
print("items with no order:", sorted(item_ids - order_ids))
print("orders with no items:", sorted(order_ids - item_ids))

customer_ids = {c["customer_id"] for c in customers}
buyer_ids = {o["customer_id"] for o in orders}
print("orders with no customer:", sorted(buyer_ids - customer_ids))
print("customers with no orders:", sorted(customer_ids - buyer_ids))

Result · 5 rows

output
repeated order ids: []
items with no order: []
orders with no items: [105]
orders with no customer: []
customers with no orders: [5]

Order 105 has no items because it is still pending. Omar (5) has no orders. Both are normal here, but a check makes them visible.

Decide for each check: a warning, a reject, or a stop. "Items with no order" should usually stop the job. "Customers with no orders" is only information.

In a real job, return the results as a dict, for example {"orders with no items": [105]}. Then the caller makes that choice for each check.

17 · Scale

Cost, scale and when to switch

⏱ 9 min · Topic 17 of 19

Cost is how the work grows when the input grows. Write n for the rows of the big side, and m for the rows of the small side.

O(n) means the work grows at the same rate as n: twice the rows, twice the work. This table shows each pattern:

How each pattern grows

Pattern	Cost	In plain words
Map, filter	O(n)	One look at each row.
Group by, aggregate, pivot	O(n)	One look at each row, one dict update each.
Hash join	O(n + m)	Build the small side once, probe once for each big row.
Nested-loop join	O(n · m)	Compare every big row with every small row.
Dedupe latest	O(n)	One dict, one comparison for each row.
Sort, then scan	O(n log n)	The sort costs most. The scan is one pass.
Top k with a heap	O(n log k)	Keep only k rows. Cheaper than a full sort when k is small.

Count the work on the shop. The nested loop compares every order with every customer. The hash join builds once and looks up once for each order:

Count the steps of two joinsworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

customers5 rows

customer_id	name	country
1	Asha	IN
2	Ben	GB
3	Carla	US
4	Dev	None
5	Omar	IN

checks = 0
matches = []
for order in orders:
    for customer in customers:
        checks += 1
        if order["customer_id"] == customer["customer_id"]:
            matches.append((order["order_id"], customer["name"]))
print("nested loop checks:", checks, "matches:", len(matches))

lookups = 0
customer_by_id = {c["customer_id"]: c for c in customers}
for order in orders:
    lookups += 1
    customer_by_id[order["customer_id"]]
print("hash join steps:", len(customers), "to build +", lookups, "lookups")

Result · 2 rows

output
nested loop checks: 30 matches: 6
hash join steps: 5 to build + 6 lookups

6 orders times 5 customers is 30 checks. The hash join needs 5 + 6 = 11 steps. Both find the same 6 matches.

The gap grows fast. With 10,000,000 orders and 1,000,000 customers, the nested loop is n times m. The hash join is n plus m:

The same count at scaleworked example

Python

n, m = 10_000_000, 1_000_000
print(f"{n * m:,}")
print(f"{n + m:,}")

Result · 2 rows

output
10,000,000,000,000
11,000,000

Ten trillion steps against eleven million. This is why you use a dict for a join on equal keys. Use a nested loop only for a condition a dict cannot look up, like a date range.

Memory is the next limit. The dict on the small side must fit in memory. The big side does not: read it as a generator, one row at a time.

A sort keeps every row in memory. A group-by dict keeps one entry for each key.

When the small side no longer fits, move the work. Split both sides by key into parts that fit, or sort both sides and merge them. Or use SQL or Spark, which do this for you.

Scaling Python & Interview Capstone shows the full interview flow.

Interview question

"Now the input is 100 times bigger. What changes?" Name what grows in memory, stream the big side and keep the small dict. Say when you would move to SQL or Spark.

Openingloading the content…

Batch

Pure Python Batch Transform Patterns

Use map/filter/reduce-style flows, in-memory joins, aggregations, stateful scans, and sorted-window logic.

⏱ 24 min readTopics chapter readerLevel · Intermediate

01 · Overview

Batch transforms in pure Python

⏱ 5 min · Topic 1 of 19

The senior Python round asks for this. You write a clean transform, then you scale it and explain the good and bad sides of each choice. This chapter gives you the patterns for both steps.

Here is the shop again, as Python data. Money is Decimal, as you learned in Types, Time, Nulls & Numeric Correctness. Most examples in this chapter start from these three lists:

The shop as three lists of dictsworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

customers5 rows

customer_id	name	country
1	Asha	IN
2	Ben	GB
3	Carla	US
4	Dev	None
5	Omar	IN

order_items7 rows

order_id	product	qty
101	Pen	2
101	Notebook	1
102	Bag	1
103	Lamp	1
104	Pen	3
106	Chair	1
106	Lamp	1

from decimal import Decimal

orders = [
    {"order_id": 101, "customer_id": 1, "status": "paid",
     "amount": Decimal("40.00"), "order_date": "2026-01-03"},
    {"order_id": 102, "customer_id": 1, "status": "paid",
     "amount": Decimal("25.00"), "order_date": "2026-01-10"},
    {"order_id": 103, "customer_id": 2, "status": "refunded",
     "amount": Decimal("60.00"), "order_date": "2026-01-11"},
    {"order_id": 104, "customer_id": 3, "status": "paid",
     "amount": Decimal("15.50"), "order_date": "2026-01-15"},
    {"order_id": 105, "customer_id": 3, "status": "pending",
     "amount": None, "order_date": "2026-01-20"},
    {"order_id": 106, "customer_id": 4, "status": "paid",
     "amount": Decimal("80.00"), "order_date": "2026-01-21"},
]
customers = [
    {"customer_id": 1, "name": "Asha", "country": "IN"},
    {"customer_id": 2, "name": "Ben", "country": "GB"},
    {"customer_id": 3, "name": "Carla", "country": "US"},
    {"customer_id": 4, "name": "Dev", "country": None},
    {"customer_id": 5, "name": "Omar", "country": "IN"},
]
order_items = [
    {"order_id": 101, "product": "Pen", "qty": 2},
    {"order_id": 101, "product": "Notebook", "qty": 1},
    {"order_id": 102, "product": "Bag", "qty": 1},
    {"order_id": 103, "product": "Lamp", "qty": 1},
    {"order_id": 104, "product": "Pen", "qty": 3},
    {"order_id": 106, "product": "Chair", "qty": 1},
    {"order_id": 106, "product": "Lamp", "qty": 1},
]

print(len(orders), len(customers), len(order_items))
print(orders[0]["order_id"], orders[0]["amount"])

Result · 2 rows

output
6 5 7
101 40.00

Order 105 has no amount yet, and Dev has no country. Omar has no orders. Each of these gaps matters later.

The next sections teach one pattern each, with code and its real output. The last sections cover tests, checks, cost and scale.

02 · The contract

Accept, reject, count

⏱ 6 min · Topic 2 of 19

A good batch transform keeps a count of every row. Each row ends in exactly one place: accepted or rejected. Then the numbers must add up.

This loop splits the orders. An order with no amount is rejected, with a reason:

Split rows and check the countworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

accepted = []
rejected = []
for order in orders:
    if order["amount"] is None:
        rejected.append((order["order_id"], "amount is missing"))
    else:
        accepted.append(order)

print("seen", len(orders), "accepted", len(accepted), "rejected", len(rejected))
print(rejected)
assert len(orders) == len(accepted) + len(rejected)

Result · 2 rows

output
seen 6 accepted 5 rejected 1
[(105, 'amount is missing')]

Order 105 is the only reject. The assert passes because 5 + 1 = 6. If a row were lost, it would stop the job.

You know the reject limit from Validation, Contracts & Error Handling. In a batch, it is a rate: the share of rows rejected.

Here the rate is 1 of 6, about 17 percent. With a limit of 10 percent, the job stops:

Stop when too many rows are rejectedworked example

Python

MAX_REJECT_RATE = 0.10

def split_orders(rows):
    accepted, rejected = [], []
    for row in rows:
        if row["amount"] is None:
            rejected.append((row["order_id"], "amount is missing"))
        else:
            accepted.append(row)
    rate = len(rejected) / len(rows) if rows else 0.0
    if rate > MAX_REJECT_RATE:
        raise ValueError(f"reject rate {rate:.1%} is above {MAX_REJECT_RATE:.0%}")
    return accepted, rejected

try:
    split_orders(orders)
except ValueError as error:
    print(error)

Result · 1 row

output
reject rate 16.7% is above 10%

The function returns both lists. The caller sees the rejects, not only the good rows. An empty batch has rate 0, not a crash.

Watch out

Do not drop a bad row with continue and say nothing. The counts stop adding up, and nobody can explain the missing row.

03 · Row by row

Map and filter

⏱ 6 min · Topic 3 of 19

Filter keeps some rows. Map changes each row. Both work well as list comprehensions.

This one keeps the paid orders:

Filter with a comprehensionworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

paid = [o for o in orders if o["status"] == "paid"]
print([o["order_id"] for o in paid])

summary = [
    {"order_id": o["order_id"], "amount": o["amount"]}
    for o in orders
    if o["status"] == "paid"
]
print(summary[0])
print(sum(o["amount"] for o in paid))

Result · 3 rows

output
[101, 102, 104, 106]
{'order_id': 101, 'amount': Decimal('40.00')}
160.50

Orders 103 and 105 are not paid, so they are out. The second comprehension filters and projects in one step: it keeps two fields only. To project means to keep only some fields of each row.

A map can also change a value. This one builds a label for each order:

Map with a comprehensionworked example

Python

labels = [f'{o["order_id"]}:{o["status"].upper()}' for o in orders]
print(labels)

Result · 1 row

output
['101:PAID', '102:PAID', '103:REFUNDED', '104:PAID', '105:PENDING', '106:PAID']

Every order gives one label. A map never changes the number of rows.

Filter first, project last.

A filter can need a field that the output does not keep. If you project early, that field is gone.

If a comprehension gets hard to read, use a for loop.

04 · Group by

Group with defaultdict

⏱ 5 min · Topic 4 of 19

Group by puts rows into buckets by a key. You know defaultdict and Counter from Records, Collections & Keyed Data. This groups order ids by customer, then counts the statuses:

Buckets and countsworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

from collections import Counter, defaultdict

order_ids_by_customer = defaultdict(list)
for order in orders:
    order_ids_by_customer[order["customer_id"]].append(order["order_id"])
print(dict(order_ids_by_customer))

print(Counter(order["status"] for order in orders))

Result · 2 rows

output
{1: [101, 102], 2: [103], 3: [104, 105], 4: [106]}
Counter({'paid': 4, 'refunded': 1, 'pending': 1})

Customer 5 (Omar) has no orders, so Omar has no bucket. A bucket exists only for a key you saw.

The same pattern can add instead of collect. Use defaultdict(Decimal) to total paid money for each customer:

Total for each keyworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

from collections import defaultdict
from decimal import Decimal

paid_by_customer = defaultdict(Decimal)
for order in orders:
    if order["status"] == "paid":
        paid_by_customer[order["customer_id"]] += order["amount"]
print(dict(paid_by_customer))

Result · 1 row

output
{1: Decimal('65.00'), 3: Decimal('15.50'), 4: Decimal('80.00')}

Asha is 40.00 + 25.00 = 65.00. Ben is missing: Ben’s only order is refunded.

A defaultdict creates a bucket when you only read a key. This changes the number of groups:

Reading a key creates itworked example

Python

from collections import defaultdict

groups = defaultdict(list)
groups[1].append(101)
print(len(groups))
print(groups[5])
print(len(groups))
print(groups.get(6))
print(len(groups))

Result · 5 rows

output
1
[]
2
None
2

Reading groups[5] added a key. The method .get(6) did not. To only look, use .get.

05 · Join

Hash join with a dict

⏱ 11 min · Topic 5 of 19

A hash join has two steps. First, build a dict on the small side, keyed by the join key. Then probe it: for each row of the big side, look up the key.

A dict finds a key by its hash, a number made from the key. That is why this is called a hash join.

The shop has few customers and more orders, so customers is the small side. Every order here has a customer, so all six find a match. Square brackets expect every key to exist.

Later in this section you see what to do when a key is missing. This joins each order to its customer:

Build, then probeworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

customers5 rows

customer_id	name	country
1	Asha	IN
2	Ben	GB
3	Carla	US
4	Dev	None
5	Omar	IN

customer_by_id = {c["customer_id"]: c for c in customers}

joined = []
for order in orders:
    customer = customer_by_id[order["customer_id"]]
    joined.append((order["order_id"], customer["name"], customer["country"]))

for row in joined:
    print(row)

Result · 6 rows

output
(101, 'Asha', 'IN')
(102, 'Asha', 'IN')
(103, 'Ben', 'GB')
(104, 'Carla', 'US')
(105, 'Carla', 'US')
(106, 'Dev', None)

Six orders in, six rows out. Dev has no country, so you get None. Omar has no orders, so Omar is not in the output.

Left join: keep Omar

A left join keeps every row of the left side, even with no match. Here you build on orders, because customers is the side you keep.

Group the orders by customer first. Then use .get with an empty list as the default:

Left join from customersworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

customers5 rows

customer_id	name	country
1	Asha	IN
2	Ben	GB
3	Carla	US
4	Dev	None
5	Omar	IN

from collections import defaultdict

orders_by_customer = defaultdict(list)
for order in orders:
    orders_by_customer[order["customer_id"]].append(order["order_id"])

for customer in customers:
    ids = orders_by_customer.get(customer["customer_id"], [])
    print(customer["name"], ids)

Result · 5 rows

output
Asha [101, 102]
Ben [103]
Carla [104, 105]
Dev [106]
Omar []

Omar stays, with an empty list. In SQL, Omar’s order columns would be NULL.

Unknown keys and repeated keys

Now imagine a new order, 107, for customer 9. Customer 9 is not in customers. Square brackets would raise KeyError.

The method .get lets you choose what to do instead:

An order with an unknown customerworked example

Python

customer_by_id = {c["customer_id"]: c for c in customers}
late_order = {"order_id": 107, "customer_id": 9, "status": "paid",
              "amount": Decimal("12.00"), "order_date": "2026-01-25"}

customer = customer_by_id.get(late_order["customer_id"])
country = customer["country"] if customer else "unknown customer"
print(late_order["order_id"], country)

Result · 1 row

output
107 unknown customer

The order is kept, as in a left join. You could also reject it, as in an inner join. Pick one and write it down.

A dict holds one value for each key. If two customers share an id, the later row silently replaces the earlier one. Guard the build step:

Refuse a repeated keyworked example

Python

def build_index(rows, key):
    index = {}
    for row in rows:
        if row[key] in index:
            raise ValueError(f"duplicate {key}: {row[key]}")
        index[row[key]] = row
    return index

repeated = customers + [{"customer_id": 3, "name": "Carla B", "country": "CA"}]
try:
    build_index(repeated, "customer_id")
except ValueError as error:
    print(error)

Result · 1 row

output
duplicate customer_id: 3

Without the guard, Carla would become "Carla B", and the result would depend on row order.

Interview question

"How would you join these two lists?" Build a dict on the small side and probe it with the big side. Say what a missing key does.

06 · Join bug

The fan-out bug

⏱ 6 min · Topic 6 of 19

You know fan-out from the SQL chapter Joins & Relationship Reasoning. A one-to-many join repeats the one-side row once for each match. If you then sum a one-side column, you count it many times.

Order 101 has two items. Order 106 has two items. This joins paid orders to their items, then sums the order amount:

Join to items, then sum the amountworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

order_items7 rows

order_id	product	qty
101	Pen	2
101	Notebook	1
102	Bag	1
103	Lamp	1
104	Pen	3
106	Chair	1
106	Lamp	1

from collections import defaultdict

items_by_order = defaultdict(list)
for item in order_items:
    items_by_order[item["order_id"]].append(item)

joined = []
for order in orders:
    if order["status"] != "paid":
        continue
    for item in items_by_order.get(order["order_id"], []):
        joined.append({**order, "product": item["product"]})

print(len(joined), "joined rows from", sum(o["status"] == "paid" for o in orders), "paid orders")
print(sum(row["amount"] for row in joined))

Result · 2 rows

output
6 joined rows from 4 paid orders
280.50

Orders 101 and 106 appear twice. So 40.00 and 80.00 are counted twice: 280.50 instead of 160.50.

The right answer sums the amount with one row for each order, before any join. This is called the order grain. A paid order is counted once, so the total is 160.50:

Sum before the joinworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

paid_orders = [o for o in orders if o["status"] == "paid"]
print(sum(o["amount"] for o in paid_orders))

Result · 1 row

output
160.50

40.00 + 25.00 + 15.50 + 80.00 = 160.50.

To catch fan-out in a pipeline, compare the row count before and after a join. If you expected one row per order, the counts must match. This guard fails on the joined list above:

A row-count guardworked example

Python

paid_orders = [o for o in orders if o["status"] == "paid"]

assert len(joined) == len(paid_orders), "join changed the row count"

Result · 1 row

last line of the error
AssertionError: join changed the row count

The guard stops the job at the join. Without it, 280.50 would flow into a report.

07 · Report

Totals by country

⏱ 4 min · Topic 7 of 19

An aggregation turns many rows into a few report rows. First name the grain: one report row for each country. Then choose what to keep for each report row: a running sum and a count.

This joins paid orders to their customer, then totals the money for each country. A missing country becomes "unknown":

Paid revenue by countryworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

customers5 rows

customer_id	name	country
1	Asha	IN
2	Ben	GB
3	Carla	US
4	Dev	None
5	Omar	IN

from collections import defaultdict
from decimal import Decimal

customer_by_id = {c["customer_id"]: c for c in customers}
revenue = defaultdict(Decimal)
order_count = defaultdict(int)

for order in orders:
    if order["status"] != "paid":
        continue
    country = customer_by_id[order["customer_id"]]["country"] or "unknown"
    revenue[country] += order["amount"]
    order_count[country] += 1

report = [
    {"country": country, "orders": order_count[country], "revenue": revenue[country]}
    for country in sorted(revenue)
]
for row in report:
    print(row)

Result · 3 rows

output
{'country': 'IN', 'orders': 2, 'revenue': Decimal('65.00')}
{'country': 'US', 'orders': 1, 'revenue': Decimal('15.50')}
{'country': 'unknown', 'orders': 1, 'revenue': Decimal('80.00')}

IN is Asha (40.00 + 25.00), and US is Carla. Dev has no country, so Dev’s 80.00 is "unknown". The total is 160.50, the same as before.

Sort the report rows. A sorted report gives the same output on every run, so a test can compare it. Check that the report total equals the total you started with.

08 · Reshape

Pivot long to wide

⏱ 6 min · Topic 8 of 19

A pivot turns values of one field into columns. A long table has one row for each fact. A wide table puts facts side by side as columns.

Here the orders are long: one row for each order. The wide table has one row for each customer with orders, and one column for each status.

First count each (customer, status) pair with a Counter. Then build one dict for each customer. The order of the columns comes from your own list, not from the data:

Count orders by customer and statusworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

from collections import Counter

statuses = ["paid", "refunded", "pending"]
counts = Counter((o["customer_id"], o["status"]) for o in orders)
print(counts[(1, "paid")], counts[(1, "refunded")])

wide = []
for customer_id in sorted({o["customer_id"] for o in orders}):
    row = {"customer_id": customer_id}
    for status in statuses:
        row[status] = counts.get((customer_id, status), 0)
    wide.append(row)

for row in wide:
    print(row)

Result · 5 rows

output
2 0
{'customer_id': 1, 'paid': 2, 'refunded': 0, 'pending': 0}
{'customer_id': 2, 'paid': 0, 'refunded': 1, 'pending': 0}
{'customer_id': 3, 'paid': 1, 'refunded': 0, 'pending': 1}
{'customer_id': 4, 'paid': 1, 'refunded': 0, 'pending': 0}

Customer 3 has one paid and one pending order. A pair that never happened, like (1, "refunded"), becomes 0.

A fixed list has a risk. A new status, like "cancelled", has no column, so its rows are lost with no error. Check for statuses you did not expect:

Fail on an unknown statusworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

unknown = {status for (_, status) in counts} - set(statuses)
if unknown:
    raise ValueError(f"unknown statuses: {sorted(unknown)}")
print("no unknown statuses:", sorted(unknown))

Result · 1 row

output
no unknown statuses: []

This continues from the code above. On the shop data it raises nothing, because every status is in the list. A new status would raise the error.

Watch out

Decide what an empty cell means. For counts, 0 is right. For amounts, 0.00 and "no data" are different facts.

09 · Dedupe

Dedupe, keep the latest

⏱ 6 min · Topic 9 of 19

Dedupe keeps one row for each business key. A business key is the id of one real thing, like order_id.

You must choose which row wins. The usual rule is the latest update, with a version number to break ties.

The shop has no repeated orders. So here is a small feed of status changes, called order_updates. Order 105 has three rows, and two of them share one time:

Keep the winner for each orderworked example

Python

Input data

order_updates5 rows

order_id	status	updated_at	version
103	paid	2026-01-11T09:00	1
105	pending	2026-01-20T09:00	1
103	refunded	2026-01-12T14:00	2
105	paid	2026-01-22T10:00	2
105	cancelled	2026-01-22T10:00	3

order_updates = [
    {"order_id": 103, "status": "paid", "updated_at": "2026-01-11T09:00", "version": 1},
    {"order_id": 105, "status": "pending", "updated_at": "2026-01-20T09:00", "version": 1},
    {"order_id": 103, "status": "refunded", "updated_at": "2026-01-12T14:00", "version": 2},
    {"order_id": 105, "status": "paid", "updated_at": "2026-01-22T10:00", "version": 2},
    {"order_id": 105, "status": "cancelled", "updated_at": "2026-01-22T10:00", "version": 3},
]

def latest_per_key(rows, key):
    winners = {}
    for row in rows:
        rank = (row["updated_at"], row["version"])
        current = winners.get(row[key])
        if current is None or rank > (current["updated_at"], current["version"]):
            winners[row[key]] = row
    return winners

winners = latest_per_key(order_updates, "order_id")
for order_id in sorted(winners):
    print(order_id, winners[order_id]["status"])

backwards = latest_per_key(reversed(order_updates), "order_id")
print(backwards == winners)

Result · 3 rows

output
103 refunded
105 cancelled
True

Order 103: the later time wins. Order 105: two rows tie on time, so version 3 wins. The last line shows that reading the rows in reverse gives the same winners.

The rank is a tuple: (updated_at, version). Python compares tuples one part at a time.

Time text like "2026-01-22T10:00" sorts in time order only when every value has the same format and time zone. Otherwise, parse it into a datetime first.

Watch out

10 · Sort and scan

Sort, then scan once

⏱ 5 min · Topic 10 of 19

Sorting turns many questions into one pass. Sort by the key, then by time. Then walk the rows, and the last row seen for each key is the latest.

This finds the latest order of each customer. The dict is overwritten each time, so the final value is the last row in sorted order:

Latest order for each customerworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

ordered = sorted(orders, key=lambda o: (o["customer_id"], o["order_date"], o["order_id"]))

latest_by_customer = {}
for order in ordered:
    latest_by_customer[order["customer_id"]] = order

for customer_id, order in latest_by_customer.items():
    print(customer_id, order["order_id"], order["order_date"])

Result · 4 rows

output
1 102 2026-01-10
2 103 2026-01-11
3 105 2026-01-20
4 106 2026-01-21

Asha has orders 101 and 102. Order 102 is later, so it wins. Carla's latest is 105, the pending order.

The dedupe loop in the last section solves a similar problem. Use that loop when you need only the winners. Use the sort when other steps also need the order.

For this dict, a sort by date alone also works. Put customer_id first when you need each customer's rows together, for example to write one customer at a time.

Watch out

Two orders of one customer can share a date. Then the winner depends on the input order. Add order_id last in the sort key, so a tie always has the same winner.

11 · Window-like

Running totals and previous row

⏱ 4 min · Topic 11 of 19

A SQL window function looks at nearby rows in an order. In Python, you sort the rows, then carry a little state for each key. State is a value you update as you go.

This prints one line for each paid order. The columns are: order_id, customer_id, row number, previous amount, running total. All three window values are per customer:

Row number, previous amount, running totalworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

from collections import defaultdict
from decimal import Decimal

paid = [o for o in orders if o["status"] == "paid"]
ordered = sorted(paid, key=lambda o: (o["customer_id"], o["order_date"], o["order_id"]))

row_number = defaultdict(int)
running = defaultdict(Decimal)
previous = {}

for order in ordered:
    cid = order["customer_id"]
    row_number[cid] += 1
    running[cid] += order["amount"]
    print(order["order_id"], cid, row_number[cid], previous.get(cid), running[cid])
    previous[cid] = order["amount"]

Result · 4 rows

output
101 1 1 None 40.00
102 1 2 40.00 65.00
104 3 1 None 15.50
106 4 1 None 80.00

Asha's second order, 102, sees the previous amount 40.00. Its running total is 40.00 + 25.00 = 65.00. A customer's first order has previous None.

The state is small: three values for each customer. The rows must be sorted first. If they are not, the running total changes with the input order.

12 · Ordering

Sort keys and tie-breaks

⏱ 6 min · Topic 12 of 19

Python sort is stable: equal rows keep the order they arrived in. But rows from a set, a parallel read or a list of files arrive in no order you chose. So a tie must be broken by the key itself.

Look at the Lamp rows. Two items tie on product. Sort by product alone, then sort the same rows read in reverse:

A tie with no tie-breakworked example

Python

Input data

order_items7 rows

order_id	product	qty
101	Pen	2
101	Notebook	1
102	Bag	1
103	Lamp	1
104	Pen	3
106	Chair	1
106	Lamp	1

by_product = lambda item: item["product"]

as_read = sorted(order_items, key=by_product)
print([(i["product"], i["order_id"]) for i in as_read if i["product"] == "Lamp"])

reread = sorted(reversed(order_items), key=by_product)
print([(i["product"], i["order_id"]) for i in reread if i["product"] == "Lamp"])

Result · 2 rows

output
[('Lamp', 103), ('Lamp', 106)]
[('Lamp', 106), ('Lamp', 103)]

The same data gives two different orders. Nothing failed, but a report built on this would change between runs.

The fix is a tuple key that ends in something unique. To sort one part high-to-low, put a minus sign on a number. This sorts by product, then by qty high-to-low, then by order_id:

A key with no tiesworked example

Python

Input data

order_items7 rows

order_id	product	qty
101	Pen	2
101	Notebook	1
102	Bag	1
103	Lamp	1
104	Pen	3
106	Chair	1
106	Lamp	1

def total_order(item):
    return (item["product"], -item["qty"], item["order_id"])

for seed in (order_items, list(reversed(order_items))):
    ranked = sorted(seed, key=total_order)
    print([(i["product"], i["qty"], i["order_id"]) for i in ranked if i["product"] in ("Lamp", "Pen")])

Result · 2 rows

output
[('Lamp', 1, 103), ('Lamp', 1, 106), ('Pen', 3, 104), ('Pen', 2, 101)]
[('Lamp', 1, 103), ('Lamp', 1, 106), ('Pen', 3, 104), ('Pen', 2, 101)]

Both inputs give the same list. Pen 104 (qty 3) comes before Pen 101 (qty 2) because of the minus sign.

If ids come from a CSV file, they are text, and "10" sorts before "9". Turn them into int in the key, for example int(row["order_id"]).

Watch out

You cannot compare None with a number. Sorting the orders by amount fails on order 105. Filter out None first, or put a flag in the key: (amount is None, amount).

13 · Top k

Top k with a heap

⏱ 6 min · Topic 13 of 19

A heap is a list that keeps its smallest value easy to find. For the top k rows (k is how many rows you want, like 2), you do not need a full sort.

heapq.nlargest keeps only k rows at a time. This finds the two largest paid orders:

Top two paid ordersworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

import heapq

paid = [o for o in orders if o["status"] == "paid"]
top2 = heapq.nlargest(2, paid, key=lambda o: (o["amount"], -o["order_id"]))
print([(o["order_id"], o["amount"]) for o in top2])

Result · 1 row

output
[(106, Decimal('80.00')), (101, Decimal('40.00'))]

The key has an order_id tie-break, so equal amounts also give a fixed result.

You can also keep the heap yourself, as rows stream past. Memory then depends on k, not on the number of rows.

Push each row. When the heap has 2 rows, heappushpop adds the new row and removes the smallest:

A heap of two, over a streamworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

import heapq

top = []
for order in orders:
    if order["status"] != "paid":
        continue
    entry = (order["amount"], order["order_id"])
    if len(top) < 2:
        heapq.heappush(top, entry)
    else:
        heapq.heappushpop(top, entry)

print(sorted(top, reverse=True))
print(len(top))

Result · 2 rows

output
[(Decimal('80.00'), 106), (Decimal('40.00'), 101)]
2

The paid amounts arrive as 40.00, 25.00, 15.50, 80.00. The heap never holds more than 2 rows. Order 102 (25.00) is pushed out by 80.00.

On a tie, this heap keeps the larger order_id. The nlargest call above keeps the smaller one. Use one rule in both places.

14 · Structure

A pipeline of small functions

⏱ 5 min · Topic 14 of 19

Write each step as a small function. A step takes rows in and gives rows out.

You know generators from Iterators, Generators & Streaming Data. A generator step passes one row at a time to the next step.

This pipeline has three steps: keep paid orders, add the country, total by country. The last function, revenue_by_country, connects the steps:

Three steps and one functionworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

customers5 rows

customer_id	name	country
1	Asha	IN
2	Ben	GB
3	Carla	US
4	Dev	None
5	Omar	IN

from collections import defaultdict
from decimal import Decimal

def only_paid(rows):
    return (row for row in rows if row["status"] == "paid")

def add_country(rows, customer_by_id):
    for row in rows:
        customer = customer_by_id.get(row["customer_id"])
        country = customer["country"] if customer else None
        yield {**row, "country": country or "unknown"}

def total_by_country(rows):
    totals = defaultdict(Decimal)
    for row in rows:
        totals[row["country"]] += row["amount"]
    return dict(sorted(totals.items()))

def revenue_by_country(orders, customers):
    customer_by_id = {c["customer_id"]: c for c in customers}
    return total_by_country(add_country(only_paid(orders), customer_by_id))

print(revenue_by_country(orders, customers))

Result · 1 row

output
{'IN': Decimal('65.00'), 'US': Decimal('15.50'), 'unknown': Decimal('80.00')}

The result matches the report from the totals section. The first two steps are lazy: they read no row until total_by_country asks for it.

Each step has one job and one test. The join table is built once, outside the loop. A generator can be read only once, so do not reuse a step result twice.

15 · Testing

Test with small fixtures

⏱ 5 min · Topic 15 of 19

A fixture is a tiny input you write by hand. You know exactly what the right answer is. Because the transform is a small function, each test needs only a few rows.

Here a fixture means test data, not a pytest fixture.

These tests use revenue_by_country from the last section. They cover a refunded order, an unknown customer and empty input. A test is a function that uses assert:

Three small testsworked example

Python

def make_order(order_id, customer_id, status, amount):
    return {"order_id": order_id, "customer_id": customer_id,
            "status": status, "amount": Decimal(amount)}

def test_only_paid_orders_count():
    rows = [make_order(1, 1, "paid", "10.00"), make_order(2, 1, "refunded", "5.00")]
    people = [{"customer_id": 1, "country": "IN"}]
    assert revenue_by_country(rows, people) == {"IN": Decimal("10.00")}

def test_unknown_customer_goes_to_unknown():
    rows = [make_order(1, 9, "paid", "7.00")]
    assert revenue_by_country(rows, []) == {"unknown": Decimal("7.00")}

def test_empty_input_gives_empty_report():
    assert revenue_by_country([], []) == {}

for test in (test_only_paid_orders_count, test_unknown_customer_goes_to_unknown,
             test_empty_input_gives_empty_report):
    test()
    print("ok", test.__name__)

Result · 3 rows

output
ok test_only_paid_orders_count
ok test_unknown_customer_goes_to_unknown
ok test_empty_input_gives_empty_report

Each test runs on its own rows, not on the whole shop. A failing test points at one rule.

Choose fixtures that hit the edges of the data: an empty batch, a missing key, a repeated key, a None amount.

Compare the whole output with ==. A dict is equal in any order. A list is not, so sort a list first.

16 · Batch checks

Checks that see the whole batch

⏱ 5 min · Topic 16 of 19

Some checks need the whole batch at once: repeated ids, items with no order, customers with no orders. A Counter and set arithmetic do most of the work.

This runs five checks on the shop. Set subtraction a - b gives the values that are in a but not in b:

Five whole-batch checksworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

customers5 rows

customer_id	name	country
1	Asha	IN
2	Ben	GB
3	Carla	US
4	Dev	None
5	Omar	IN

order_items7 rows

order_id	product	qty
101	Pen	2
101	Notebook	1
102	Bag	1
103	Lamp	1
104	Pen	3
106	Chair	1
106	Lamp	1

from collections import Counter

order_counts = Counter(o["order_id"] for o in orders)
repeated_ids = [oid for oid, n in order_counts.items() if n > 1]
print("repeated order ids:", repeated_ids)

order_ids = {o["order_id"] for o in orders}
item_ids = {i["order_id"] for i in order_items}
print("items with no order:", sorted(item_ids - order_ids))
print("orders with no items:", sorted(order_ids - item_ids))

customer_ids = {c["customer_id"] for c in customers}
buyer_ids = {o["customer_id"] for o in orders}
print("orders with no customer:", sorted(buyer_ids - customer_ids))
print("customers with no orders:", sorted(customer_ids - buyer_ids))

Result · 5 rows

output
repeated order ids: []
items with no order: []
orders with no items: [105]
orders with no customer: []
customers with no orders: [5]

Order 105 has no items because it is still pending. Omar (5) has no orders. Both are normal here, but a check makes them visible.

Decide for each check: a warning, a reject, or a stop. "Items with no order" should usually stop the job. "Customers with no orders" is only information.

In a real job, return the results as a dict, for example {"orders with no items": [105]}. Then the caller makes that choice for each check.

17 · Scale

Cost, scale and when to switch

⏱ 9 min · Topic 17 of 19

Cost is how the work grows when the input grows. Write n for the rows of the big side, and m for the rows of the small side.

O(n) means the work grows at the same rate as n: twice the rows, twice the work. This table shows each pattern:

How each pattern grows

Pattern	Cost	In plain words
Map, filter	O(n)	One look at each row.
Group by, aggregate, pivot	O(n)	One look at each row, one dict update each.
Hash join	O(n + m)	Build the small side once, probe once for each big row.
Nested-loop join	O(n · m)	Compare every big row with every small row.
Dedupe latest	O(n)	One dict, one comparison for each row.
Sort, then scan	O(n log n)	The sort costs most. The scan is one pass.
Top k with a heap	O(n log k)	Keep only k rows. Cheaper than a full sort when k is small.

Count the work on the shop. The nested loop compares every order with every customer. The hash join builds once and looks up once for each order:

Count the steps of two joinsworked example

Python

Input data

orders6 rows

order_id	customer_id	status	amount	order_date
101	1	paid	40.00	2026-01-03
102	1	paid	25.00	2026-01-10
103	2	refunded	60.00	2026-01-11
104	3	paid	15.50	2026-01-15
105	3	pending	None	2026-01-20
106	4	paid	80.00	2026-01-21

customers5 rows

customer_id	name	country
1	Asha	IN
2	Ben	GB
3	Carla	US
4	Dev	None
5	Omar	IN

checks = 0
matches = []
for order in orders:
    for customer in customers:
        checks += 1
        if order["customer_id"] == customer["customer_id"]:
            matches.append((order["order_id"], customer["name"]))
print("nested loop checks:", checks, "matches:", len(matches))

lookups = 0
customer_by_id = {c["customer_id"]: c for c in customers}
for order in orders:
    lookups += 1
    customer_by_id[order["customer_id"]]
print("hash join steps:", len(customers), "to build +", lookups, "lookups")

Result · 2 rows

output
nested loop checks: 30 matches: 6
hash join steps: 5 to build + 6 lookups

6 orders times 5 customers is 30 checks. The hash join needs 5 + 6 = 11 steps. Both find the same 6 matches.

The gap grows fast. With 10,000,000 orders and 1,000,000 customers, the nested loop is n times m. The hash join is n plus m:

The same count at scaleworked example

Python

n, m = 10_000_000, 1_000_000
print(f"{n * m:,}")
print(f"{n + m:,}")

Result · 2 rows

output
10,000,000,000,000
11,000,000

Ten trillion steps against eleven million. This is why you use a dict for a join on equal keys. Use a nested loop only for a condition a dict cannot look up, like a date range.

Memory is the next limit. The dict on the small side must fit in memory. The big side does not: read it as a generator, one row at a time.

A sort keeps every row in memory. A group-by dict keeps one entry for each key.

When the small side no longer fits, move the work. Split both sides by key into parts that fit, or sort both sides and merge them. Or use SQL or Spark, which do this for you.

Scaling Python & Interview Capstone shows the full interview flow.

Interview question

"Now the input is 100 times bigger. What changes?" Name what grows in memory, stream the big side and keep the small dict. Say when you would move to SQL or Spark.