Least Recently Used 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 –

• Capacity
• Map – key value pairs
• Doubly Linked List – to keep track of least recently used item

get ( key ) –

~Check if the item is present in the map~

~if(not present) return -1~

~else

~value = map[key]~

~move the key to the end of the Doubly linked list~

put ( key, value ) –

~if (key already present in map)~

~ change the value of key to the new value~

~else ~

~check if map.size === capacity~

~if(yes)~

~itemToRemove = head of DoublyLinkedList~

~delete itemToRemove from map~

~move the head pointer to the head.next node~

~make a new node with {value, key}~

~add it to the map~

~add this node to the tail of the DoublyLinkedList~

Code –

let LRUCache = function(capacity){
	this.capacity = capacity
	this.map = new Map()
	
	this.head = {}
	this.tail = {}

	this.head.next = this.tail
	this.tail.prev = this.head
}

LRUCache.prototype.get = function(key){
	if(this.map.has(key)){
		let item = this.map.get(key)
	
		//move item from its position to the tail in the 
		//linked list	
		item.prev.next = item.next
		item.next.prev = item.prev
		
		this.tail.prev.next = item
		item.prev = this.tail.prev
		item.next = this.tail
		this.tail.prev = item
		return item.value
	} else {
		return -1
	}
}

LRUCache.prototype.put = function(key, value){
	// if key already present
	if(this.get(key) !== -1){
	//assign the new value to the key
		this.map.get(key).value = value
	} else {
		if(this.map.size === this.capacity){
			this.map.delete(this.head.next.key)
			this.head.next = this.head.next.next
			this.head.next.prev = this.head
		}
		
		let newNode = { value, key }
		
		this.map.set(key, newNode)
		this.tail.prev.next = newNode
		newNode.prev = this.tail.prev
		newNode.next = this.tail
		this.tail.prev = newNode
	}
}

Time Complexity – O(1)

Space Complexity – O(n)