LRU Cache

Build a Least Recently Used (LRU) cache with a fixed capacity:

• get k — print the value stored for key k, or -1 if it is not in the cache. A successful get makes k the most recently used key.
• put k v — store value v for key k (replacing any old value) and make k the most recently used key. If this makes the cache hold more than capacity keys, evict the least recently used key.

Input:

• line 1: capacity q
• next q lines: one operation each

Output: one line for every get.

Constraints: 1 ≤ capacity ≤ 3000, 1 ≤ q ≤ 10⁵, 1 ≤ k ≤ 10⁴, 0 ≤ v ≤ 10⁵. There is at least one get.

The design: both operations must be O(1). Combine a hash map (key → node) with a doubly linked list ordered by recency: move a node to the front on every use; evict from the back. (Java's LinkedHashMap and Python's OrderedDict do this for you — build it yourself once to really understand it.)