Maybe you and I have never met, but we may not have met. I am a head fish

This medium algorithm problem, I didn’t write it at the beginning

This is an online pen-based test question for the interview with Ant Financial. When I saw the question, I was overwhelmed. Subconsciously, I felt it was very difficult. The result, of course, is not written… Later, I learned that THE KEEP-alive component of Vue also uses LRU algorithm, which completely aroused my curiosity…

A little bit of experience doing algorithm problems

Don’t panic when you encounter questions that you can’t answer. Be sure to calm your mind, find out more effective information from the questions, and try to draw more pictures and write more. (If the interview is on site, remember to bring a pen and draw more pictures.

Drawing is one of the most effective ways to solve problems

Drawing is one of the most effective ways to solve problems

Drawing is one of the most effective ways to solve problems

Look at the title

leetCode

Using your knowledge of data structures, design and implement an LRU (least recently used) caching mechanism. Implement the LRUCache class:

  1. LRUCache (int capacity)Positive integerInitialize the LRU cache as capacity
  2. int get(int key) Returns the value of the keyword if it exists in the cache, otherwise -1.
  3. void put(int key, int value) If the keyword already exists, change its data value;If the keyword does not exist, insert the set of keyword-values.When the cache reaches its maximum capacity, it should delete the oldest unused data value before writing new dataTo make room for new data values.

1 and 2 are relatively simple, mainly condition 3. When the cache reaches its maximum capacity, it should delete the oldest unused data value before writing new data. Capacity corresponds to condition 1, but the key is how do you understand the longest unused?

Data is used in both read and write operations. The key that has not been used for the longest time is the key that has not been read or written for the longest time when the capacity reaches the upper limit. It’s still too raw. Let me draw a picture.

Drawing understanding

Let’s say I’m a toy merchant, and I rent a stall on the street that only has room for three toys (I can’t afford to be too poor), so most of the toys are not displayed but stored in a warehouse.

Good guy, finally a person to ask, I hurriedly put a toy in the first grid…

Business is so good, people want to ask about bikes again, because the first box is the prime location, so I put the latest ones there…

It’s so hot, I’ll soon run out of three squares…

Since the boxes are the most popular from top to bottom, I put the toys in the bottom boxes back in the warehouse to make room for new toys

Of course, if the customer wants to see the toys already in the booth, I put him in the first and hottest box

Map images

Let’s go back to the problem, and it makes a lot of sense when we look at the picture

  1. LRUCache(int capacity) Specifies the positive integer capacity used to initialize the LRU cache

  2. Constantly adjust the toy position, take toys from the warehouse to the booth and from the booth to the warehouse, which can be understood as conditions 2 and 3

Start lifting…

Method a

Use arrays and objects together

var LRUCache = function (capacity) {
  // Use an array to record the read and write order
  this.keys = []
  // Use an object to hold the key value
  this.cache = {}
  / / capacity
  this.capacity = capacity
}

LRUCache.prototype.get = function (key) {
  // If yes
  if (typeof this.cache[key] ! = ='undefined') {
    // Delete the original location
    remove(this.keys, key)
    // Move to the last one to keep access up to date
    this.keys.push(key)
    / / the return value
    return this.cache[key]
  }
  return -1
}

LRUCache.prototype.put = function (key, value) {
  if (typeof this.cache[key] ! = ='undefined') {
    // Update the existing value first
    this.cache[key] = value
    // Update the location to the last one
    remove(this.keys, key)

    this.keys.push(key)
  } else {
    // Join when it does not exist
    this.keys.push(key)
    this.cache[key] = value
    // If the capacity exceeds the maximum, delete the oldest unused key (i.e. the first key in the array).
    if (this.keys.length > this.capacity) {
      removeCache(this.cache, this.keys, this.keys[0])}}}// Remove key from array
function remove(arr, key) {
  if (arr.length) {
    const index = arr.indexOf(key)

    if (index > -1) {
      return arr.splice(index, 1)}}}// Remove the key from the cache
function removeCache(cache, keys, key) {
  cache[key] = null
  remove(keys, key)
}

const lRUCache = new LRUCache(2)

console.log(lRUCache.put(1.1)) // Cache is {1=1}
console.log(lRUCache.put(2.2)) // Cache is {1=1, 2=2}
console.log(lRUCache.get(1))    / / returns 1
console.log(lRUCache.put(3.3)) {1=1, 3=3}
console.log(lRUCache.get(2))    // return -1 (not found)
console.log(lRUCache.put(4.4)) {4=4, 3=3}
console.log(lRUCache.get(1))// return -1 (not found)
console.log(lRUCache.get(3))    / / return 3
console.log(lRUCache.get(4))/ / return 4

Copy the code

Method 2

Map implementation

In the first implementation, we use arrays to store the order of each key access (get, set), which is more difficult to implement, is there any other solution, let us more convenient, do not need to maintain the array? The values can be set sequentially with Map, and handling the LRU algorithm will be extremely convenient

/ * * *@param {number} capacity* /
var LRUCache = function (capacity) {
  this.cache = new Map(a)this.capacity = capacity
};

/ * * *@param {number} key
 * @return {number}* /
LRUCache.prototype.get = function (key) {
  if (this.cache.has(key)) {
    const value = this.cache.get(key)
    // Update the location
    this.cache.delete(key)
    this.cache.set(key, value)

    return value
  }

  return -1
};

/ * * *@param {number} key 
 * @param {number} value
 * @return {void}* /
LRUCache.prototype.put = function (key, value) {
  // If it already exists, update its location to "latest"
  // Delete first, then insert
  if (this.cache.has(key)) {
    this.cache.delete(key)
  } else {
    // Check whether size matches capacity before inserting data
    // If yes, delete the data initially inserted
    // keys() gets a traversable object. Next () gets an object of the form {value: 'XXX ', done: false}
    if (this.cache.size >= this.capacity) {
      this.cache.delete(this.cache.keys().next().value)
    }
  }

  this.cache.set(key, value)
};

const lRUCache = new LRUCache(2)

console.log(lRUCache.put(1.1)) // Cache is {1=1}
console.log(lRUCache.put(2.2)) // Cache is {1=1, 2=2}
console.log(lRUCache.get(1))    / / returns 1
console.log(lRUCache.put(3.3)) {1=1, 3=3}
console.log(lRUCache.get(2))    // return -1 (not found)
console.log(lRUCache.put(4.4)) {4=4, 3=3}
console.log(lRUCache.get(1))// return -1 (not found)
console.log(lRUCache.get(3))    / / return 3
console.log(lRUCache.get(4))/ / return 4


Copy the code

The last

I hope I can share practical, basic and advanced knowledge points with you all the time.

I look forward to your attention in nuggets: front end bighead fish, you can also find me in the public number: front end bighead fish.