Least Recently Used (LRU) Cache

Hey everyone, Today we will be solving one of the most asked questions in coding interviews which is to design a data structure for LRU cache.

It should support get and put functionality.

Get — give you the value of the key if it exists in the cache otherwise return -1.

Put — Add the value of the key if it’s not already present.

- When the cache reaches its capacity it should invalidate the least recently used item before adding the new one.

- If you put a key that already exists — replace the value of the key with the new value.

Example:

let cache = new LRUCache(3) //new cache with capacity = 2
cache.put(2, 2)
cache.put(1, 1)
cache.get(1) //returns 1
cache.put(3, 3)
cache.put(4, 4) //removes key 2
cache.get(2) // returns -1
cache.put(5, 5) //removes key 1
cache.get(1) //returns -1
cache.get(3) //returns 3
cache.get(4) //returns 4
cache.get(5) //returns 5

Approach:

Data Structure will have following properties: