LRU Cache
Problem
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 thekey
if the key exists, otherwise return-1
.void put(int key, int value)
Update the value of thekey
if thekey
exists. Otherwise, add thekey-value
pair to the cache. If the number of keys exceeds thecapacity
from this operation, evict the least recently used key.
The functions get
and put
must each run in O(1)
average time complexity.
Solution Approach
Expected Time complexity:
Click - to see solution code
- C++
class LRUCache {
list<int> lst;
unordered_map<int, int> mp;
unordered_map<int, list<int>::iterator> itr;
int size;
public:
LRUCache(int capacity) { this->size = capacity; }
int get(int key) {
if (mp.find(key) == mp.end()) return -1;
update(key);
return mp[key];
}
void put(int key, int value) {
if (mp.size() == size && mp.find(key) == mp.end()) evict();
update(key);
mp[key] = value;
}
void update(int key) {
if (mp.find(key) != mp.end()) lst.erase(itr[key]);
lst.push_front(key);
itr[key] = lst.begin();
}
void evict() {
itr.erase(lst.back());
mp.erase(lst.back());
lst.pop_back();
}
};