The LRU Cache Interview Question: A Step-by-Step Walkthrough

"Design and implement an LRU cache" is one of the most frequently asked coding interview questions at companies of every size. It tests whether you can combine two data structures, reason about constant-time operations, and write careful pointer code. Here is how to approach it so the answer feels calm and complete. Clarify the requirements An LRU (least recently used) cache has a fixed capacity and supports two operations: - get(key): return the value if present, otherwise -1, and mark the key as recently used. - put(key, value): insert or update the value and mark it recently used; if the cache exceeds capacity, evict the least recently used key. Ask whether both operations must be O(1). They almost always do, and saying so out loud sets up your design. Why one data structure is not enough A hash map gives O(1) lookup but has no notion of order. A list keeps order but finding an item is O(n). The standard solution combines them: a hash map from key to node, and a doubly linked list ordered from most to least recently used. Why doubly linked? To remove a node in O(1) you need access to its previous node. A singly linked list would force a scan. This is a detail interviewers often probe, so explain it before they ask. Use sentinel nodes Create dummy head and tail nodes that always exist. The real items sit between them. This removes nearly every null check: inserting after head and removing before tail become the same two-line operations regardless of whether the cache is empty. The helper methods Write two small helpers first: - remove(node): link node.prev to node.next and node.next to node.prev. - add_to_front(node): insert node right after head. Then the main operations are short: - get: if key not in map, return -1. Otherwise remove the node, add it to the front, return its value. - put: if key exists, update the value, remove and re-add to front. Otherwise create a node, add it to the front, store it in the map. If size exceeds capacity, take the node before tail, remove it, and delete its key from the map. The detail candidates forget most often is storing the key inside the node. Without it, you cannot delete the evicted entry from the hash map. Language shortcuts In Python, collections.OrderedDict with move_to_end and popitem(last=False) gives a compact solution; in Java, LinkedHashMap with access order and removeEldestEntry does the same. Mention these, but be ready to implement the linked list by hand, since many interviewers want to see it. Testing Walk through a capacity-2 example: put(1), put(2), get(1), put(3) should evict key 2, not key 1. Also test updating an existing key, capacity 1, and get on a missing key. Common follow-ups - Make it thread-safe: a lock around both operations, or finer-grained locking with trade-offs. - LFU cache: evict least frequently used, usually with frequency buckets of linked lists. - TTL expiry: store timestamps and lazily evict expired entries on access. - Distributed caching: consistent hashing and per-node LRU. Explaining while you code This question rewards narration: name each helper, say why the list is doubly linked, and trace one example before you finish. If you tend to lose track of pointers under pressure, Linkjob AI (https://linkjob.ai) provides real-time help during job interviews and technical interviews, helping you keep the structure clear while you code.