LRU Cache
Med#0146Time: O(capacity)Space: O(capacity)101 companies
Patterns
Algorithms
Data structures
Prompt
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity)Initialize the LRU cache with positive sizecapacity.int get(int key)Return the value of thekeyif the key exists, otherwise return-1.void put(int key, int value)Update the value of thekeyif thekeyexists. Otherwise, add thekey-valuepair to the cache. If the number of keys exceeds thecapacityfrom this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
Example 1:
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4
Constraints:
1 <= capacity <= 30000 <= key <= 1040 <= value <= 105- At most
2 * 105calls will be made togetandput.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a HashMap for fast key-value lookups and an ArrayList to maintain the order of usage. The HashMap stores the key-value pairs, while the ArrayList stores the keys in order from least recently used to most recently used.
Algorithm
- Initialize a
HashMapto store key-value pairs and anArrayListto track usage order. - For
get(key):- Check if the key is in the
HashMap. If not, return -1. - Find and remove the key from the
ArrayList(O(N) operation). - Add the key to the end of the
ArrayList. - Return the value from the
HashMap.
- Check if the key is in the
- For
put(key, value):- If the key exists in the
HashMap:- Update the value in the
HashMap. - Find and remove the key from the
ArrayList(O(N)). - Add the key to the end of the
ArrayList.
- Update the value in the
- If the key does not exist:
- Check if the cache size has reached capacity.
- If yes, remove the first element (LRU key) from the
ArrayList(O(N)) and the corresponding entry from theHashMap. - Add the new key-value pair to the
HashMap. - Add the new key to the end of the
ArrayList.
- If the key exists in the
Walkthrough
When a get or put operation occurs for a key, that key is considered the most recently used.
get(key): We first check if the key exists in theHashMap. If it does, we retrieve the value. Then, we must update its position in theArrayListto mark it as most recently used. This involves finding the key in the list, removing it, and adding it to the end. The removal operation in anArrayListtakes O(N) time, where N is the capacity of the cache.put(key, value): If the key already exists, we update its value in theHashMapand move it to the end of theArrayList(an O(N) operation). If the key is new, we check if the cache is at capacity. If it is, we remove the least recently used item, which is at the beginning of theArrayListand also in theHashMap. Removing from the beginning of anArrayListis an O(N) operation as all subsequent elements need to be shifted. Then, we add the new item to theHashMapand to the end of theArrayList.
import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map; class LRUCache { private int capacity; private Map<Integer, Integer> cache; private List<Integer> usageOrder; public LRUCache(int capacity) { this.capacity = capacity; this.cache = new HashMap<>(); this.usageOrder = new ArrayList<>(); } public int get(int key) { if (!cache.containsKey(key)) { return -1; } // Move the key to the end to mark it as most recently used usageOrder.remove(Integer.valueOf(key)); usageOrder.add(key); return cache.get(key); } public void put(int key, int value) { if (cache.containsKey(key)) { // Key exists, update value and move to end cache.put(key, value); usageOrder.remove(Integer.valueOf(key)); usageOrder.add(key); } else { // New key if (cache.size() >= capacity) { // Cache is full, evict the least recently used item int lruKey = usageOrder.get(0); usageOrder.remove(0); cache.remove(lruKey); } cache.put(key, value); usageOrder.add(key); } }}Complexity
Time
O(capacity)
Space
O(capacity)
Trade-offs
Pros
Conceptually straightforward to understand.
Cons
Fails to meet the O(1) time complexity requirement for
getandputoperations due to the linear time complexity of list manipulations.
The optimal solution combines a HashMap and a custom Doubly Linked List. The HashMap provides O(1) time complexity for lookups, while the Doubly Linked List provides O(1) time complexity for adding or removing nodes, which is crucial for maintaining the least-recently-used order efficiently.
Algorithm
- Initialize a
HashMap<Integer, Node>and a Doubly Linked List with sentinelheadandtailnodes. - The
Nodeclass containskey,value,prev, andnextpointers. - For
get(key):- Look up the node in the
HashMap. If not found, return -1. - If found, move the node to the front of the linked list (by removing it from its current position and adding it after
head). This takes O(1). - Return the node's value.
- Look up the node in the
- For
put(key, value):- Look up the node in the
HashMap. - If the node exists:
- Update its value.
- Move it to the front of the list (O(1)).
- If the node does not exist:
- Create a new
Node. - If
cache.size()equalscapacity:- Get the LRU node (the one before
tail). - Remove it from the linked list (O(1)).
- Remove its key from the
HashMap(O(1)).
- Get the LRU node (the one before
- Add the new node to the front of the list (O(1)).
- Add the new key and node to the
HashMap(O(1)).
- Create a new
- Look up the node in the
Walkthrough
We create a Doubly Linked List where each node stores a key-value pair. The HashMap maps each key to its corresponding node in the list. This allows us to jump directly to a node in O(1) time.
The order of the list represents the usage order. We maintain two dummy nodes, head and tail, to simplify boundary conditions. The node right after head is the most recently used (MRU), and the node right before tail is the least recently used (LRU).
get(key): We use theHashMapto find the node in O(1). If it exists, we move this node to the front of the list (right afterhead) to mark it as the MRU. This move operation involves just changing a few pointers and takes O(1) time. We then return the node's value.put(key, value): If the key already exists, we update the value in its corresponding node and move the node to the front of the list (O(1)). If the key is new, we create a new node. We check if the cache is full. If so, we evict the LRU item by removing the node just beforetailfrom both the linked list and theHashMap(O(1)). Finally, we add the new node to the front of the list and add its key-node pair to theHashMap(O(1)).
import java.util.HashMap;import java.util.Map; class LRUCache { private class Node { int key; int value; Node prev; Node next; } private final Map<Integer, Node> cache; private final int capacity; private final Node head; private final Node tail; public LRUCache(int capacity) { this.capacity = capacity; this.cache = new HashMap<>(); // Initialize sentinel nodes this.head = new Node(); this.tail = new Node(); head.next = tail; tail.prev = head; } // Helper to add a node to the front (most recently used) private void addNode(Node node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } // Helper to remove a node from the list private void removeNode(Node node) { Node prev = node.prev; Node next = node.next; prev.next = next; next.prev = prev; } // Helper to move a node to the front private void moveToFront(Node node) { removeNode(node); addNode(node); } public int get(int key) { Node node = cache.get(key); if (node == null) { return -1; } moveToFront(node); return node.value; } public void put(int key, int value) { Node node = cache.get(key); if (node != null) { // Key exists, update value and move to front node.value = value; moveToFront(node); } else { // New key if (cache.size() == capacity) { // Cache is full, evict LRU item Node lru = tail.prev; removeNode(lru); cache.remove(lru.key); } Node newNode = new Node(); newNode.key = key; newNode.value = value; cache.put(key, newNode); addNode(newNode); } }}Complexity
Time
O(1)
Space
O(capacity)
Trade-offs
Pros
Achieves the required O(1) average time complexity for both
getandputoperations.Provides a deep understanding of how such a data structure can be built from scratch.
Cons
Implementation is more complex than using a built-in data structure like Java's
LinkedHashMap.Requires careful handling of pointers to avoid bugs.
Solutions
Solution
public class LRUCache { class Node { public Node Prev ; public Node Next ; public int Key ; public int Val ; } private Node head = new Node (); private Node tail = new Node (); private Dictionary < int , Node > cache = new Dictionary < int , Node >(); private readonly int capacity ; private int size ; public LRUCache ( int capacity ) { this . capacity = capacity ; head . Next = tail ; tail . Prev = head ; } public int Get ( int key ) { Node node ; if ( cache . TryGetValue ( key , out node )) { moveToHead ( node ); return node . Val ; } return - 1 ; } public void Put ( int key , int Val ) { Node node ; if ( cache . TryGetValue ( key , out node )) { moveToHead ( node ); node . Val = Val ; } else { node = new Node () { Key = key , Val = Val }; cache . Add ( key , node ); addToHead ( node ); if (++ size > capacity ) { node = removeTail (); cache . Remove ( node . Key ); -- size ; } } } private void moveToHead ( Node node ) { removeNode ( node ); addToHead ( node ); } private void removeNode ( Node node ) { node . Prev . Next = node . Next ; node . Next . Prev = node . Prev ; } private void addToHead ( Node node ) { node . Next = head . Next ; node . Prev = head ; head . Next = node ; node . Next . Prev = node ; } private Node removeTail () { Node node = tail . Prev ; removeNode ( node ); return node ; } } /** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.Get(key); * obj.Put(key,Val); */class Node { int key ; int val ; Node prev ; Node next ; Node () { } Node ( int key , int val ) { this . key = key ; this . val = val ; } } class LRUCache { private Map < Integer , Node > cache = new HashMap <>(); private Node head = new Node (); private Node tail = new Node (); private int capacity ; private int size ; public LRUCache ( int capacity ) { this . capacity = capacity ; head . next = tail ; tail . prev = head ; } public int get ( int key ) { if (! cache . containsKey ( key )) { return - 1 ; } Node node = cache . get ( key ); moveToHead ( node ); return node . val ; } public void put ( int key , int value ) { if ( cache . containsKey ( key )) { Node node = cache . get ( key ); node . val = value ; moveToHead ( node ); } else { Node node = new Node ( key , value ); cache . put ( key , node ); addToHead ( node ); ++ size ; if ( size > capacity ) { node = removeTail (); cache . remove ( node . key ); -- size ; } } } private void moveToHead ( Node node ) { removeNode ( node ); addToHead ( node ); } private void removeNode ( Node node ) { node . prev . next = node . next ; node . next . prev = node . prev ; } private void addToHead ( Node node ) { node . next = head . next ; node . prev = head ; head . next = node ; node . next . prev = node ; } private Node removeTail () { Node node = tail . prev ; removeNode ( node ); return node ; } } /** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); *//** * @param {number} capacity */ var LRUCache = function (capacity) { this.size = 0; this.capacity = capacity; this.cache = new Map(); this.head = new Node(0, 0); this.tail = new Node(0, 0); this.head.next = this.tail; this.tail.prev = this.head;};/** * @param {number} key * @return {number} */ LRUCache.prototype.get = function (key) { if (!this.cache.has(key)) { return -1; } const node = this.cache.get(key); this.removeNode(node); this.addToHead(node); return node.val; };/** * @param {number} key * @param {number} value * @return {void} */ LRUCache.prototype.put = function (key, value) { if (this.cache.has(key)) { const node = this.cache.get(key); this.removeNode(node); node.val = value; this.addToHead(node); } else { const node = new Node(key, value); this.cache.set(key, node); this.addToHead(node); if (++this.size > this.capacity) { const nodeToRemove = this.tail.prev; this.cache.delete(nodeToRemove.key); this.removeNode(nodeToRemove); --this.size; } } };LRUCache.prototype.removeNode = function (node) { if (!node) return; node.prev.next = node.next; node.next.prev = node.prev;};LRUCache.prototype.addToHead = function (node) { node.next = this.head.next; node.prev = this.head; this.head.next.prev = node; this.head.next = node;};/** * @constructor * @param {number} key * @param {number} val */ function Node( key, val,) { this.key = key; this.val = val; this.prev = null; this.next = null;} /** * Your LRUCache object will be instantiated and called as such: * var obj = new LRUCache(capacity) * var param_1 = obj.get(key) * obj.put(key,value) */struct Node { int k ; int v ; Node * prev ; Node * next ; Node () : k ( 0 ) , v ( 0 ) , prev ( nullptr ) , next ( nullptr ) {} Node ( int key , int val ) : k ( key ) , v ( val ) , prev ( nullptr ) , next ( nullptr ) {} }; class LRUCache { public: LRUCache ( int capacity ) : cap ( capacity ) , size ( 0 ) { head = new Node (); tail = new Node (); head -> next = tail ; tail -> prev = head ; } int get ( int key ) { if ( ! cache . count ( key )) return - 1 ; Node * node = cache [ key ]; moveToHead ( node ); return node -> v ; } void put ( int key , int value ) { if ( cache . count ( key )) { Node * node = cache [ key ]; node -> v = value ; moveToHead ( node ); } else { Node * node = new Node ( key , value ); cache [ key ] = node ; addToHead ( node ); ++ size ; if ( size > cap ) { node = removeTail (); cache . erase ( node -> k ); -- size ; } } } private: unordered_map < int , Node *> cache ; Node * head ; Node * tail ; int cap ; int size ; void moveToHead ( Node * node ) { removeNode ( node ); addToHead ( node ); } void removeNode ( Node * node ) { node -> prev -> next = node -> next ; node -> next -> prev = node -> prev ; } void addToHead ( Node * node ) { node -> next = head -> next ; node -> prev = head ; head -> next = node ; node -> next -> prev = node ; } Node * removeTail () { Node * node = tail -> prev ; removeNode ( node ); return node ; } }; /** * Your LRUCache object will be instantiated and called as such: * LRUCache* obj = new LRUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); */class Node : def __init__ ( self , key = 0 , val = 0 ): self . key = key self . val = val self . prev = None self . next = None class LRUCache : def __init__ ( self , capacity : int ): self . cache = {} # key ==> Node(val) self . head = Node () # dummy node self . tail = Node () # dummy node self . capacity = capacity self . size = 0 self . head . next = self . tail # note: key setup self . tail . prev = self . head def get ( self , key : int ) -> int : if key not in self . cache : return - 1 node = self . cache [ key ] self . move_to_head ( node ) return node . val def put ( self , key : int , value : int ) -> None : if key in self . cache : node = self . cache [ key ] node . val = value self . move_to_head ( node ) else : node = Node ( key , value ) self . cache [ key ] = node self . add_to_head ( node ) self . size += 1 if self . size > self . capacity : tail = self . remove_tail () self . cache . pop ( tail . key ) self . size -= 1 def move_to_head ( self , node ): self . remove_node ( node ) self . add_to_head ( node ) def remove_node ( self , node ): node . prev . next = node . next node . next . prev = node . prev def add_to_head ( self , node ): node . next = self . head . next node . prev = self . head self . head . next = node node . next . prev = node def remove_tail ( self ): node = self . tail . prev self . remove_node ( node ) return node # Your LRUCache object will be instantiated and called as such: # obj = LRUCache(capacity) # param_1 = obj.get(key) # obj.put(key,value) ############ ''' example: >>> od = collections.OrderedDict() >>> >>> od[1]=1 >>> od[2]=2 >>> od[3]=3 >>> >>> od OrderedDict([(1, 1), (2, 2), (3, 3)]) >>> od.move_to_end(1) >>> od OrderedDict([(2, 2), (3, 3), (1, 1)]) >>> >>> od.get(1) 1 >>> od.popitem() (1, 1) >>> od OrderedDict([(2, 2), (3, 3)]) >>> >>> od[1]=1 >>> od OrderedDict([(2, 2), (3, 3), (1, 1)]) >>> >>> od.popitem(last=False) (2, 2) >>> od OrderedDict([(3, 3), (1, 1)]) ''' import collections class LRUCache : def __init__ ( self , capacity : 'int' ): self . cache = collections . OrderedDict () self . remain = capacity def get ( self , key : 'int' ) -> 'int' : if key not in self . cache : return - 1 self . cache . move_to_end ( key ) # meaning end is the most recently used return self . cache . get ( key ) def put ( self , key : 'int' , value : 'int' ) -> 'None' : if key not in self . cache : if self . remain > 0 : self . remain -= 1 else : self . cache . popitem ( last = False ) # pop start position else : self . cache . pop ( key ) self . cache [ key ] = value # add to end of dict, meaning most recently used ############ ### below solution with no ordered-dict class DLinkedNode : def __init__ ( self , key = 0 , value = 0 ): self . key = key self . val = value self . next = None self . prev = None class DLinkedList : def __init__ ( self ): self . head = DLinkedNode () # dummy head, its next is real head self . tail = DLinkedNode () # dummy tail, its prev is real tail self . head . next , self . tail . prev = self . tail , self . head def add_node ( self , node ): # add to head node . prev , node . next = self . head , self . head . next node . next . prev , node . prev . next = node , node def remove_node ( self , node ): node . prev . next , node . next . prev = node . next , node . prev return node . key def remove_tail ( self ): return self . remove_node ( self . tail . prev ) # dummy tail's prev is real tail def move_to_head ( self , node ): self . remove_node ( node ) self . add_node ( node ) # def __repr__(self): # ans = [] # h = self.head # while h: # ans.append(str(h.val)) # h = h.next # return '<DLinkedList: {}>'.format('->'.join(ans)) class LRUCache : def __init__ ( self , capacity : int ): self . capacity = capacity self . nodes_map = {} self . cache_list = DLinkedList () def get ( self , key : int ) -> int : node = self . nodes_map . get ( key , None ) if node : self . cache_list . move_to_head ( node ) return node . val else : return - 1 def put ( self , key : int , value : int ) -> None : node = self . nodes_map . get ( key , None ) if not node : if self . capacity > 0 : self . capacity -= 1 else : rm_key = self . cache_list . remove_tail () self . nodes_map . pop ( rm_key ) # note api new_node = DLinkedNode ( key , value ) self . nodes_map [ key ] = new_node self . cache_list . add_node ( new_node ) else : self . cache_list . move_to_head ( node ) node . val = valueVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.