JSInterview30:Part 1 — Implement a LRU cache in JavaScript
A LRU cache is a data structure that can store key-value pairs and evict the least recently used item when the capacity is reached. It works by keeping track of the order of the items based on their usage, and removing the item that has not been used for the longest time when the cache is full.
Implementing LRU cache is a popular question asked in Paytm Frontend Interview Rounds.
One way to implement a LRU cache is to use a combination of a hash map and a doubly linked list. The hash map allows us to store and retrieve the key-value pairs in constant time, while the doubly linked list allows us to maintain the order of the items based on their usage. The head element of the doubly linked list would point to the most recently used entry, and the tail would point to the least recently used entry.
Explanation with Example
Here is an example of how a LRU cache with a capacity of 3 would work:
- Initially, the cache is empty and the hash map and the doubly linked list are both empty.
- We insert a key-value pair (1, A) into the cache. The hash map stores the pair as (1, node), where node is a reference to a node in the doubly linked list that contains the key and the value. The doubly linked list stores the node as the head and the tail, since it is the only node in the list.
- We insert another key-value pair (2, B) into the cache. The hash map stores the pair as (2, node), where node is a reference to a new node in the doubly linked list that contains the key and the value. The doubly linked list inserts the node at the front of the list, making it the new head and pushing the previous node to the next position.
- We insert another key-value pair (3, C) into the cache. The hash map stores the pair as (3, node), where node is a reference to a new node in the doubly linked list that contains the key and the value. The doubly linked list inserts the node at the front of the list, making it the new head and pushing the previous nodes to the next positions. The cache is now full, and the order of the items from most recently used to least recently used is (3, C), (2, B), (1, A).
- We request the value of the key 2 from the cache. The hash map returns the node that contains the key and the value. The doubly linked list moves the node to the front of the list, making it the new head and changing the order of the items to (2, B), (3, C), (1, A). The cache returns the value B.
- We request the value of the key 4 from the cache. The hash map does not have the key, so the cache returns -1 and does not change the order of the items.
- We insert a new key-value pair (4, D) into the cache. The hash map stores the pair as (4, node), where node is a reference to a new node in the doubly linked list that contains the key and the value. The doubly linked list inserts the node at the front of the list, making it the new head and pushing the previous nodes to the next positions. Since the cache is full, it evicts the least recently used item, which is the tail of the list. The hash map deletes the key-value pair that corresponds to the tail node, which is (1, A). The order of the items in the cache is now (4, D), (2, B), (3, C).
Based on above example, here are a few scenarios which we need to tackle in our final implementation:
- Scenario 1: The cache is empty and a new key-value pair is inserted. The expected behavior is that the cache should store the pair and set it as the most recently used item.
- Scenario 2: The cache is not full and a new key-value pair is inserted. The expected behavior is that the cache should store the pair and set it as the most recently used item, while keeping the existing pairs in the cache.
- Scenario 3: The cache is full and a new key-value pair is inserted. The expected behavior is that the cache should evict the least recently used item and replace it with the new pair, which should be set as the most recently used item.
- Scenario 4: The cache contains a key-value pair and the same key is requested. The expected behavior is that the cache should return the value of the key and set it as the most recently used item, while keeping the other pairs in the cache.
- Scenario 5: The cache contains a key-value pair and a different key is requested. The expected behavior is that the cache should return -1 and not change the order of the items in the cache.
Code Implementation
Now let’s implement a LRU cache based on above scenarios:
// Define a node class for the doubly linked list
class Node {
constructor(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
// Define a LRU cache class
class LRUCache {
constructor(capacity) {
this.capacity = capacity; // The maximum number of items in the cache
this.map = new Map(); // The hash map to store the key-value pairs
this.head = null; // The head of the doubly linked list
this.tail = null; // The tail of the doubly linked list
}
// Get the value of a key from the cache
get(key) {
// If the key is not in the map, return -1
if (!this.map.has(key)) {
return -1;
}
// Get the node from the map
let node = this.map.get(key);
// If the node is not the head, move it to the front of the list
if (node !== this.head) {
this.removeNode(node); // Remove the node from its current position
this.addNode(node); // Add the node to the front of the list
}
// Return the value of the node
return node.value;
}
// Put a key-value pair into the cache
put(key, value) {
// If the key is already in the map, update its value and move it to the front of the list
if (this.map.has(key)) {
let node = this.map.get(key);
node.value = value;
if (node !== this.head) {
this.removeNode(node); // Remove the node from its current position
this.addNode(node); // Add the node to the front of the list
}
} else {
// If the key is not in the map, create a new node and add it to the front of the list
let node = new Node(key, value);
this.map.set(key, node); // Add the key-value pair to the map
this.addNode(node); // Add the node to the front of the list
// If the cache is full, remove the least recently used item from the tail of the list and delete it from the map
if (this.map.size > this.capacity) {
let tail = this.tail;
this.removeNode(tail); // Remove the tail node from the list
this.map.delete(tail.key); // Delete the key-value pair from the map
}
}
}
// Helper method to remove a node from the doubly linked list
removeNode(node) {
// If the node is the head, update the head pointer
if (node === this.head) {
this.head = node.next;
}
// If the node is the tail, update the tail pointer
if (node === this.tail) {
this.tail = node.prev;
}
// If the node has a previous node, update its next pointer
if (node.prev) {
node.prev.next = node.next;
}
// If the node has a next node, update its prev pointer
if (node.next) {
node.next.prev = node.prev;
}
}
// Helper method to add a node to the front of the doubly linked list
addNode(node) {
// If the list is empty, set the node as the head and the tail
if (!this.head) {
this.head = node;
this.tail = node;
} else {
// If the list is not empty, insert the node before the head and update the head pointer
node.next = this.head;
this.head.prev = node;
this.head = node;
}
}
}
The code above implements a LRU cache with the following features:
The constructor takes a capacity parameter that specifies the maximum number of items in the cache.
The get method takes a key parameter and returns the value of the key if it is in the cache, or -1 if it is not. It also updates the order of the items in the cache based on the usage.
The put method takes a key and a value parameter and inserts or updates the key-value pair in the cache. It also updates the order of the items in the cache based on the usage. If the cache is full, it evicts the least recently used item from the cache.
The removeNode and addNode methods are helper methods that manipulate the doubly linked list.
Driver code for testing the LRU cache:
// LRU cache with capacity 3
const lru = new LRUCache (3);
lru.put(1, "A");
lru.put(2, "B");
lru.put(3, "C");
lru.put(4, "D");
console.log(lru.get(1));
console.log(lru.get(4));
/* Output:
-1
D
*/
The time complexity of the get and put methods is O(1), since they only involve constant time operations on the hash map and the doubly linked list. The space complexity of the LRU cache is O(capacity), since it stores at most capacity key-value pairs in the hash map and the doubly linked list.
Conclusion
This was simple and short explanation of LRU cache implementation in JavaScript. Hope you understand the concept well. That’s it from my end for today. Have a nice day ahead 😁
Subscribe to my YouTube channel for more content:-
