Least Recently Used (LRU) cache | Interview Question

How to implement cache ? Top interview coding interview questions

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

Let’s discuss the approach

Data structure that follows the constraints of a Least Recently Used (LRU) cache.

  • Get the key / Check if the key exists
  • Put the key / Check if capacity is full or not
  • LRU Cache = Two data structures to manage the elements.

What data structure we should use to implement LRU cache ?

  • Map: used to store elements in the list
  • Double Linked List: used to keep track of the ordering when performing operations
var Node = function(key = 0, val = 0) {
this.key = key;
this.val = val;
this.next = null;
this.prev = null;
}
  • A doubly-linked list and a map gives us the following:
    * Time complexity: O(1)
    * Space complexity: O(n)
  • We will use head/tail, to keep track of the order when elements are retrieved or added.
    * - the “head”, which is the least recently used entry,
    * - the “tail”, which is the most recently used entry
var LRUCache = function(capacity) {
let map = {};
let head = new Node();
let tail = new Node();
this.cap = capacity;
this.size = 0;
this.map = map;
};
  • There will be two pointers per node which is relatively low cost to manage the ordering.

get(key) should return value, conditions

  • If element not found, return -1
  • If element found, we need to remove the element and insert that element to Head
  • Why Doubly linked list ? Just give a minute to think, can we search O(1) time complexity using array or Single Linked List? No , we cannot. Why ? we need to search an element in array or linked list linearly which is O(n) time Because we need to implement get(key) in O(1) time. So here the solution will be to use Doubly linked list
/** 
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
let map= this.map;
if(key in map) { // if element found
let res = map[key].val;
this.moveToHead(map[key]);
return res;
} else {
return -1; // if element not found
}
};

put(key, value) should do insertion, conditions -

  • If capacity is not full, the simply add element to list
  • If the capacity is full, then remove the least recently used element and then add new element to list
  • Why Doubly linked list ? Just give a minute to think, can we do insertion in O(1) time using Array or linked list ? so If you use array you need to shift element which is O(n) as on left side of array we have to maintain most frequently used element and on right side we need to maintain least frequently used element. So here the solution will be to use Doubly linked list
/** 
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
let map = this.map;
if(key in map) {
this.moveToHead(map[key]);
map[key].val = value;
} else {
let node = new Node(key, value);
this.moveToHead(node);
map[key] = node;
if(this.size === this.cap) {
this.removeTail();
} else {
this.size++;
}
}
};

How to move node to Head ?

  • Step 1, If node.next exist, then connect the node.next pointer to node.prev pointer
  • Step 2, point the node to head
   this.moveToHead = function(node) {
if(node.next) {
connect(node.prev, node.next); // step1
}
connect(head, node, head.next); // step 2
}

How to remove node from Tail ?

  • removing node’s key from the map
   this.removeTail = function() {
let node = tail.prev;
connect(node.prev, tail);
delete map[node.key];
}

Implementation,

var LRUCache = function(capacity) {
let map = {};
let head = new Node();
let tail = new Node();
this.cap = capacity;
this.size = 0;

var connect = function(a,b,c = null) {
a.next = b;
b.prev = a;
if(c) {
c.prev = b;
b.next = c;
}
}
connect(head, tail);

this.moveToHead = function(node) {
if(node.next) {
connect(node.prev, node.next);
}
connect(head, node, head.next);
}

this.removeTail = function() {
let node = tail.prev;
connect(node.prev, tail);
delete map[node.key];
}
this.map = map;
};
var Node = function(key = 0, val = 0) {
this.key = key;
this.val = val;
this.next = null;
this.prev = null;
}

/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
let map= this.map;
if(key in map) {
let res = map[key].val;
this.moveToHead(map[key]);
return res;
} else {
return -1;
}
};

/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
let map = this.map;
if(key in map) {
this.moveToHead(map[key]);
map[key].val = value;
} else {
let node = new Node(key, value);
this.moveToHead(node);
map[key] = node;
if(this.size === this.cap) {
this.removeTail();
} else {
this.size++;
}
}
};

Working in Walmart as UI Developer | Mentor | React | JavaScript | HTML | CSS