LeetLLM
MediumCachingPython 3

LRU TTL Cache

Combine recency ordering and TTL cleanup without corrupting cache invariants.

35m3 sample tests7 hidden tests

Implement a bounded cache with eviction and optional expiry. Recency chooses among live entries; an expired TTL deadline always takes priority.

Requirements

  • Define LRUTTLCache(capacity, now).
  • put(key, value, ttl=None) stores a value. For an existing live key, overwrite the value, move it to most recently used, and replace its TTL from now() (ttl=None means no expiry).
  • get(key) returns the value or None when missing or expired.
  • get marks a key as most recently used.
  • When capacity is exceeded, evict expired entries first, then least recently used entries. Cleanup of expired keys must happen on put when reclaiming capacity, independent of any earlier get for the expired key.
  • Expiry is inclusive: a key is expired when now() >= expires_at.
  • A non-positive capacity stores no entries. A non-positive TTL expires immediately.

Example

This trace makes a most recently used, evicts b, then advances the injected clock to a's inclusive expiry boundary.

python
1clock = {"now": 0.0} 2cache = LRUTTLCache(capacity=2, now=lambda: clock["now"]) 3cache.put("a", 1, ttl=5) 4cache.put("b", 2) 5assert cache.get("a") == 1 6cache.put("c", 3) 7assert cache.get("b") is None 8clock["now"] = 5.0 9assert cache.get("a") is None

Constraints

  • Use standard-library Python only.
  • Don't use functools.lru_cache.

Editor