Solution For Lru Cache
The LRU Cache problem on LeetCode is a popular algorithmic problem that involves designing an efficient data structure that supports two operations – get and put. The data structure should be able to store a fixed number of key-value pairs and should satisfy the following conditions:
If a key is already present in the cache, its corresponding value should be updated (since we are considering the most recently used value), and it should be moved to the front of the cache.
If a key is not present in the cache, it should be added to the cache and moved to the front of the cache. If the cache is full, the least recently used key-value pair should be removed from the cache to make space for the new key-value pair.
To solve this problem, we can use a combination of a hash map and a doubly linked list. The hash map will map each key to its corresponding node in the doubly linked list. The doubly linked list will maintain the order in which the keys were last accessed, with the most recently used key at the front of the list and the least recently used key at the end of the list.
Here is the step-by-step solution to the LRU Cache problem:
Step 1: Define a doubly linked list node class that stores the key and value of each key-value pair in the cache, as well as pointers to the previous and next nodes in the list.
class Node {
public:
int key;
int value;
Node* prev;
Node* next;
Node(int key, int value): key(key), value(value), prev(nullptr), next(nullptr) {}
};
Step 2: Define a hash map that maps keys to their corresponding nodes in the doubly linked list.
unordered_map<int, Node*> cacheMap;
Step 3: Define a doubly linked list that maintains the order in which the keys were last accessed.
class LRUCache {
int capacity;
Node* head;
Node* tail;
public:
LRUCache(int capacity): capacity(capacity), head(nullptr), tail(nullptr) {}
};
Step 4: Implement the get method that retrieves the value of a key from the cache. If the key is not present in the cache, return -1. If the key is present in the cache, move its corresponding node to the front of the list and return its value.
int get(int key) {
if (cacheMap.find(key) == cacheMap.end()) {
// key not found in cache
return -1;
}
// key found in cache
Node* node = cacheMap[key];
if (node != head) {
// move node to front of list
if (tail == node) {
tail = node->prev;
}
node->prev->next = node->next;
if (node->next != nullptr) {
node->next->prev = node->prev;
}
node->prev = nullptr;
node->next = head;
head->prev = node;
head = node;
}
return node->value;
}
Step 5: Implement the put method that adds a key-value pair to the cache. If the key is already present in the cache, update its value and move its corresponding node to the front of the list. If the key is not present in the cache, create a new node for the key-value pair and add it to the front of the list. If the cache is full, remove the least recently used key-value pair (i.e., the node at the end of the list) from the cache.
void put(int key, int value) {
if (cacheMap.find(key) != cacheMap.end()) {
// key already exists in cache, update value and move node to front of list
Node* node = cacheMap[key];
node->value = value;
if (node != head) {
// move node to front of list
if (tail == node) {
tail = node->prev;
}
node->prev->next = node->next;
if (node->next != nullptr) {
node->next->prev = node->prev;
}
node->prev = nullptr;
node->next = head;
head->prev = node;
head = node;
}
} else {
// key not found in cache, create new node and add to front of list
Node* node = new Node(key, value);
cacheMap[key] = node;
if (head == nullptr) {
head = tail = node;
} else {
node->next = head;
head->prev = node;
head = node;
}
if (cacheMap.size() > capacity) {
// cache is full, remove least recently used node from end of list
cacheMap.erase(tail->key);
Node* prevTail = tail->prev;
delete tail;
tail = prevTail;
if (tail != nullptr) {
tail->next = nullptr;
}
}
}
}
Step 6: Test the LRU Cache implementation by creating an instance of the LRUCache class and calling the get and put methods on it with various key-value pairs.
Step by Step Implementation For Lru Cache
import java.util.HashMap;
import java.util.Map;
public class LRUCache {
private Map map;
private int capacity;
private Node head;
private Node end;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
}
public int get(int key) {
if(map.containsKey(key)) {
Node n = map.get(key);
remove(n);
setHead(n);
return n.value;
}
return -1;
}
public void remove(Node n) {
if(n.pre != null) {
n.pre.next = n.next;
} else {
head = n.next;
}
if(n.next != null) {
n.next.pre = n.pre;
} else {
end = n.pre;
}
}
public void setHead(Node n) {
n.next = head;
n.pre = null;
if(head != null)
head.pre = n;
head = n;
if(end == null)
end = head;
}
public void set(int key, int value) {
if(map.containsKey(key)) {
Node old = map.get(key);
old.value = value;
remove(old);
setHead(old);
} else {
Node created = new Node(key, value);
if(map.size() >= capacity) {
map.remove(end.key);
remove(end);
setHead(created);
} else {
setHead(created);
}
map.put(key, created);
}
}
}
class Node {
int key;
int value;
Node pre;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
} from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache = OrderedDict() def get(self, key: int) -> int: if key not in self.cache: return -1 value = self.cache[key] self.cache.move_to_end(key) return value def put(self, key: int, value: int) -> None: if key in self.cache: self.cache.move_to_end(key) self.cache[key] = value if len(self.cache) > self.capacity: self.cache.popitem(last=False)
var LRUCache = function(capacity) {
this.capacity = capacity;
this.map = {};
this.list = new List();
};
LRUCache.prototype.get = function(key) {
if (!this.map[key]) return -1;
var node = this.map[key];
this.list.moveToHead(node);
return node.value;
};
LRUCache.prototype.put = function(key, value) {
if (this.map[key]) {
this.map[key].value = value;
this.list.moveToHead(this.map[key]);
return;
}
var newNode = new Node(key, value);
if (this.list.size === this.capacity) {
delete this.map[this.list.tail.key];
this.list.removeTail();
}
this.list.addToHead(newNode);
this.map[key] = newNode;
};
var List = function() {
this.head = null;
this.tail = null;
this.size = 0;
};
List.prototype.addToHead = function(node) {
if (this.head === null) {
this.head = node;
this.tail = node;
} else {
this.head.prev = node;
node.next = this.head;
this.head = node;
}
this.size++;
};
List.prototype.removeTail = function() {
if (this.size === 0) return;
if (this.size === 1) {
this.head = null;
this.tail = null;
this.size--;
return;
}
this.tail = this.tail.prev;
this.tail.next = null;
this.size--;
};
List.prototype.moveToHead = function(node) {
if (node === this.head) return;
if (node === this.tail) {
this.removeTail();
} else {
node.prev.next = node.next;
node.next.prev = node.prev;
}
this.addToHead(node);
};
var Node = function(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
};class LRUCache {
public:
LRUCache(int capacity) {
this->capacity = capacity;
}
int get(int key) {
auto it = map.find(key);
if (it == map.end()) return -1;
update(it);
return it->second.first;
}
void put(int key, int value) {
auto it = map.find(key);
if (it != map.end()) update(it);
else {
if (list.size() == capacity) {
map.erase(list.back());
list.pop_back();
}
list.emplace_front(key, value);
}
map[key] = {value, list.begin()};
}
private:
typedef list> LRUList;
typedef unordered_map LRUMap;
int capacity;
LRUList list;
LRUMap map;
void update(LRUMap::iterator it) {
int key = it->first;
int value = it->second.first;
list.erase(it->second.second);
list.emplace_front(key, value);
it->second.second = list.begin();
}
}; using System;
using System.Collections.Generic;
public class LRUCache {
//We will be using a dictionary to store the key value pairs and a linked list to store the order in which the key value pairs were accessed
Dictionary dict = new Dictionary();
LinkedList list = new LinkedList();
//We will also be keeping track of the capacity of the cache
int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
}
//This is the get function which will be used to get the value of a key
public int Get(int key) {
//We first check if the key exists in the dictionary
if(dict.ContainsKey(key))
{
//If it does, we remove it from the linked list
list.Remove(key);
//And add it back to the front of the linked list
list.AddFirst(key);
//We then return the value associated with the key
return dict[key];
}
//If the key does not exist, we return -1
return -1;
}
//This is the put function which will be used to insert key value pairs into the cache
public void Put(int key, int value) {
//We first check if the key already exists in the dictionary
if(dict.ContainsKey(key))
{
//If it does, we remove it from the linked list
list.Remove(key);
}
//If the dictionary is full, we remove the last element in the linked list
//This is the least recently used element and hence needs to be removed
if(list.Count == capacity)
{
dict.Remove(list.Last.Value);
list.RemoveLast();
}
//We then add the key value pair to the dictionary
dict.Add(key, value);
//We also add the key to the front of the linked list
list.AddFirst(key);
}
}