LRU Cache

Problem

Implement an O(1) LRU cache (relevant to buffer pool / query caching).

Example

capacity 2: put(1,1),put(2,2),get(1)->1,put(3,3) evicts 2

Constraints

• Up to 2 × 10^5 calls

Hint

Hash map + doubly linked list.