Design an LFU Cache

Design the object model and public API for a fixed-capacity Least-Frequently-Used (LFU) cache with O(1) get and put, breaking frequency ties by least-recently-used within the lowest frequency.

Operating context. One process, an in-memory key/value cache with a capacity fixed at construction. Every successful get or update increments an item's access frequency. When an insert would exceed capacity, evict the entry with the lowest frequency; if several share that frequency, evict the least-recently-used among them. The workload is read-heavy with interleaved writes.

Out of scope. Persistence or write-back, distributed / sharded caches, time-to-live expiry (name the TTL seam only), full thread-safe concurrency as a hard requirement (single-threaded core, name the locking seam), and cache warming.

What to produce. The class model (an entry node, a per-frequency LRU list, a frequency-bucket index, and a live minimum-frequency tracker), the public API (get, put, size, capacity), the O(1) promotion path that moves an entry from one frequency bucket to the next on access, and the eviction path that removes the LRU tail of the minimum-frequency bucket — with the min-frequency invariant stated explicitly.