LRU Cache

Question

## 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
Netflix may pivot to 'now make it thread-safe' or 'now distribute it' — be ready to extend.