LRU Cache

Description

Implement a Least Recently Used (LRU) cache with fixed capacity.

Methods:
    __init__(capacity)         set capacity (>= 1)
    get(key) -> int            return value if present, else -1.
                               accessing a key marks it most-recently-used.
    put(key, value) -> None    insert/update. If at capacity, evict the
                               least-recently-used key. put also marks the
                               key most-recently-used.

Both get and put must run in O(1) average time.

The classic structure: dict[key] -> doubly-linked-list-node, plus a
DLL ordered by recency. Or use collections.OrderedDict and call
move_to_end / popitem(last=False).

Constraints

- 1 <= capacity <= 3000
- 0 <= key, value <= 10^4
- get and put both O(1) average time
- 'Use' = either get or put on a key