Accidental quadratics: an index-backed join and a streaming top-k

Two lines that read as idiomatic Python, pass review, and are invisible in a flat profile — because the time is attributed to a comprehension, and a comprehension looks like work.

def join_orders(orders: Sequence[Order], customers: Sequence[Customer]) -> list[EnrichedOrder]: ...
def top_k(scores: Iterable[float], k: int) -> list[float]: ...

join_orders must return one EnrichedOrder per order, in the input order, with customer_name set from the matching customer or None when there is no match. The starter is the shape everyone writes:

[EnrichedOrder(...) for o in orders for c in customers if c.customer_id == o.customer_id]

It reads like SQL and has two defects. It is O(len(orders) × len(customers)) — fine at 500 rows, 1.6 × 10⁹ comparisons at 40,000 each. And an unmatched order produces no row at all, so orders vanish silently. An unmatched order is a documented result, not something to drop: dropping it means a revenue report that quietly excludes exactly the records with a data-quality problem, which are the ones someone needed to see.

Build a dict[int, str] index in one pass and look up in the second.

top_k must return the k largest values, descending, from a stream that is consumed once and cannot be materialised. The starter does sorted(scores)[:k] — which loads everything into memory, sorts all of it, and then takes the smallest k. heapq.nlargest(k, scores) holds k items, not n.

solve drives both:

def solve(
    orders: list[list[float]],
    customers: list[list[object]],
    k: int,
    stream_n: int,
    generate: int,
) -> dict[str, object]: ...

When generate > 0 the orders and customers are built internally at that scale instead of coming from the arguments — customer i for i in range(generate), and order i pointing at customer (i * 7) % (generate + 3), so a few orders reference customers that do not exist. It returns row counts, the total amount, the first three enriched rows, and the top-k values rendered as fixed-point strings so the comparison is exact rather than tolerance-based.

On measuring big-O honestly. The technique worth transferring is not “time it once” — it is to run at n and at 2n and look at the ratio. A linear algorithm gives about 2; a quadratic one gives about 4. That test is machine-independent, survives a noisy laptop, and does not need a calibrated threshold that will be wrong on someone else’s hardware. This harness cannot make timing assertions, so the hidden case simply runs at a scale where the quadratic join takes more than ten seconds and the indexed one takes under a tenth of one. In your own codebase, write the ratio test.

Your submission must pass mypy --strict.