Lru Cache
Category: Linked Lists
```
Problem Statement
- Retrieving a key's value with the getValueFromKey method.
- Retrieving the most recently used (the most recently inserted or retrieved) key with the getMostRecentKey method. Each of these methods should run in constant time. Additionally, the LRUCache class should store a maxSize property set to the size of the cache, which is passed in as an argument during instantiation. This size represents the maximum number of key-value pairs that the cache can store at once. If a key-value pair is inserted in the cache when it has reached maximum capacity, the least recently used key-value pair should be evicted from the cache and no longer retrievable; the newly added key-value pair should e ectively replace it. Note that inserting a key-value pair with an already existing key should simply replace the key's value in the cache with the new value and shouldn't evict a key-value pair if the cache is full. Lastly, attempting to retrieve a value from a key that isn't in the cache should return None / null . Sample Usage // All operations below are performed sequentially. LRUCache(3): - // instantiate an LRUCache of size 3 insertKeyValuePair("b", 2): - insertKeyValuePair("a", 1): - insertKeyValuePair("c", 3): - getMostRecentKey(): "c" // "c" was the most recently inserted key getValueFromKey("a"): 1 getMostRecentKey(): "a" // "a" was the most recently retrieved key insertKeyValuePair("d", 4): - // the cache had 3 entries; the least recently used one is evicted getValueFromKey("b"): None // "b" was evicted in the previous operation insertKeyValuePair("a", 5): - // "a" already exists in the cache so its value just gets replaced getValueFromKey("a"): 5 Hints Hint 1 What data structure could allow you to insert, retrieve, and evict resources as fast as possible, all the while keeping track of the least recently accessed resource - essentially keeping track of the order of the resources? A hash table would allow you to insert and retrieve resources fast, but it wouldn't allow you to keep track of their order. An array would let you keep track of their order, but it wouldn't let you access elements fast; it also wouldn't allow you to move an element from one position to another in constant time, which you would need to do to make a newly-accessed key / value pair the most recent one upon retrieval of a key's value. A linked list would allow you to keep track of elements' order and to move them seamlessly (if you knew their position), but it wouldn't allow you to access them easily without knowing their position beforehand. Could a heap help? What about a BST or a trie? Would any other data structures work? Hint 2 Could you use multiple data structures to make your LRU Cache's functionality fast and e cient? Could you store keys in one data structure, for instance, and values in an auxiliary data structure? What should these data structures be in order for all of the LRU Cache's methods to run in constant time? Hint 3 Try storing keys in a hash table and mapping them to nodes in a doubly linked list containing the keys' corresponding values (perhaps the nodes would also have to store the keys themselves). With these two data structures, you could access any key / value pair very easily via the hash table, and you could also e ortlessly move nodes in the linked list so as to keep track of the most recent and least recent key / value pairs. The linked list would also allow you to keep track of the entire order of the key / value pairs, thus allowing you to perpetually update the least recent key / value pairs after evictions. Optimal Space & Time Complexity (all 3 methods) O(1) time | O(1) space
```
Approach & Solution
Solution 1
``` removeTail(); } node.removeBindings(); head.prev = node; node.next = head; head = node; } } public void removeTail() { if (tail == null) { return; } if (tail == head) { head = null; tail = null; return; } tail = tail.prev; tail.next = null; } } static class DoublyLinkedListNode { String key; int value; DoublyLinkedListNode prev = null; DoublyLinkedListNode next = null; public DoublyLinkedListNode(String key, int value) { this.key = key; this.value = value; } public void removeBindings() { if (prev != null) { prev.next = next; } if (next != null) { next.prev = prev; } prev = null; next = null; } } static class LRUResult { boolean found; int value; public LRUResult(boolean found, int value) { this.found = found; this.value = value; } } }
Solution 2
``` 55 public void replaceKey(String key, int value) { 56 if (!this.cache.containsKey(key)) { 57 return; 58 } 59 cache.get(key).value = value; 60 } 61 } 62 63 static class DoublyLinkedList { 64 DoublyLinkedListNode head = null; 65 DoublyLinkedListNode tail = null; 66 67 public void setHeadTo(DoublyLinkedListNode node) { 68 if (head == node) { 69 return; 70 } else if (head == null) { 71 head = node; 72 tail = node; 73 } else if (head == tail) { 74 tail.prev = node; 75 head = node; 76 head.next = tail; 77 } else { 78 if (tail == node) { 79 removeTail(); 80 } 81 node.removeBindings(); 82 head.prev = node; 83 node.next = head; 84 head = node; 85 } 86 } 87 88 public void removeTail() { 89 if (tail == null) { 90 return; 91 } 92 if (tail == head) { 93 head = null; 94 tail = null; 95 return; 96 } 97 tail = tail.prev; 98 tail.next = null; 99 } 100 } 101 102 static class DoublyLinkedListNode { 103 String key; 104 int value; 105 DoublyLinkedListNode prev = null; y p 106 DoublyLinkedListNode next = null; 107 108 public DoublyLinkedListNode(String key, int value) { 109 this.key = key; 110 this.value = value; 111 } 112
Solution 3
``` } // O(1) time | O(1) space public LRUResult getValueFromKey(String key) { if (!cache.containsKey(key)) { return new LRUResult(false, -1); } updateMostRecent(cache.get(key)); return new LRUResult(true, cache.get(key).value); } // O(1) time | O(1) space public String getMostRecentKey() { return listOfMostRecent.head.key; } public void evictLeastRecent() { String keyToRemove = listOfMostRecent.tail.key; listOfMostRecent.removeTail(); cache.remove(keyToRemove); } public void updateMostRecent(DoublyLinkedListNode node) { listOfMostRecent.setHeadTo(node); } public void replaceKey(String key, int value) { if (!this.cache.containsKey(key)) { return; } cache.get(key).value = value; } } static class DoublyLinkedList { DoublyLinkedListNode head = null; DoublyLinkedListNode tail = null; public void setHeadTo(DoublyLinkedListNode node) { if (head == node) { return; } else if (head == null) { head = node;
Solution 4
```java
import java.util.*;
4
class Program {
static class LRUCache {
Map
```
Test Cases
``` Test Case 1 { "maxSize": 3, "classMethodsToCall": [ {"arguments": ["b", 2], "method": "insertKeyValuePair"}, {"arguments": ["a", 1], "method": "insertKeyValuePair"}, {"arguments": ["c", 3], "method": "insertKeyValuePair"}, {"arguments": [], "method": "getMostRecentKey"}, {"arguments": ["a"], "method": "getValueFromKey"}, {"arguments": [], "method": "getMostRecentKey"}, {"arguments": ["d", 4], "method": "insertKeyValuePair"}, {"arguments": ["b"], "method": "getValueFromKey"}, {"arguments": ["a", 5], "method": "insertKeyValuePair"}, {"arguments": ["a"], "method": "getValueFromKey"} ] } Test Case 2 { "maxSize": 1, "classMethodsToCall": [ {"arguments": ["a"], "method": "getValueFromKey"}, {"arguments": ["a", 1], "method": "insertKeyValuePair"}, {"arguments": ["a"], "method": "getValueFromKey"}, {"arguments": ["a", 9001], "method": "insertKeyValuePair"}, {"arguments": ["a"], "method": "getValueFromKey"}, {"arguments": ["b", 2], "method": "insertKeyValuePair"}, {"arguments": ["a"], "method": "getValueFromKey"}, {"arguments": ["b"], "method": "getValueFromKey"}, {"arguments": ["c", 3], "method": "insertKeyValuePair"}, {"arguments": ["a"], "method": "getValueFromKey"}, {"arguments": ["b"], "method": "getValueFromKey"}, {"arguments": ["c"], "method": "getValueFromKey"} ] } Test Case 3 { "maxSize": 4, "classMethodsToCall": [ {"arguments": ["a", 1], "method": "insertKeyValuePair"}, {"arguments": ["b", 2], "method": "insertKeyValuePair"}, {"arguments": ["c", 3], "method": "insertKeyValuePair"}, {"arguments": ["d", 4], "method": "insertKeyValuePair"}, {"arguments": ["a"], "method": "getValueFromKey"}, {"arguments": ["b"], "method": "getValueFromKey"}, {"arguments": ["c"], "method": "getValueFromKey"}, {"arguments": ["d"], "method": "getValueFromKey"}, {"arguments": ["e", 5], "method": "insertKeyValuePair"}, {"arguments": ["a"], "method": "getValueFromKey"}, {"arguments": ["b"], "method": "getValueFromKey"}, {"arguments": ["c"], "method": "getValueFromKey"}, {"arguments": ["d"], "method": "getValueFromKey"}, {"arguments": ["e"], "method": "getValueFromKey"} ] } Test Case 4 { "maxSize": 4, "classMethodsToCall": [ {"arguments": ["a", 1], "method": "insertKeyValuePair"}, {"arguments": [], "method": "getMostRecentKey"}, {"arguments": ["b", 2], "method": "insertKeyValuePair"}, {"arguments": [], "method": "getMostRecentKey"}, {"arguments": ["c", 3], "method": "insertKeyValuePair"}, {"arguments": [], "method": "getMostRecentKey"}, {"arguments": ["d", 4], "method": "insertKeyValuePair"}, {"arguments": [], "method": "getMostRecentKey"}, {"arguments": ["a"], "method": "getValueFromKey"}, {"arguments": [], "method": "getMostRecentKey"}, {"arguments": ["b"], "method": "getValueFromKey"}, {"arguments": [], "method": "getMostRecentKey"}, {"arguments": ["c"], "method": "getValueFromKey"}, {"arguments": [], "method": "getMostRecentKey"}, {"arguments": ["d"], "method": "getValueFromKey"}, {"arguments": [], "method": "getMostRecentKey"}, {"arguments": ["e", 5], "method": "insertKeyValuePair"}, {"arguments": [], "method": "getMostRecentKey"} ] } Test Case 5 { "maxSize": 4, "classMethodsToCall": [ {"arguments": ["a", 1], "method": "insertKeyValuePair"}, {"arguments": ["b", 2], "method": "insertKeyValuePair"}, {"arguments": ["c", 3], "method": "insertKeyValuePair"}, {"arguments": ["d", 4], "method": "insertKeyValuePair"}, {"arguments": ["a"], "method": "getValueFromKey"}, {"arguments": ["e", 5], "method": "insertKeyValuePair"}, {"arguments": ["a"], "method": "getValueFromKey"}, {"arguments": ["b"], "method": "getValueFromKey"}, {"arguments": ["c"], "method": "getValueFromKey"}, {"arguments": ["f", 5], "method": "insertKeyValuePair"}, {"arguments": ["c"], "method": "getValueFromKey"}, {"arguments": ["d"], "method": "getValueFromKey"}, {"arguments": ["g", 5], "method": "insertKeyValuePair"}, {"arguments": ["e"], "method": "getValueFromKey"}, {"arguments": ["a"], "method": "getValueFromKey"}, {"arguments": ["c"], "method": "getValueFromKey"}, {"arguments": ["f"], "method": "getValueFromKey"}, {"arguments": ["g"], "method": "getValueFromKey"} ] }