A: hi! ~ Hello, everyone, I am YK bacteria 🐷, a front-end microsystem ✨, like to share their small knowledge 🏹, welcome to follow me 😘 ~ [wechat account: YK2012YK2012, wechat official account: ykyk2012]
“This is the 30th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”
The interviewer asked me if I knew about LRU cache, and asked me to implement a JavaScript version of… I said I’d heard of it, but I might not be able to do it, so I switched to a simple reverse list. Although write out simple question, but the backhand still give me to hang ~ the second time encounter is quick hand second face, the interviewer asked me to know LRU cache? I said I knew a little bit, and then he said it’s ok if you don’t know. I told you, I explained to me what LRU is, and then told me what function I want to achieve, and then I did it under the guidance of the interviewer. Of course, I passed the interview in the last round
146. LRU caching mechanism
Using your knowledge of data structures, design and implement an LRU (least recently used) caching mechanism.
Implement the LRUCache class:
LRUCache(int capacity)Initialize the LRU cache as a positive integer capacityint get(int key)Returns the value of the keyword if it exists in the cache, otherwise -1void put(int key, int value)If the keyword already exists, change its data value; If the keyword does not exist, the set of keyword – values is inserted. When the cache reaches its maximum capacity, it should delete the oldest unused data values before writing new data to make room for new data values
The sample
- The input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
- The output
[null, null, null, 1, null, -1, null, -1, 3, 4]
- explain
1. LRUCache lRUCache = new LRUCache(2);
2. lRUCache.put(1.1); // Cache is {1=1}
3. lRUCache.put(2.2); // Cache is {1=1, 2=2}
4. lRUCache.get(1); / / returns 1
5. lRUCache.put(3.3); {1=1, 3=3}
6. lRUCache.get(2); // return -1 (not found)
7. lRUCache.put(4.4); {4=4, 3=3}
8. lRUCache.get(1); // return -1 (not found)
9. lRUCache.get(3); / / return 3
10. lRUCache.get(4); / / return 4
Copy the codeAnalyze and implement the least recently used cache mechanism. There are two operations, one is get read data, one is PUT write data or update data. The capacity of this cache is limited, that is, the data that has not been read or updated (put) will be deleted. In other words, the data that has been read or updated will be updated.
The next step is to choose which data structure to use. We can imagine if the data is never read, then this is like a queue
And then if GET reads the data, the data will change, and it will move to the far right of the queue
Ok, let’s take a closer look at the read and write operations
Get Reads data: looks for a location in the cache. If found, moves the data to the right and returns it. If not found, return -1
Put: Finds a location in the cache, if any, performs an update operation, updates the value and moves the data to the far right; If not, add new data to the far right; Here, add operations are divided into two cases. One is to add data directly when the capacity is not full; the other is to delete data on the left when the capacity is full.
The data operations involved here are:
① Search involves key value pairs, and search, it is easy to think of is to use a JS object to store key value pairs
② Moving involves data structures that move frequently. We think of linked lists
Delete the nodes on the side of the linked list, we think of a bidirectional list
Our final data structure should look something like this
For details on how to implement bidirectional lists, see this blog post: Designing a bidirectional list II — Implementing a Bidirectional list in JavaScript — Digging Gold (Juejin. Cn)
In this way, the operation of deleting, adding and moving data is to change the various Pointers of the linked list
【 solution 1 】 bidirectional linked list
First, we define a node class in a bidirectional linked list. The node stores both key and value data
class ListNode {
constructor(key, value) {
this.key = key
this.value = value
this.next = null
this.prev = null}}Copy the codeThen we start defining our defining LRU caching mechanism
class LRUCache {
// Cache constructor
constructor(capacity) {
// Set the cache capacity, which is used to store the empty objects of key-value pairs and the amount of data stored in the current cache
this.capacity = capacity;
this.hash = {};
this.count = 0;
// Define the virtual head and tail of the bidirectional list
this.dummyHead = new ListNode();
this.dummyTail = new ListNode();
// Associate the nodes together
this.dummyHead.next = this.dummyTail;
this.dummyTail.prev = this.dummyHead;
}
// Let's start by defining some caching methods
// get to get the element
get(key) {
// Get the node directly from the object
let node = this.hash[key];
// Return -1 if not found
if (node === null) {
return -1;
} else {
// Move the node to the head of the list (delete the node and add it to the head)
this.removeFromList(node);
this.addToHead(node);
// Then return the value of this object
returnnode.value; }}put(key, value) {
// Now look for the node in the object
let node = this.hash[key];
// Add if it cannot be found
if (node == null) {
// If the cache is full, remove the tail node
if (this.count == this.capacity) {
let tail = this.dummyTail.prev;
this.removeFromList(tail);
// Delete the mapping in the object
delete this.hash[tail.key];
// The number of cached data is reduced by one
this.count--;
}
// If the cache is not full, create a new node
let newNode = new ListNode(key, value);
// Create a mapping in the object
this.hash[key] = newNode;
// Add the list header
this.addToHead(newNode);
// The number of cached data is increased by one
this.count++;
} else {
// Select * from 'update';
node.value = value;
this.removeFromList(node);
this.addToHead(node); }}// Delete a node from the list
removeFromList(node) {
let temp1 = node.prev;
let temp2 = node.next;
temp1.next = temp2;
temp2.prev = temp1;
}
// Add a node to the head of the list
addToHead(node) {
node.prev = this.dummyHead;
node.next = this.dummyHead.next;
this.dummyHead.next.prev = node;
this.dummyHead.next = node; }}Copy the code【 答 案 】 B
An LRU cache can be easily implemented in JavaScript with the help of some API in the Map data structure
One major difference between the Map and Object types is that Map instances maintain the insertion order of key-value pairs, so they can iterate based on the insertion order.
Keys () and values() return iterators that generate keys and values in insertion order, respectively
How do you move an element to the top, using the same logic we did above with a double-linked list, just delete the element and then insert it again
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map(a); }get(key) {
if (this.map.has(key)) {
let temp = this.map.get(key);
// Remove the element from the map
this.map.delete(key);
// Then insert it back into the map
this.map.set(key, temp);
return temp;
} else {
return -1; }}put(key, value) {
if (this.map.has(key)) {
this.map.delete(key);
}
this.map.set(key, value);
if (this.map.size > this.capacity) {
// Remove the oldest node, i.e. the element inserted first. Map. keys produces an iterator, so use next to get the first element
this.map.delete(this.map.keys().next().value); }}}Copy the codeGuess what version I wrote in the interview?
Finally, welcome to my column and make friends with YK bacteria