Problem - LRU Cache

Design a data structure that implements a Least Recently Used (LRU) cache. Implement:

• get(key): Return the value if key exists, else $-1$. Mark as recently used.
• put(key, value): Insert or update. If at capacity, evict the least recently used item first.

Both operations must be $O(1)$.

You're solving a classic system design question that combines two data structures. The hash map provides $O(1)$ lookup.

The doubly linked list maintains usage order with $O(1)$ move-to-front and remove-from-back operations. Constraints: capacity from $1$ to $3000$, up to $2 \cdot 10^5$ operations.