LRU Cache

Problem Implement a Least Recently Used (LRU) cache with O(1) get(key) and put(key, value); 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

• Up to 2 × 10^5 calls; both operations O(1) average.

Example

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