Code lab · World 04 · Caching

LRU cache in O(1).

A hash map plus a doubly linked list gives O(1) get and put with least-recently-used eviction. No OrderedDict.

Medium~35 min3 example + 9 hidden tests+90 XPJump to the code ↓

Saving also stores the Python runtime (~13.5 MB, once for every lab) so this lab runs with no internet.

PractisesW04 · D12.1 Cache-Aside (Lazy Loading)W00 · P611.2 Cache Eviction Policies

A cache has finite memory, so when it is full something has to go. LRU (least recently used) evicts the entry that has gone longest without being read or written (Week 0, Part 6, section 11.2): with capacity 4 and accesses A, B, C, D, A, B, inserting E evicts C. It is the policy behind most in-process caches and Memcached, and a classic "implement this" interview round.

Implement LRUCache(capacity):

Method	Does
`get(key)`	the value, or `None` when missing. A hit makes `key` the most recently used
`put(key, value)`	inserts or updates `key` and makes it most recently used. If that pushes the size over `capacity`, evict the least recently used key
`delete(key)`	removes `key`; returns `True` if it was there, `False` otherwise
`__len__()`	number of entries
`order()`	keys from least to most recently used (the tests use it to check recency)

Rules the tests check:

get and put run in O(1): the hidden tests count key comparisons, and scanning a list on every access fails them.
capacity below 1 raises ValueError.
A miss doesn't change the order. Updating an existing key never evicts anything.
Build the recency list yourself: collections.OrderedDict and functools.lru_cache are off limits, as they usually are in the interview.

Python 3.14 loads on first run (~6.5 MB once)14

Loading the editor…

⌘/Ctrl + Enternot run yet · 8 s limit

press Run tests

Write your code, then run 3 example tests and 9 hidden tests. Each run is limited to 8 seconds: an infinite loop gets stopped and Python restarts, your code stays.

← Transactional outbox relay