# Least Recently Used (LRU) cache | Interview Question

`Input["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"][, [1, 1], [2, 2], , [3, 3], , [4, 4], , , ]Output[null, null, null, 1, null, -1, null, -1, 3, 4]ExplanationLRUCache 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 1lRUCache.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 3lRUCache.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 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++;        }    }};`

--

--

--

## More from iAmSonika | www.startlearncoding.com

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

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

## Building LightOS with React Native ## JavaScript is a dynamic computer programming language. ## Building a GraphQL Server in Nestjs  ## Arrays in Unity ## Color Pop effect using BodyPix and Tensorflow.js ## Simple MERN Todo ## The ‘this’ keyword in JavaScript, demystified  ## iAmSonika | www.startlearncoding.com

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

## Longest Substring with K Distinct Characters ## HackerRank: Common Child (JavaScript) ## LeetCode — 1306 Jump Game III javascript solution (faster than 100%) 