LeetLLM
HardCachingPython 3

LFU TTL Cache

Combine frequency buckets, recency tie-breaks, and TTL cleanup without corrupting eviction state.

45m3 sample tests7 hidden tests

Implement a bounded cache with eviction and optional expiry. LFU counts successful accesses; a TTL deadline removes an entry when its lifetime runs out, regardless of frequency.

Requirements

  • Define LFUTTLCache(capacity, now).
  • put(key, value, ttl=None) stores a value.
  • get(key) returns the value or None when missing or expired.
  • A successful get increments the key frequency.
  • Updating an existing live key updates its value and TTL, and counts as an access. Passing ttl=None removes any previous expiration.
  • New keys start with frequency 1.
  • When capacity is exceeded, evict expired entries first, then the key with lowest frequency.
  • If multiple keys have the same lowest frequency, evict the least recently used key within that frequency.
  • 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 raises a above b in frequency, evicts b, then advances the injected clock to a's inclusive expiry boundary.

python
1clock = {"now": 0.0} 2cache = LFUTTLCache(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.
  • Prefer dict plus frequency buckets over a full scan on every eviction.

Editor