# LRU Cache **Difficulty:** MEDIUM [External](https://leetcode.com/problems/lru-cache) Canonical: https://scaleengineer.com/dsa/problems/lru-cache **Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design) **Algorithms:** [LRU Cache](https://scaleengineer.com/algorithms/lru-cache) **Data structures:** Hash Table, Linked List, Doubly-Linked List **Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [Chewy](https://scaleengineer.com/companies/chewy), [Cisco](https://scaleengineer.com/companies/cisco), [Docusign](https://scaleengineer.com/companies/docusign), [DoorDash](https://scaleengineer.com/companies/doordash), [Expedia](https://scaleengineer.com/companies/expedia), [FreshWorks](https://scaleengineer.com/companies/freshworks), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Grab](https://scaleengineer.com/companies/grab), [IBM](https://scaleengineer.com/companies/ibm), [Intel](https://scaleengineer.com/companies/intel), [Intuit](https://scaleengineer.com/companies/intuit), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [KLA](https://scaleengineer.com/companies/kla), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Myntra](https://scaleengineer.com/companies/myntra), [Nutanix](https://scaleengineer.com/companies/nutanix), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [PayPal](https://scaleengineer.com/companies/paypal), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [SAP](https://scaleengineer.com/companies/sap), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Shopee](https://scaleengineer.com/companies/shopee), [Snowflake](https://scaleengineer.com/companies/snowflake), [SoFi](https://scaleengineer.com/companies/sofi), [TikTok](https://scaleengineer.com/companies/tiktok), [VMware](https://scaleengineer.com/companies/vmware), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [ZScaler](https://scaleengineer.com/companies/zscaler), [eBay](https://scaleengineer.com/companies/ebay), [Capital One](https://scaleengineer.com/companies/capital-one), [Coupang](https://scaleengineer.com/companies/coupang), [Freecharge](https://scaleengineer.com/companies/freecharge), [Netflix](https://scaleengineer.com/companies/netflix), [Salesforce](https://scaleengineer.com/companies/salesforce), [Tesla](https://scaleengineer.com/companies/tesla), [Autodesk](https://scaleengineer.com/companies/autodesk), [Citadel](https://scaleengineer.com/companies/citadel), [Snap](https://scaleengineer.com/companies/snap), [Swiggy](https://scaleengineer.com/companies/swiggy), [Zenefits](https://scaleengineer.com/companies/zenefits), [Disney](https://scaleengineer.com/companies/disney), [Media.net](https://scaleengineer.com/companies/media.net), [PhonePe](https://scaleengineer.com/companies/phonepe), [Turo](https://scaleengineer.com/companies/turo), [Zepto](https://scaleengineer.com/companies/zepto), [BitGo](https://scaleengineer.com/companies/bitgo), [Niantic](https://scaleengineer.com/companies/niantic), [Confluent](https://scaleengineer.com/companies/confluent), [X](https://scaleengineer.com/companies/x), [Sprinklr](https://scaleengineer.com/companies/sprinklr), [razorpay](https://scaleengineer.com/companies/razorpay), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [Booking.com](https://scaleengineer.com/companies/booking.com), [Nokia](https://scaleengineer.com/companies/nokia), [Cloudflare](https://scaleengineer.com/companies/cloudflare), [Rakuten](https://scaleengineer.com/companies/rakuten), [Vimeo](https://scaleengineer.com/companies/vimeo), [smartnews](https://scaleengineer.com/companies/smartnews), [Twitch](https://scaleengineer.com/companies/twitch), [Rubrik](https://scaleengineer.com/companies/rubrik), [Citrix](https://scaleengineer.com/companies/citrix), [Splunk](https://scaleengineer.com/companies/splunk), [Squarespace](https://scaleengineer.com/companies/squarespace), [Tencent](https://scaleengineer.com/companies/tencent), [Tripadvisor](https://scaleengineer.com/companies/tripadvisor), [MongoDB](https://scaleengineer.com/companies/mongodb), [NetApp](https://scaleengineer.com/companies/netapp), [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies), [Rivian](https://scaleengineer.com/companies/rivian), [Verkada](https://scaleengineer.com/companies/verkada), [Roku](https://scaleengineer.com/companies/roku), [General Motors](https://scaleengineer.com/companies/general-motors), [Groww](https://scaleengineer.com/companies/groww), [Navan](https://scaleengineer.com/companies/navan), [Workday](https://scaleengineer.com/companies/workday), [BP](https://scaleengineer.com/companies/bp), [Ripple](https://scaleengineer.com/companies/ripple), [Nordstrom](https://scaleengineer.com/companies/nordstrom), [Cruise](https://scaleengineer.com/companies/cruise), [Okta](https://scaleengineer.com/companies/okta), [Zalando](https://scaleengineer.com/companies/zalando), [thoughtspot](https://scaleengineer.com/companies/thoughtspot), [Fiverr](https://scaleengineer.com/companies/fiverr), [Optiver](https://scaleengineer.com/companies/optiver), [The Trade Desk](https://scaleengineer.com/companies/the-trade-desk), [Reddit](https://scaleengineer.com/companies/reddit), [ThousandEyes](https://scaleengineer.com/companies/thousandeyes), [Mobileye](https://scaleengineer.com/companies/mobileye), [AppFolio](https://scaleengineer.com/companies/appfolio), [Aurora](https://scaleengineer.com/companies/aurora), [Cohesity](https://scaleengineer.com/companies/cohesity), [Highspot](https://scaleengineer.com/companies/highspot), [Shopify](https://scaleengineer.com/companies/shopify) --- ## Problem Design a data structure that follows the constraints of a **[Least Recently Used (LRU) cache](https://en.wikipedia.org/wiki/Cache%5Freplacement%5Fpolicies#LRU)**. Implement the `LRUCache` class: * `LRUCache(int capacity)` Initialize the LRU cache with **positive** size `capacity`. * `int get(int key)` Return the value of the `key` if the key exists, otherwise return `-1`. * `void put(int key, int value)` Update the value of the `key` if the `key` exists. Otherwise, add the `key-value` pair to the cache. If the number of keys exceeds the `capacity` from 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 <= 3000` * `0 <= key <= 104` * `0 <= value <= 105` * At most `2 * 105` calls will be made to `get` and `put`. # Approaches ## Using HashMap and ArrayList 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. **Time:** O(capacity) · **Space:** O(capacity) **Pros:** Conceptually straightforward to understand. **Cons:** Fails to meet the O(1) time complexity requirement for `get` and `put` operations due to the linear time complexity of list manipulations. ### Explanation 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 the `HashMap`. If it does, we retrieve the value. Then, we must update its position in the `ArrayList` to 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 an `ArrayList` takes O(N) time, where N is the capacity of the cache. - **`put(key, value)`**: If the key already exists, we update its value in the `HashMap` and move it to the end of the `ArrayList` (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 the `ArrayList` and also in the `HashMap`. Removing from the beginning of an `ArrayList` is an O(N) operation as all subsequent elements need to be shifted. Then, we add the new item to the `HashMap` and to the end of the `ArrayList`. ```java import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; class LRUCache { private int capacity; private Map cache; private List 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); } } } ``` ### Algorithm - Initialize a `HashMap` to store key-value pairs and an `ArrayList` to 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`. - **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`. - 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 the `HashMap`. - Add the new key-value pair to the `HashMap`. - Add the new key to the end of the `ArrayList`. ## Using HashMap and Doubly Linked List 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. **Time:** O(1) · **Space:** O(capacity) **Pros:** Achieves the required O(1) average time complexity for both `get` and `put` operations.; 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. ### Explanation 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 the `HashMap` to find the node in O(1). If it exists, we move this node to the front of the list (right after `head`) 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 before `tail` from both the linked list and the `HashMap` (O(1)). Finally, we add the new node to the front of the list and add its key-node pair to the `HashMap` (O(1)). ```java import java.util.HashMap; import java.util.Map; class LRUCache { private class Node { int key; int value; Node prev; Node next; } private final Map 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); } } } ``` ### Algorithm - Initialize a `HashMap` and a Doubly Linked List with sentinel `head` and `tail` nodes. - The `Node` class contains `key`, `value`, `prev`, and `next` pointers. - **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. - **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()` equals `capacity`: - Get the LRU node (the one before `tail`). - Remove it from the linked list (O(1)). - Remove its key from the `HashMap` (O(1)). - Add the new node to the front of the list (O(1)). - Add the new key and node to the `HashMap` (O(1)). # Solutions ### CSharp ```csharp 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); */ ``` ### Java ```java 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); */ ``` ### JavaScript ```javascript /** * @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) */ ``` ### CPP ```cpp 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); */ ``` ### Python ```python 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 ''.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 = value ```