Skip to main content
ELYTE
HardAlgorithms & Data StructuresDebug

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 un...

Start problemBrowse all problems

What you will practice

PythonHash Maps & SetsLinked ListCachingDebugging

Requirements

  • Basic correctness: `put(k, v)` then `get(k)` returns `v`. Repeated puts on the same key overwrite the value.
  • Capacity bound: after inserting more than `capacity` distinct 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.
  • `get` on a missing key returns `None` and must NOT add anything to the cache. After 1,000 misses, `len(cache._dict)` should still be `0`.
  • Recency updates: calling `get(k)` or `put(k, ...)` on an existing key promotes it to most-recently-used so it isn't evicted next.

Starter files

lru_cache.pyEditable starter

What the judge checks

  • Runs in the python environment with the python-pytest runner.
  • Uses a 8000ms judge budget.
  • Behavior rules include: Basic Get Put Correctness Preserved, Eviction Removes Dict Entry, Eviction Unlinks Correct Node, Internal Size Bounded By Capacity.

Constraints

  • Do not change the public API (`__init__`, `get`, `put`).
  • Keep the underlying data structure: a `dict` keyed by cache key, with values pointing into a doubly-linked list. Tests inspect `cache._dict`.
  • Capacity is always positive; the constructor may raise on invalid input.

Example behavior

Input
cache = LRUCache(2); cache.put('a', 1); cache.put('b', 2); cache.put('c', 3)
Output
cache.get('a') == None  (a was evicted as LRU); cache.get('b') == 2; cache.get('c') == 3

Capacity=2, three inserts. 'a' is the oldest, so it goes.

Input
cache = LRUCache(2); cache.get('x'); cache.get('y'); len(cache._dict)
Output
0

Misses must not create entries. A cache that does is leaking.

Follow-up

How would you add a TTL to each entry so that entries also expire by age, not just by recency?