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 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
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
Cache capacity = 5
cache = | 5 | 3 | 2 | 1 | 4 |
MRU LRU
if entry exist
- move entry to front. return
else
- return -1
using lp = list >;
class LRUCache {
int c;
lp dll;
unordered_map um;
public:
LRUCache(int capacity):c(capacity){
um.reserve(capacity);
}
int get(int key) {
auto it = um.find(key);
// if key not found return -1
if (it == um.end()) {
return -1;
}
// if key found, Move entry to front ie MRU(Most recently used)
// void splice (const_iterator position, list& x, const_iterator i)
dll.splice(dll.begin(), dll, it->second);
return it->second->second;
}
void put(int key, int value) {
auto it = um.find(key);
// if Key found in um
// - Replace value of key
// - key comes to front, ie becomes MRU(Most recently used)
if (it != um.end()){
it->second->second = value; //Replace the value in dll
dll.splice(dll.begin(), dll, it->second); //Move element to end of dll
return;
}
// if key not found
if (dll.size() < c) {
// Cache has space
// Insert at front of dll ie becomes MRU(Most recently used)
um[key] = dll.insert(dll.begin(), {key, value});
} else {
// Size of cache is full.
// - Remove last entry from cache ie remove LRU (Least recently used)
// - Remove key from hashmap
if (!dll.empty()) {
int temp_key = dll.back().first;
um.erase(temp_key);
dll.pop_back();
}
// Insert (key,value) at start
// Note address in hashmap
dll.push_front({key, value});
um[key] = dll.begin();
}
}
};
/**
* 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);
*/
"""
dll | 5 | 4 | 1 | 3 | 2 |
MRU LRU
hashmap
"""
class LRUCache:
def __init__(self, capacity: int):
self.capa = capacity
self.hm = {} # Hashmap
self.dll = [] # Double linked list
def get(self, key: int) -> int:
# key is not present in Hashmap
if key not in self.hm:
return -1
# Remove the key from the dll and insert it at the front (MRU)
self.dll.remove(key)
self.dll.insert(0, key)
return self.hm[key]
def put(self, key: int, value: int) -> None:
if key in self.hm:
# key present in hashmap
# Remove from dll, insert at front MRU.
self.hm[key] = value
self.dll.remove(key)
self.dll.insert(0, key)
else:
# key not present in hashmap
if len(self.dll) >= self.capa:
# sizeof(dll) is greater than capacity. DLL full
# Remove LRU element, remove from hm
lru_key = self.dll.pop()
self.hm.pop(lru_key)
# Insert the new key at the front (MRU)
self.dll.insert(0, key)
self.hm[key] = value