LeetLLM
HardCachingPython 3

LFU TTL Cache

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

45m2 sample tests4 hidden tests

Implement a bounded cache with least-frequently-used eviction and optional TTLs.

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

Example

python
1cache = LFUTTLCache(capacity=2, now=lambda: 0) 2cache.put("a", 1) 3cache.put("b", 2) 4assert cache.get("a") == 1 5cache.put("c", 3) 6assert cache.get("b") is None 7assert cache.get("a") == 1

Constraints

  • Use standard-library Python only.
  • Prefer dict plus frequency buckets over a full scan on every eviction.

Editor
Results
Run sample tests or submit all tests.