Syllabus Lesson 77 of 141 · Odd limits
Odd limits

Fixed memory

Why it matters "Count how often each thing happens" is a dictionary, until the number of things is unbounded and the memory is not. An approximate count with a guaranteed bound is often worth far more than an exact count you cannot afford.

An API gateway flags heavy users. It sees every request, there can be any number of users, and each gateway process gets a fixed slice of memory for this job. The flag is only a prompt for a human to look, so a small over-count is fine; an under-count could hide a heavy user, so it is not.

Sketch: a fixed-size summary of a stream that answers questions approximately, with a known error bound. A count-min sketch, for example, keeps a few rows of counters and hashes each item to one counter per row; the smallest of those counters is never below the true count.

import zlib
row_index = zlib.crc32(f"{row}:{item}".encode()) % width   # same on every run
Your turn

Write class ApproxCounter with add(item) (items are strings) and estimate(item) (a whole number).

Limits. After 30,000 events from up to 10,000 different users, the counter may hold at most 3,500 items (kept() on the counter). Estimates must never be below the true count, and for at least 95% of users (including users never seen) must be at most the true count plus 300 (1% of the events). Results must be repeatable on every run and device: do not use hash() (it changes per run) or random numbers; zlib.crc32 or hashlib with fixed seeds are fine.

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