Fix the Memory-Leaking LRU Cache
An LRU cache from a production service is leaking memory and serving stale entries. Basic functional tests still pass — cache.put('a', 1); cache.get('a') returns 1 — but under stress the internal dictionary grows unbounded and eviction picks the wrong key.
Find and fix every bug in lru_cache.py. The shape of the implementation (doubly-linked list + dict) is correct. What's broken is the bookkeeping: which node gets unlinked, whether the dict entry is released, and what happens on a miss.
- Basic correctness:
put(k, v)thenget(k)returnsv. Repeated puts on the same key overwrite the value. - Capacity bound: after inserting more than
capacitydistinct keys,len(cache._dict)must stay<= capacity. - Correct eviction order: when the cache is full and a new key is inserted, the LEAST recently used key must be removed — not the most recently used one.
geton a missing key returnsNoneand must NOT add anything to the cache. After 1,000 misses,len(cache._dict)should still be0.- Recency updates: calling
get(k)orput(k, ...)on an existing key promotes it to most-recently-used so it isn't evicted next.
cache = LRUCache(2); cache.put('a', 1); cache.put('b', 2); cache.put('c', 3)cache.get('a') == None (a was evicted as LRU); cache.get('b') == 2; cache.get('c') == 3Capacity=2, three inserts. 'a' is the oldest, so it goes.
cache = LRUCache(2); cache.get('x'); cache.get('y'); len(cache._dict)0
Misses must not create entries. A cache that does is leaking.
- Do not change the public API (
__init__,get,put). - Keep the underlying data structure: a
dictkeyed by cache key, with values pointing into a doubly-linked list. Tests inspectcache._dict. - Capacity is always positive; the constructor may raise on invalid input.
How would you add a TTL to each entry so that entries also expire by age, not just by recency?
Keep moving through related algorithms & data structures problems and build a stronger search-friendly practice loop around this topic.
View track →