Fix a Slow Join and a Wasteful Top-k

An order report is fast in testing and takes minutes in production. Two functions cause it. join_orders compares every order with every customer, and top_k sorts every score to keep five. Fix both. Keep the data classes, _stream, _generate and solve as they are.

The join is quadratic, which means doubling the input makes it about four times slower. Twice the orders and twice the customers make four times the pairs. With 40,000 of each, that is 1.6 billion comparisons.

Join orders to customer names

join_orders(orders: Sequence[Order], customers: Sequence[Customer]) -> list[EnrichedOrder]

• Return one new EnrichedOrder per order, in the order of orders. Copy its order_id, customer_id and amount.
• Set customer_name to the name of the customer with that ID, or None if there is none. Keep orders that have no customer. The starter drops them.
• If two customers share an ID, use the name of the later one. Return one row per order, never one per matching customer.
• An empty name "" still counts as a match.
• Do not change either input.

Build a dictionary from customer ID to name once, then look up each order's customer in it. A dictionary lookup takes about the same time however many customers there are.

orders = [Order(1, 10, 2.0), Order(2, 99, 3.0)]
customers = [Customer(10, "old"), Customer(10, "new")]
assert join_orders(orders, customers) == [
    EnrichedOrder(1, 10, 2.0, "new"), EnrichedOrder(2, 99, 3.0, None),
]
assert join_orders([], customers) == []

Keep the largest scores

top_k(scores: Iterable[float], k: int) -> list[float]

• Return the k largest scores, largest first. Keep duplicates.
• If k is more than the number of scores, return them all, largest first.
• If k is zero or negative, or there are no scores, return [].
• scores can be a generator. Read it once, and don't build a list of every score only to keep a few.

heapq.nlargest(k, scores) does all of this. It keeps only the k largest values seen so far. The starter's sorted(scores)[:k] keeps the smallest values instead, and it holds every score in memory.

assert top_k(iter([1.0, 3.0, 3.0, -2.0]), 3) == [3.0, 3.0, 1.0]
assert top_k(iter([2.0, 1.0]), 5) == [2.0, 1.0]
assert top_k(iter([2.0]), 0) == []

What the driver reports

solve builds the inputs, calls your two functions and reports on them. When generate is 0 or less, it reads orders as [order_id, customer_id, amount] rows and customers as [customer_id, name] rows. When generate is more than 0, it makes that many orders and customers itself, and some orders have no customer. stream_n is the number of scores passed to top_k.

The largest test joins 40,000 orders to 40,000 customers and keeps 5 of 500,000 scores. The nested loop cannot finish it in time. Your submission must pass mypy --strict.