LRU / LFU Cache: low-level design

Design an in-memory cache with a fixed capacity. When it is full and a new item arrives, it must evict one item by a rule: least recently used (LRU) or least frequently used (LFU). Both `get` and `put` must run in O(1) time.

Stage 1: The contract

Say what a cache does before choosing how.

We have a goal (fast get and put) but no shape. A plain map is the obvious first try. A `Cache` interface with `get` and `put`, and a first implementation, `HashCache`, that is just a hash map. Starting with the interface means every later version (LRU, LFU, expiring) can be swapped in. The hash map gives O(1) `get` and `put`. It never evicts. Once we add a capacity the hard question appears: which item do we throw out, and how do we find it in O(1)?

Stage 2: O(1) recency: a linked list

Find the least recently used item without scanning.

With only a hash map we cannot answer 'which item was used least recently?' without scanning every entry, which is O(n). A **doubly linked list** keeps items in recency order: most recent at the head, least recent at the tail. The map stores each key's *node*, so we can jump straight to it. On `get` we look up the node in the map and move it to the head: O(1), because with a `prev` pointer a node can unlink itself. On overflow we drop the tail node and its map entry: O(1) too. Two structures to keep in step. Every change must update both the map and the list, or they drift apart. Wrapping that in a few small methods keeps it safe.

Stage 3: Make eviction pluggable

Let LRU, LFU or anything else be chosen without rewriting the cache.

`LRUCache` mixes two jobs: storing values and choosing what to evict. LFU would mean copying the whole class. The cache keeps only the key-value storage and asks an `EvictionPolicy` what to do on each use and which key to evict. `LRUPolicy` uses the linked list. `LFUPolicy` counts uses with frequency buckets. This is **Strategy**: one cache, many rules. The cache never knows which rule it runs. A new rule (FIFO, random) is one class. Slightly more indirection: each access calls the policy. For a cache that is acceptable because the policy call is O(1).

Stage 4: Expiry and thread safety

Add extra behaviour by wrapping, not by editing.

Real caches also forget items after a time and are used from many threads. Putting both inside the cache classes would tangle everything. `TTLCache` wraps any `Cache` and drops items older than their time limit. `SynchronizedCache` wraps any `Cache` and takes a lock around each call. This is **Decorator**: each wrapper implements `Cache` and holds another `Cache`, so they stack in any order: `new SynchronizedCache(new TTLCache(new PolicyCache(...)))`. One global lock is correct but limits throughput. Splitting the cache into shards, each with its own lock, scales better and still fits the same interface.