LRU Cache

Question

## Problem

Implement an O(1) LRU cache.

## 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.