LRU Cache

Problem

Design a fixed-capacity cache that evicts the least recently used entry when full. Implement a class LRUCache with:

• __init__(capacity): create a cache that can hold at most capacity key/value pairs.
• get(key): return the value for key if present, otherwise -1. A successful get counts as a use.
• put(key, value): insert or overwrite the value for key. This counts as a use. If inserting a new key exceeds the capacity, evict the entry that was used least recently before inserting.

Both operations must run in O(1) average time.

• Capacity is at most a few thousand entries.
• Keys and values are non-negative integers.
• Expect up to a couple hundred thousand combined calls to get and put.

Examples

• Capacity 2: put(10,100), put(20,200), get(10) → 100; put(30,300) evicts key 20 (key 10 was used more recently); get(20) → -1; put(40,400) evicts key 10; get(10) → -1, get(30) → 300, get(40) → 400.
• Capacity 1: put(5,50), put(6,60) evicts key 5; get(5) → -1, get(6) → 60.
• Capacity 2: put(7,70), put(7,700) overwrites without eviction; get(7) → 700. Overwriting an existing key never triggers eviction.

Hints

1. A hash map gives O(1) lookup, but how do you know which key was used least recently without scanning?
2. You need an ordering by recency that supports "move this element to the front" and "remove the last element" in O(1). Which linked structure does that?
3. Hash map from key to node, plus a doubly linked list ordered by recency with sentinel head and tail. get and put unlink the node and re-insert it at the front; eviction removes the node before the tail.