LRU cache

Implement LRUCache(capacity) with get(key), which returns the value or -1, and put(key, value), which inserts or updates and, when the cache is over capacity, evicts the least recently used key. Both must run in O(1) on average. Both get and put count as a use.

Before you code

You need three things in O(1): find a key, move it to "most recent", and remove the oldest. A hash map does the first; a doubly linked list ordered by recency does the other two, but only if you can reach a key's node without searching.

Hints

1. Map each key to its list node. Each node stores the key as well as the value, because eviction needs to delete the key from the map.
2. Use two sentinel nodes, head and tail, so that unlink and insert never check for null.
3. get: look up the node, unlink it, reinsert it after head.
4. put: update and move an existing node, or create one; if the size exceeds capacity, remove the node before tail and delete its key.
5. In Python, collections.OrderedDict with move_to_end does all of this; build it by hand first.

Production & complexity notes

When solving LRU cache on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Insert, delete and the dummy head to reinforce the underlying pattern.

What it practices

O(1) unlink in a doubly linked list with sentinels, from Insert, delete and the dummy head.