Implement an LRU Cache

Problem Design and implement an LRU cache: get(key) and put(key, value) in O(1), evicting the least-recently-used entry when capacity is exceeded — with the datastore and eviction policy behind interfaces.

Requirements

• get: return value and mark as most-recently used, or -1/absent; put: upsert, mark MRU, evict LRU if over capacity; fixed capacity given at construction.

Core design

• Hashmap (key → node) + doubly linked list ordered by recency (head = MRU, tail = LRU): get looks up O(1) and moves the node to head; put updates-or-inserts at head, evicting the tail node (and its map entry) when full. Sentinel head/tail nodes remove the null-check edge cases — say so.
• Interface layer (the LLD twist here): Cache<K,V> interface; EvictionPolicy<K> abstraction (onGet/onPut/evictCandidate) with LRUPolicy as one implementation so LFU/FIFO plug in; storage behind a Store interface for testability.

Discussion points

• Why both structures are needed: map alone can't order, list alone can't look up — the O(1)+O(1) pairing is the question.
• Correctness traps: updating an existing key must also refresh recency; evict must remove from BOTH structures.
• Extensions: thread safety (coarse lock vs segmented; why LinkedHashMap/accessOrder=true is the cheeky Java answer), TTL entries, LFU (O(1) via frequency buckets) as the follow-on.