Card 07/ 08
Practice: Planning a Solution for Deliveries Before a Given Time
Up to 300,000 delivery times and as many questions asking how many arrived before a time t: plan it in six steps, then write it.
Planning a solution with the six steps for an unseen problem, before writing any of it, is the whole of this exercise. A depot logs up to 300,000 delivery times, in minutes after opening, and then answers up to 300,000 questions, each asking how many deliveries arrived before a time t. Work through the six steps, decide the approach and its cost, then write the function.
Use the deliveries 14 3 9 9 20 and the questions 9, 2 and 25 as your hand-worked example. One clarifying question changes the answers, so find it first.
Show the six steps and a solution
- Clarify. Does a delivery at exactly t count? Decide that it does not: "before" means strictly before, so the two deliveries at 9 do not count for t = 9. There are up to 3 × 10⁵ deliveries (n) and as many questions (q). Times may repeat. No deliveries is possible, and then every answer is 0.
- Work examples. For 14 3 9 9 20: t = 9 gives 1 (only 3), t = 2 gives 0, and t = 25 gives 5.
- State the brute force. For each question, count the deliveries below t: O(n × q), which is 9 × 10¹⁰ steps at the limits, hundreds of times over the budget of about 10⁸ a second.
- Find the bottleneck. Every question rescans every delivery. Sort the deliveries once, O(n log n), then answer each question with a binary search for the first time that is not below t, O(log n) each. In total O((n + q) log n), about 1.1 × 10⁷ steps.
- Write. The listing below.
- Trace. Sorted, the times are 3 9 9 14 20. The first time not below 9 sits at index 1, so 1 delivery came before 9. The first not below 25 would sit at index 5, past the end, so all 5 did.
Python's bisect_left returns the index of the first value not less than t, which is exactly the number of values strictly below t: the rule the clarifying question chose. bisect_right would count the deliveries at t as well.
from bisect import bisect_left
def count_before(deliveries: list[int], questions: list[int]) -> list[int]:
ordered = sorted(deliveries)
return [bisect_left(ordered, t) for t in questions]
deliveries = [14, 3, 9, 9, 20]
for t, count in zip([9, 2, 25], count_before(deliveries, [9, 2, 25])):
print(f"before {t}: {count}")
print("no deliveries:", count_before([], [5]))before 9: 1
before 2: 0
before 25: 5
no deliveries: [0]← → move through sections and cards