Syllabus Lesson 14 of 141 · Rules of the duel
Rules of the duel

Your first duel: the slow disk

Why it matters The first answer to "count things in a range" is to look at every thing. That is fine until the data is big and reading it costs money or time. Here it does.

A sensor logs events as whole-second timestamps, already sorted. The log sits on a slow, metered disk: every value you read is billed. Analysts send you a batch of time windows and want to know how many events fall in each.

Solve it before you look anything up. When you pass, you will see what an AI assistant would most likely have written, and an expert's route, side by side.

The data

from creative.budget import Tape
tape = Tape([3, 7, 7, 12, 40])   # sorted timestamps, every read counted
queries = [(0, 8), (7, 13)]       # windows: start included, end excluded
# window_counts(tape, queries) -> [3, 3]
Your turn

Write window_counts(tape, queries). tape is a Tape of sorted whole-number timestamps (repeats allowed). queries is a list of (start, end) pairs. Return a list with, for each window, how many timestamps t have start <= t < end. Budget: with 100,000 events and 1,000 windows you may read at most 60,000 values from the tape. len(tape) is free.

Spotted a problem in this lesson? Report it · Ask about this lesson

This exercise opens soon

Finish the lesson before it and this one unlocks. The whole course is free, no account needed, and you can read this lesson right now.

Start at lesson 1 Back to syllabus