LRU Cache

Question

## Problem

Design a data structure for a **Least Recently Used (LRU) cache** supporting `get(key)` and `put(key, value)` in **O(1)** average time. When capacity is exceeded, evict the least recently used key.

## Example
```
LRUCache(2)
put(1,1); put(2,2); get(1) -> 1
put(3,3)  // evicts key 2
get(2) -> -1
```

## Constraints
- 1 ≤ capacity ≤ 3000
- Up to 2 × 10^5 calls

## Hint
Hash map + doubly linked list. This is Apple's single most frequently reported coding question — be ready to implement the linked list from scratch.