LRU Cache

LRU Cache

What is this problem about?

The LRU (Least Recently Used) Cache is an iconic design problem. You must build a data structure with a specific capacity. It must support get(key) to retrieve a value, and put(key, value) to add or update a value. The critical rule is that if a put operation exceeds the capacity, the cache must evict the least recently used item. Both get and put operations must execute in $O(1)$ average time complexity.

Why is this asked in interviews?

This is arguably the most famous system design coding question. It is universally asked because it perfectly tests a candidate's ability to combine two disparate data structures to achieve a time complexity that neither could achieve alone. It acts as a benchmark for your understanding of memory management, pointer manipulation, and dictionary operations.

Algorithmic pattern used

The only way to achieve $O(1)$ time for all operations is by combining a Hash Map with a Doubly-Linked List.

• The Hash Map maps keys to specific Nodes in the Linked List, providing $O(1)$ access.
• The Doubly-Linked List orders the items by usage. The "most recently used" items are moved to the head (or tail), and the "least recently used" naturally fall to the opposite end. Because it's doubly-linked, you can remove a node from the middle in $O(1)$ time if you have its reference from the Hash Map.

Example explanation

Initialize LRUCache(capacity=2).

• put(1, 1): Map: {1: Node(1)}. List: [1].
• put(2, 2): Map: {1: Node(1), 2: Node(2)}. List: [2, 1] (2 is most recent).
• get(1): Returns 1. Node(1) becomes most recent. List becomes: [1, 2].
• put(3, 3): Over capacity! Evict least recent (tail of list, which is 2). Remove 2 from Map and List. Insert 3. Map: {1: Node(1), 3: Node(3)}. List: [3, 1].
• get(2): Returns -1 (not found).

Common mistakes candidates make

The most disastrous mistake is trying to use an Array or standard List instead of a Doubly-Linked List. Shifting elements in an array when you remove an item takes $O(N)$ time, which immediately fails the prompt's $O(1)$ requirement. Another common error is forgetting to remove the evicted node's key from the Hash Map, causing memory leaks and false positives on future lookups.

Interview preparation tip

When building the LRU Cache in an interview, do not hesitate to write helper functions for your Doubly-Linked List! Write explicit addNodeToHead(node) and removeNode(node) methods before you write the main get and put logic. Using dummy head and tail nodes makes these helper functions completely immune to null-pointer exceptions, resulting in incredibly clean, bug-free code.