[tabby title=”Task”]
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
The cache is initialized with a positive capacity.
Follow up:
Could you do both operations in O(1) time complexity?
Example:
LRUCache cache = new LRUCache( 2 /* capacity */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 (not found) cache.put(4, 4); // evicts key 1 cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4
This problem was taken from Leetcode
[tabby title=”Solution”]
The brute force solution will be to use array, to push every new element at the top, and on ‘get’ to pop out the element and to put it at the top of the array.
A better solution will be to use hashmap where the element retrieval will be O(1) (constant) but the hashmap is not keeping track of the order of the elements. To solve this problem we are going to link elements in the hashnmap table with double linked list, where each element will point to its previous and next sibling.
On every ‘get’ operation we are going to re-link the element and it’s siblings.
When the cache reaches the capacity we are going to remove the least used node from the bottom.
| put(1,1) | put(2,2) | get(1) | put(3,3) | get(2) | put(4,4) | get(1) | get(3) | get(4) | |
| return | 1 | -1 | -1 | 3 | 4 | ||||
| result | 1 | 2,1 | 1,2 | 3,1 => (2) | 3,1 | 4,3 => (1) | 4,3 | 3,4 | 4,3 |
class LRUCache {
constructor(capacity) {
this.head = null;
this.tail = null;
this.capacity = capacity;
this.count = 0;
this.hashMap = new Map();
}
get(key) {
var node = this.hashMap.get(key);
if(node) {
if(node == this.head) {
// node is already at the head, just return the value
return node.val;
}
if(this.tail == node && this.tail.prev) {
// if the node is at the tail,
// set tail to the previous node if it exists.
this.tail = this.tail.prev;
this.tail.next = null;
}
// link neibouring nodes together
if(node.prev)
node.prev.next = node.next;
if(node.next)
node.next.prev = node.prev;
// add the new head node
node.prev = null;
node.next = this.head;
this.head.prev = node;
this.head = node;
return node.val;
}
return -1;
}
put(key, val) {
this.count ++;
var newNode = { key, val, prev: null, next: null };
if(this.head == null) {
// this.hashMap is empty creating new node
this.head = newNode;
this.tail = newNode;
}
else {
var oldNode = this.hashMap.get(key);
if(oldNode) {
// if node with the same key exists,
// clear prev and next pointers before deleting the node.
if(oldNode.next) {
if(oldNode.prev)
oldNode.next.prev = oldNode.prev;
else
this.head = oldNode.next;
}
if(oldNode.prev) {
oldNode.prev.next = oldNode.next;
if(oldNode == this.tail)
this.tail = oldNode.prev;
}
// removing the node
this.hashMap.delete(key);
this.count --;
}
// adding the new node and set up the pointers to it's neibouring nodes
var currentHead = this.head;
currentHead.prev = newNode;
newNode.next = currentHead;
this.head = newNode;
if(this.tail == null)
this.tail = currentHead;
if(this.count == this.capacity + 1) {
// remove last nove if over capacity
var lastNode = this.tail;
this.tail = lastNode.prev;
if(!this.tail) {
//debugger;
}
this.tail.next = null;
this.hashMap.delete(lastNode.key);
this.count --;
}
}
this.hashMap.set(key, newNode);
return null;
}
}
[tabbyending]
