Cache hit rates under Zipf popularity

CodingIntermediate⏱ 1 hourAI SystemscachingzipfLRUhit ratesimulation

Problem

Work out what a cache of a given size is actually worth.

zipf_probs(N, a) — the normalised popularity law.
static_hit_rate(N, a, C) — the hit rate of an oracle cache holding the $C$ most popular items, as a ratio of generalised harmonic numbers.
power_law_hit_rate(N, a, C) — the asymptotic $(C/N)^{1-a}$ .
lru_hit_rate(requests, capacity) — simulated LRU on a request trace.

Then compare LRU against the static optimum on a Zipf trace, and check whether the power law is a usable approximation.

Implement it, then check the implementation against something you can verify independently.

Solve it here9 tests · Python runs in your browser

⌘/Ctrl + ↵ to run · limit 90s · draft saved in this browser

9 tests will run against your code. The first run downloads the Python runtime — several megabytes, once per browser.

Hints — 0 of 2 revealed

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
Simulate distance contrast run	Classical ML	Coding	Beginner	30 min
Balls into bins, with one choice and with two run	AI Systems	Coding	Intermediate	1 hour
Measure anisotropy in an embedding space run	RAG	Coding	Intermediate	1 hour
Measure fan-out amplification and the value of hedging run	AI Systems	Coding	Intermediate	1 hour
Measure the covariance estimation rate run	High-Dim Statistics	Coding	Intermediate	1 hour