Syllabus Lesson 20 of 141 · Fixation on yourself
Fixation on yourself

Self first: the wrapped log

Why it matters This is a full trap problem, and the tutor stays locked until you have written your own three approaches. Notice how it feels to start with nothing but the problem.

A small device keeps its event log in a ring buffer: a fixed-size file written in time order. When it fills up, writing wraps round to the start and overwrites the oldest entries. So the file is sorted, but rotated: the newest entries are followed by the oldest ones. Reading from the device's flash is slow and every value read counts.

Support staff ask questions like "how many events since 14:02?" in batches, and want an answer for each.

The data

from creative.budget import Tape
tape = Tape([50, 61, 70, 12, 20, 33])  # written in order, wrapped after 70
queries = [20, 65]
# count_since(tape, queries) -> [5, 1]   (20, 33, 50, 61, 70) and (70)

Start your code with your three approaches:

my_approaches = ["...", "...", "..."]
Your turn

First assign my_approaches: three approaches of your own, at least four words each (the tutor unlocks then; the check needs it too). Then write count_since(tape, queries). tape is a Tape of distinct whole-number timestamps, written in increasing order and possibly wrapped round once at an unknown position (it may also not have wrapped at all). It holds at least one entry. For each value q in queries, return how many entries are >= q. Budget: with 100,000 entries and 100 queries you may read at most 20,000 values. len(tape) is free.

Ideas before prompts: the AI tutor unlocks once my_approaches holds 3 approaches of your own.

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