Least Recently Used (LRU) cache | Interview Question

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

  • 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

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Building LightOS with React Native

JavaScript is a dynamic computer programming language.

Building a GraphQL Server in Nestjs

Set up Lazy Loading in React Application

Arrays in Unity

Color Pop effect using BodyPix and Tensorflow.js

Simple MERN Todo

The ‘this’ keyword in JavaScript, demystified

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
iAmSonika | www.startlearncoding.com

iAmSonika | www.startlearncoding.com

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

More from Medium

Longest Substring with K Distinct Characters

AlphaCamp Leetcode 訓練營 01. 搜尋與分類

HackerRank: Common Child (JavaScript)

LeetCode — 1306 Jump Game III javascript solution (faster than 100%)