LRU Cache

Problem Design a data structure for a Least Recently Used (LRU) cache supporting get(key) and put(key, value) in O(1) average time. When capacity is exceeded, evict the least recently used key.

Input / Output

• Input: a capacity, then a sequence of get(key) and put(key, value) calls.
• Output: get returns the value or -1; put inserts/updates and may evict.

Constraints

• 1 <= capacity <= 3000; up to 2 × 10^5 calls; both operations must be O(1) average.

Example

• LRUCache(2): put(1,1); put(2,2); get(1) → 1; put(3,3) evicts key 2; get(2) → -1.