LRU Cache

Problem Implement an O(1) Least Recently Used (LRU) cache (relevant to a buffer pool / query cache): get(key) and put(key, value), evicting the least recently used key when capacity is exceeded.

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.