How would you implement a least recently used (LRU) cache, and what are its core components?
An LRU cache is typically implemented using two primary data structures: a hash map (or dictionary) and a doubly linked list. The hash map stores key-value pairs where the value is a reference to a node in the doubly linked list. This allows O(1) average-case time complexity for both data retrieval (get) and insertion/update (put) operations. The doubly linked list maintains the order of usage, with the most recently used item at one end and the least recently used item at the other. When the cache reaches its capacity limit, the node at the least recently used end of the list is evicted.
Core Data Structures
The hash map facilitates quick access to any item in the cache. Each entry in the map, key: Node, allows direct access to the corresponding node in the doubly linked list. This node contains the actual value and pointers to its previous and next elements in the list. The doubly linked list is critical for efficiently managing the usage order; moving an item to the front or removing the tail can both be done in O(1) time because pointers can be updated without traversing the entire list.
Best practice
A robust LRU implementation requires careful handling of capacity. When a new item is added and the cache is full, the least recently used item (the tail of the doubly linked list) must be removed from both the list and the hash map. For a get operation, if the item is found, it must be moved to the head of the list to signify its recent use. Consider thread safety for concurrent access by using locks or mutexes to protect shared data structures (hash map and linked list) from race conditions.
Edge case interviewers probe for
Interviewers often ask about handling items that are retrieved but not updated, ensuring they are still marked as recently used. Another common probe involves scenarios where the capacity limit is zero or one, or how to handle eviction when an item fails to be removed (e.g., due to an external dependency). Distributed LRU caches, where multiple instances need to synchronize, present significant challenges that move beyond a single-node implementation.
Common mistake
A frequent error is using a singly linked list instead of a doubly linked list. While a singly linked list can add to the head in O(1), removing an arbitrary node or the tail requires O(N) traversal to find the preceding node. Another mistake is forgetting to update an item’s position in the linked list during a get operation, which means it won’t be correctly marked as recently used and may be prematurely evicted. Inefficient pointer management or not keeping the hash map and linked list consistent also leads to bugs.
What the interviewer is checking
The interviewer is assessing your understanding of fundamental data structures, their performance characteristics, and how to combine them to solve a practical problem. They want to see your ability to manage pointers, handle various operations (get, put, eviction) with optimal time complexity, and consider real-world concerns such as capacity management and concurrency. It also reveals your attention to detail and ability to reason about system behavior.
Imagine you have a small desk for your frequently used tools, but it only fits a few. This desk is your LRU cache. When you need a tool, you grab it and put it right in front of you on the desk, because you just used it. If the desk is full and you need a new tool, you look at all the tools on the desk and pick up the one that’s been sitting there untouched the longest, and you put it away to make space for your new tool.
To make this system work efficiently, you also have a list in your head of where each tool is on the desk, like a quick mental index. So when you need a tool, you don’t have to search the whole desk; you just check your mental index to see if it’s there. The trick is making sure your mental index and the actual tools on the desk always match, especially when you move a tool to the front or put an old one away.
Why interviewers ask this
Interviewers ask about LRU caches to evaluate a candidate’s grasp of core data structures, their ability to apply them to practical system design problems, and their understanding of time complexity tradeoffs. It’s a classic question that combines theoretical knowledge with practical implementation skills.
What a strong answer signals
A strong answer clearly articulates the use of both a hash map and a doubly linked list, explaining why each is necessary for O(1) operations. It demonstrates awareness of edge cases like cache capacity, get operations updating recency, and potential concurrency issues. It signals a candidate who can think algorithmically and consider production-readiness.
Common follow-ups
- How would you ensure thread-safety for your LRU cache in a multi-threaded environment?
- What if the
getoperation was not considered a “use” for eviction purposes, onlyput? - How would you handle varying item sizes in the cache, and how would that affect eviction strategy?
Advanced variation
Design a distributed LRU cache across multiple servers, considering consistency, replication, and network latency. Alternatively, implement an LFU (Least Frequently Used) cache, which requires a more complex data structure like a frequency map of doubly linked lists.
Consider a video streaming platform like Zomato that serves restaurant menu images. Repeatedly fetching the same high-resolution image from a cloud storage bucket can be slow and expensive. Implementing an in-memory LRU cache on the application server for these images allows frequently accessed images to be served directly from RAM, drastically reducing latency and load on the storage backend. When the cache is full, the image that hasn’t been requested in the longest time is automatically removed to make space for newer, more popular content.
class LRUCache:
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.prev = None
self.next = None
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {} # key -> node
self.head = self.Node(0, 0) # dummy head
self.tail = self.Node(0, 0) # dummy tail
self.head.next = self.tail
self.tail.prev = self.head
def _remove_node(self, node):
# Remove a node from the doubly linked list
node.prev.next = node.next
node.next.prev = node.prev
def _add_node(self, node):
# Add a node to the head of the doubly linked list
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self._remove_node(node)
self._add_node(node)
return node.value
def put(self, key: int, value: int) -> None:
if key in self.cache:
self._remove_node(self.cache[key])
node = self.Node(key, value)
self.cache[key] = node
self._add_node(node)
if len(self.cache) > self.capacity:
lru_node = self.tail.prev
self._remove_node(lru_node)
del self.cache[lru_node.key]
- 1LRU caches combine a hash map and a doubly linked list for efficient operations.
- 2The hash map provides O(1) average time complexity for
getandputoperations. - 3The doubly linked list enables O(1) updates for recency and eviction of the least recently used item.
- 4Careful handling of edge cases like capacity limits and concurrency is crucial for a robust implementation.
- 5This pattern is widely used in systems to optimize performance by reducing access to slower data sources.