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.
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)?
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.
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).
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.