The front-end will interview high frequency algorithm: LRU cache elimination algorithm

The preface

In a previous interview, the interviewer asked me this question. If you go to a page for the first time, every blog entry is recorded in the cache and can be read directly from the cache without having to request again. So let’s say the maximum size of the cache is 100, how do you design an algorithm to make sure that when the cache reaches its capacity, the earliest cache entries are eliminated?

At that time, my first reaction was to assign a label, timestamp or serial number to mark the order of storing each time I saved the container. However, it was too expensive to traverse no matter reading cache or replacing, so I came up with a more feasible method, queue.

The queue

A queue is a common data structure with a first-in, first-out (FIFO) feature. The queue is inserted at one end and deleted at the other end. Queues are certainly a viable approach for our problem. Before we get started, let’s organize our thoughts and focus on what we need to achieve.

1. The store data (PUT) and query data (GET) methods need to be implemented
2. If new data exceeds the queue capacity, delete the earliest data
3. After querying for data that exists in the queue, push the data to the beginning of the queue

So let’s start implementing the code:

/ / the queue
const List = [];

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value; }}class cacheList {
  constructor (capacity) {
    // Capacity specifies the length of the queue
    this.capacity = capacity;
  }

  isFull() {
    return List.length === this.capacity;
  }

  isNodeInList(key) {
    for (let i = 0; i < List.length; i++) {
      if (List[i].key === key) {
        returnList[i]; }}return false;
  }

  remove(key) {
    for (let i = 0; i < List.length; i++) {
      if (List[i].key === key) {
        const node = List.splice(i, 1);
        return node[0]; }}}put(key, value) {
    // Check whether the node exists. If so, update the value of the node
    if (this.isNodeInList(key)) {
	  // Remove the original node and move it to the head of the queue
      const node = this.remove(key);
      node.value = value;
      List.unshift(node);
    } else {
      if (this.isFull()) {
	    // If the queue capacity exceeds, delete the tail node
        List.pop();
      }
      List.unshift(newNode(key, value)); }}get(key) {
    if (this.isNodeInList(key)) {
	  // Move the node to the queue head
      const node = this.remove(key);;
      this.put(key, node.value);
    } else {
	  return -1; }}}Copy the code

So that’s the basic functionality, but the algorithm is definitely not just for the task, and we can see that there are some areas that can be optimized. For example, we need to traverse the queue to see if the data exists in the queue. Similarly, the location of the node needs to be traversed before deleting the node, which also means that the time complexity of our PUT and GET operations is at O(opacity). So let’s think of a better way.

HashMap + bidirectional linked list

For the case that we need to traverse each time we query the location of the node, we can map the node through hashMap, so that we can easily find the location of the node.

The bidirectional list is in the order in which we use the cache, with the node near the head being the latest and the node near the tail being the obsolete. (Question: Why use a two-way list, one-way list can not satisfy?)

Thus, the idea can be optimized to find the node’s position in a bidirectional linked list using a hashMap, and then move the node’s position by modifying prev and Next. So both put and get can optimize the time complexity to O(1). Without further ado, write code:

// Two-way linked list
class DoubleLinkedListNode {
  constructor(key, value) {
      this.key = key;
      this.value = value;
      this.prev = null;
      this.next = null; }}class LRUCache {
  constructor (capacity) {
    this.capacity = capacity;
    this.hashMap = {};
	// We need to add a false head and tail node to simplify the insert and delete operation code. We do not need to special handle the head and tail node
    this.fakeHead = new DoubleLinkedListNode(null.null);
    this.fakeTail = new DoubleLinkedListNode(null.null);
    this.fakeHead.next = this.fakeTail;
    this.fakeTail.prev = this.fakeHead;
  }

  isFull() {
    return Object.keys(this.hashMap).length === this.capacity;
  }

  remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    node.prev = null;
    node.next = null;
    return node;
  }

  add(node) {
    const firstNode = this.fakeHead.next;
    node.prev = this.fakeHead;
    node.next = firstNode;
    firstNode.prev = node;
    this.fakeHead.next = node;
  }

  put(key, value) {
    if (this.hashMap[key]) {
      const node = this.hashMap[key];
      node.value = value;
      this.add(this.remove(node));
    } else {
      if (this.isFull()) {
        const lastNode = this.fakeTail.prev;
        delete this.hashMap[lastNode.key];
        this.remove(lastNode);
      }
      const node = new DoubleLinkedListNode(key, value);
      this.hashMap[key] = node;
      this.add(node); }}get(key) {
    if (this.hashMap[key]) {
      const node = this.hashMap[key];
      this.add(this.remove(node));
      return node.value;
    } else {
      return -1; }}}Copy the code

As you can see, we no longer need to traverse to find the location of the node, and it is much easier to move the node. Going back to the question, why can’t you use a singly linked list? When you want to move a node to the head of the list or delete a node, you need to set next (Node.prev.next) of the previous node of the current node to next (Node.next) of the current node. If the list is one-way, you need to traverse to find the last node of the current node. This adds to the cost of time.

A hashMap is a Java data type consisting of arrays and linked lists, and the time complexity of a hashMap get operation is only O(1), ideally. We used JS objects to simulate the implementation of hashMap, so we can ignore this minor problem.