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)
Add comment