LRU Cache Design

Problem Design a Least Recently Used (LRU) cache supporting get(key) and put(key, value) in O(1) average time, evicting the least recently used entry once capacity is exceeded.

Input / Output

• Input: a fixed positive capacity at construction, followed by a sequence of get and put calls.
• Output: get returns the stored value or -1 if absent; put inserts or updates, evicting the least recently used key if the cache overflows.

Constraints

• Both operations must be O(1) average — not O(log n).
• Capacity is fixed and positive; keys and values are generic.
• A get counts as a use: it must refresh recency, not just read. Updating an existing key via put also refreshes recency rather than growing the cache.
• Eviction happens only when inserting a new key into a full cache.

Example

• capacity=2; put(1,1); put(2,2); get(1) -> 1; put(3,3) evicts key 2 because get(1) had just made key 1 the most recent; get(2) -> -1.
• Key detail in that trace: key 2 is evicted rather than key 1 precisely because the get(1) call promoted key 1 to most-recently-used. An implementation that only tracks insertion order would wrongly evict key 1.
• Tricky case: with capacity=2, put(1,1); put(2,2); put(1,10) updates key 1 in place — size stays 2 and nothing is evicted.