Implement the Least Recently Used (LRU) cache class LRUCache. The class should support the following operations
LRUCache(int capacity) Initialize the LRU cache of size capacity.
int get(int key) Return the value corresponding to the key if the key exists, otherwise return -1.
voidput(int key,int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the introduction of the new pair causes the cache to exceed its capacity, remove the least recently used key.
A key is considered used if a get or a put operation is called on it.
let's take this and brainstorm our implementation part:
get(key)
If the key exists, return its value and mark it as recently used.
If the key does not exist, return -1.
If the key exists:
Mark the key as recently used:
In a Map, remove the key and reinsert it , to refresh its order.
Return its value.
If the key does not exist:
Return -1.
put(key, value)
Add or update a key-value pair in the cache.
If the cache exceeds its capacity, remove the least recently used key before adding a new one.
If the key exists:
Update its value and mark it as recently used (refresh its order).
If the key does not exist:
Check if the cache has reached its capacity:
If yes, remove the least recently used key (the first key in the Map).
Insert the new key-value pair into the cache.
class LRUCache {
/**
* @param {number} capacity
*/
constructor(capacity) {
this.cache = new Map()
this.capacity = capacity
}
\
get(key) {
/*
If the key exists,return its value and mark it as recently used.
If the key does not exist, return -1.
*/
if (!this.cache.get(key)) {
return -1
}
// how to mark the key as recently used?
// order in the map, early on has least used, and later is used more recently
const value = this.cache.get(key)
this.cache.delete(key)
this.cache.set(key, value)
return value
}
put(key, value) {
/*
Add or update a key-value pair in the cache,and update the order
If the cache exceeds its capacity, remove the least recently used key before adding a new one.
*/
if(this.cache.has(key)){
this.cache.delete(key)
}else if(this.cache.size >= this.capacity){
const leastRecentlyUsedKey = this.cache.keys().next().value
this.cache.delete(leastRecentlyUsedKey)
}
this.cache.set(key, value)
}
}
The Map object in JavaScript is a powerful and versatile data structure that has several unique properties, making it ideal for problems like the LRU Cache and many others.
Let's break down its nature, advantages, and some ideas we can use beyond the LRU Cache.
Nature of Map
This question a
Key-Value Storage A Map stores key-value pairs
Unlike plain JavaScript objects ({}), the keys in a Map can be any data type—strings, numbers, objects, or even functions
const map = new Map();
map.set('key1', 'value1'); // Key is a string
map.set(123, 'value2'); // Key is a number
map.set({ id: 1 }, 'value3'); // Key is an object
console.log(map.get('key1')); // Output: value1
console.log(map.get(123)); // Output: value2
.Preserves Insertion Order: The Map maintains the insertion order of keys. This means:
The first key added will always come first when iterating over the Map.
When you delete and re-add a key, it moves to the end of the order.
This is why it's useful for tracking the Least Recently Used (LRU) item in the LRU Cache problem.
Implement the Least Recently Used (LRU) cache class LRUCache. The class should support the following operations
A key is considered used if a get or a put operation is called on it.
Ensure that get and put each run in O(1)
O(1) average time complexity.
Example 1:
Input: ["LRUCache", [2], "put", [1, 10], "get", [1], "put", [2, 20], "put", [3, 30], "get", [2], "get", [1]] Output: [null, null, 10, null, null, 20, -1] Explanation: LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 10); // cache: {1=10} lRUCache.get(1); // return 10 lRUCache.put(2, 20); // cache: {1=10, 2=20} lRUCache.put(3, 30); // cache: {2=20, 3=30}, key=1 was evicted lRUCache.get(2); // returns 20 lRUCache.get(1); // return -1 (not found)class LRUCache { /** * @param {number} capacity */ constructor(capacity) {} /** * @param {number} key * @return {number} */ get(key) {} /** * @param {number} key * @param {number} value * @return {void} */ put(key, value) {} }let's take this and brainstorm our implementation part:
class LRUCache { /** * @param {number} capacity */ constructor(capacity) { this.cache = new Map() this.capacity = capacity } \ get(key) { /* If the key exists,return its value and mark it as recently used. If the key does not exist, return -1. */ if (!this.cache.get(key)) { return -1 } // how to mark the key as recently used? // order in the map, early on has least used, and later is used more recently const value = this.cache.get(key) this.cache.delete(key) this.cache.set(key, value) return value } put(key, value) { /* Add or update a key-value pair in the cache,and update the order If the cache exceeds its capacity, remove the least recently used key before adding a new one. */ if(this.cache.has(key)){ this.cache.delete(key) }else if(this.cache.size >= this.capacity){ const leastRecentlyUsedKey = this.cache.keys().next().value this.cache.delete(leastRecentlyUsedKey) } this.cache.set(key, value) } }The Map object in JavaScript is a powerful and versatile data structure that has several unique properties, making it ideal for problems like the LRU Cache and many others.
Let's break down its nature, advantages, and some ideas we can use beyond the LRU Cache.
Nature of Map
This question a
const map = new Map(); map.set('key1', 'value1'); // Key is a string map.set(123, 'value2'); // Key is a number map.set({ id: 1 }, 'value3'); // Key is an object console.log(map.get('key1')); // Output: value1 console.log(map.get(123)); // Output: value2This question can also be solved using double linked list which we will cover in next thread.