146.LRU Cache
Solve this problem incrementally, don't try to get to the optimal solution in one shot.
Think out loud and achieve V0, reflect what can be optimized.
Thought process:
What data structure to use to:
- keep track of key/value pairs
- keep track of order of being recently accessed
It's fairly obvious 1 needs a map.
for 2, the initial thoughts are it needs to be a list like structure, where one element can be added to the end (last recently accessed), and can remove the oldest
item from the head. This suggests access to the head and the tail of the data structure is needed. They need to be done in O(1), which is THE most important hint that it has to be a doubly linked list (supports head and tail, moving an element to the end takes only O(1).
That is the most important step, to figure out what data structure to use. Second important thing is when moving element, we need to make sure the prev and next nodes are correctly updated. The mental model here is to imagine cutting a link out of a chain - you need to reconnect both sides.
From V0, we want to separate the linked like operations to helper functions: removeNode, addToTail, moveToTail:
V1:
class LRUCache {
public:
class Node {
public:
Node* prev;
Node* next;
int key;
int value;
Node(int key, int value)
{
this->key = key;
this->value = value;
prev = nullptr;
next = nullptr;
}
};
std::unordered_map<int, Node*> keyValues;
int capacity_;
Node* head_;
Node* tail_;
LRUCache(int capacity) : capacity_(capacity), head_(nullptr), tail_(nullptr) {}
int get(int key) {
auto it = keyValues.find(key);
if (it != keyValues.end()){
auto cur = it->second;
if (cur == tail_) {
return cur->value;
}
// Remove cur from current position - handle both directions
removeNode(cur);
// move cur to the end
addToTail(cur);
return cur->value;
}
return -1;
}
void put(int key, int value) {
auto it = keyValues.find(key);
if (it != keyValues.end()){
it->second->value = value;
get(key);
return;
}
// If adding new node, needs to check if map is at capactiy
if (keyValues.size() >= capacity_){
Node* oldHead = head_;
keyValues.erase(oldHead->key);
//evict the head
removeHead();
}
Node* newNode = new Node(key, value);
keyValues[key] = newNode;
// Update key order
newNode->prev = tail_;
if (tail_ != nullptr){
tail_->next = newNode;
} else {
head_ = newNode;
}
tail_ = newNode;
}
void addToTail(Node* node){
if (tail_ != nullptr){
tail_->next = node;
node->prev = tail_;
}
node->next = nullptr;
tail_ = node;
}
void removeNode(Node* node){
if (node->prev != nullptr){
node->prev->next = node->next; // Bridge the gap
} else {
head_ = node->next; // cur was head, update head
}
if (node->next != nullptr){
node->next->prev = node->prev; // Bridge the gap backwards
}
}
void removeHead(){
head_ = head_->next;
if (head_ != nullptr){
head_->prev = nullptr;
} else {
tail_ = nullptr;
}
}
};
V0:
Pay attention to handling both prev and next when moving nodes.
#include <unordered_map>
#include <iostream>
class LRUCache {
public:
class Node {
public:
Node* prev;
Node* next;
int key;
int value;
Node(int key, int value)
{
this->key = key;
this->value = value;
prev = nullptr;
next = nullptr;
}
};
std::unordered_map<int, Node*> keyValues;
int capacity_;
Node* head_;
Node* tail_;
LRUCache(int capacity) : capacity_(capacity), head_(nullptr), tail_(nullptr) {}
int get(int key) {
auto it = keyValues.find(key);
if (it != keyValues.end()){
auto cur = it->second;
if (cur == tail_) {
return cur->value;
}
// Remove cur from current position - handle both directions
if (cur->prev != nullptr){
cur->prev->next = cur->next;
} else {
head_ = cur->next;
}
if (cur->next != nullptr){ // handle next pointer
cur->next->prev = cur->prev;
}
// move cur to the end
cur->prev = tail_;
cur->next = nullptr;
if (tail_ != nullptr){
tail_->next = cur;
} else {
head_ = cur;
}
tail_ = cur;
return cur->value;
}
return -1;
}
void put(int key, int value) {
auto it = keyValues.find(key);
if (it != keyValues.end()){
it->second->value = value;
get(key);
return;
}
// If adding new node, needs to check if map is at capactiy
if (keyValues.size() >= capacity_){
Node* oldHead = head_;
keyValues.erase(oldHead->key);
//evict the head
head_ = head_->next;
if (head_ != nullptr) {
head_->prev = nullptr;
} else {
tail_ = nullptr;
}
}
Node* newNode = new Node(key, value);
keyValues[key] = newNode;
// Update key order
newNode->prev = tail_;
if (tail_ != nullptr){
tail_->next = newNode;
} else {
head_ = newNode;
}
tail_ = newNode;
}
};
/**
* 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);
*/
