LRU Cache

Problem

Implement an LRU cache with O(1) get and put.

Example

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

Constraints

• Up to 2 × 10^5 calls

Discussion

Be ready to extend: make it thread-safe, or distribute it.