← Create New Paste

Implementing an LRU Cache in a Coding Interview: Hash Map + Doubly Linked List

5 views
"Design and implement an LRU (least recently used) cache with O(1) get and put" is one of the most common medium-to-hard coding interview questions (LeetCode 146). It tests whether you can combine two data structures so each covers the other's weakness. Here is how to approach it in a 45-minute round. 1. Clarify the contract Ask: what is the capacity, and can it be zero? What should get return for a missing key (usually -1)? Does put on an existing key update the value and count as a "use"? Are keys and values integers, or generic? Is thread safety required? Most interviewers want a single-threaded version first, with a discussion of concurrency at the end. 2. Why one structure is not enough A hash map gives O(1) lookup but has no notion of order. A list or queue keeps recency order but finding and moving an element is O(n). The trick is to store, in the hash map, a pointer to a node in a doubly linked list. The list keeps nodes ordered from most recently used (head) to least recently used (tail). The map gives you the node in O(1), and the doubly linked list lets you unlink and re-insert it in O(1) because each node knows its neighbours. 3. Use sentinel nodes Create a dummy head and a dummy tail that are always present. Real nodes live between them. This removes almost every null check: inserting at the front is always "between head and head.next", and evicting is always "the node before tail". Interviewers notice when you reach for sentinels because it shows you have written linked list code before and know where the bugs hide. 4. The operations - remove(node): node.prev.next = node.next; node.next.prev = node.prev. - add_front(node): node.next = head.next; node.prev = head; head.next.prev = node; head.next = node. - get(key): if key not in map, return -1. Otherwise remove(node), add_front(node), return node.value. - put(key, value): if key exists, update the value, remove and add_front. Otherwise create a node, add_front, store it in the map, and if the size now exceeds capacity, take lru = tail.prev, remove(lru), and delete map[lru.key]. Store the key inside the node. Candidates often forget this and then cannot delete the evicted entry from the map. 5. Complexity Both get and put are O(1) time. Space is O(capacity) for the map plus the list nodes. 6. Test cases to say out loud Capacity 1 (every put of a new key evicts the previous one). Putting an existing key should not increase size or trigger eviction. A get should refresh recency, so the sequence put(1), put(2), get(1), put(3) with capacity 2 evicts key 2, not key 1. Walk through this example on the whiteboard before you code; it catches most ordering bugs. 7. Language shortcuts and when to mention them In Python, collections.OrderedDict with move_to_end and popitem(last=False) solves the problem in a few lines; in Java, LinkedHashMap with accessOrder=true and removeEldestEntry does the same. Mention these, but ask whether the interviewer wants you to build the structure yourself. Usually they do. 8. Follow-up questions Expect: how would you make it thread-safe (a single lock is simplest; segmented locks or a concurrent map plus approximate recency scale better)? How does this relate to real caches (Redis uses approximated LRU by sampling keys rather than a full list)? What about LFU (LeetCode 460), which needs frequency buckets, each with its own doubly linked list? 9. Communicating while you code The data structure itself is not hard to memorise. What separates strong candidates is explaining the invariant clearly: "the head side is most recent, the tail side is least recent, and the map always points at live nodes." Say it before coding and refer back to it when you debug. Practising this aloud is the best preparation. If you would like support during the actual round, Linkjob AI (https://linkjob.ai) gives real-time help during live job interviews and technical interviews, so you can keep your explanation and edge cases organised while you write the code.
Created Nov 15, 2026 15:05 Expires Nov 15, 2027 15:05