Design A Least Recently Used (LRU) Cache

A cache (pronounced cash) is a place of storage that allows for faster data retrieval. Separate from the main data storage, it's usually faster memory that houses frequently accessed values.

With a cache in place, when a client application needs to access data, it'll check the cache first before going to main memory. As an example, web browsers will typically download a page once, and refer to its cached assets in future calls to help speed up the experience.

To determine whether something should be cached, a few eviction strategies are used. IBM refers to eviction as "a feature where file data blocks in the cache are released when fileset usage exceeds the fileset soft quota, and space is created for new files". The process of releasing blocks is called eviction.

One of the most common is LRU, or Least Recently Used. It's exactly as it sounds-- we keep track of usage so that we can "evict" the least recently used key.

Can you implement a LRU Cache where the following code would properly work with some constraints?

// initialize with a capacity of 3 keys
const cache = new Cache(3);
cache.put(1, 1);
cache.put(2, 4);
cache.put(3, 9);
cache.get(1);      // returns 1
cache.put(4, 16);  // evicts key 2
cache.get(2);      // returns -1

# initialize with a capacity of 3 keys
cache = Cache(3)
cache.put(1, 1)
cache.put(2, 4)
cache.put(3, 9)
cache.get(1)      # returns 1
cache.put(4, 16)  # evicts key 2
cache.get(2)      # returns -1

The put and get methods should have a time complexity of O(1).

Constraints

• The cache size will be <= 100000
• The key and value will have values between -1000000000 and 1000000000

```js
class Cache {
  constructor(capacity) {
    // do something
  }
}

const cache = new Cache(3);
cache.put(1, 1);
cache.put(2, 4);
cache.put(3, 9);
cache.get(1);      // returns 1
cache.put(4, 16);  // evicts key 2
cache.get(2);      // returns -1
```

Let's start by laying out our requirements. We're implementing a cache with a get method and a put method. There are several other methods that we want in a production cache class, but this will do for now.

1. get(key) needs to do a lookup of the key in the cache. If it does not find the key, we'll return a -1 for "not found".

2. put(key, val) needs to insert the key if it's not in the cache. If the cache has reached capacity, it needs to invalidate the least recently used key.

There are a few ways to have get and put operate in constant time. Let's think of data structures we can use that support quick access. One easy way is to use a hash table data structure, which enables lookups in O(1) time. We set the keys and values of the cache to be a hash table/hash map, and retrieval speed is taken care of.

What about put? We'll also want our addition and eviction operations to run in constant time as well. A data structure we could introduce for this is a doubly linked list. A doubly linked list node is unique in that it has references to both the next node in the list, as well as the previous node. How does that help us? We'll see in a bit!

We get a decent hash table for free, built into many programming languages already. In the case of dynamic languages, we can use objects in JS or dictionaries in Python, so let's jump to implementing a doubly linked list. Here's what a DLinkedNode definition might look like:

class DLinkedNode {
    constructor(key, val, pre, next) {
        this.key = key;
        this.val = val;
        this.pre = pre;
        this.next = next;
    }
}

class DLinkedNode:
    def __init__(self, key, val, pre, next):
        self.key = key
        self.val = val
        self.pre = pre
        self.next = next

With that, we can initialize doubly linked list nodes easily by calling new DLinkedNode(key, value, null, null).

In the Cache class, we'll also want to add the standard addNode and removeNode helper methods, as we'll be doing that quite a bit. addNode specifically adds a new node to the head of the doubly linked list. removeNode removes it place by manipulating the pre and next values of its neighbors.

class DLinkedNode {
    constructor(key, val, pre, next) {
        this.key = key;
        this.val = val;
        this.pre = pre;
        this.next = next;
    }
}

// for our Cache class
addNode(node) {
    node.pre = this.head;
    node.next = this.head.next;
    this.head.next.pre = node;
    this.head.next = node;
};

removeNode(node) {
    // take a node's predecessor
    const pre = node.pre;
    // find the node after it
    const next = node.next;
    // assign the predecessor's "next" node as the one after current
    pre.next = next;
    next.pre = pre;
};

class DLinkedNode:
    def __init__(self, key, val, pre, next):
        self.key = key
        self.val = val
        self.pre = pre
        self.next = next

# for our Cache class
def addNode(node):
    node.pre = self.head
    node.next = self.head.next
    self.head.next.pre = node
    self.head.next = node

def removeNode(node):
    # take a node's predecessor
    pre = node.pre
    # find the node after it
    next = node.next
    # assign the predecessor's "next" node as the one after current
    pre.next = next
    next.pre = pre

Now, when we new up a Cache instance, we'll want certain things predefined in the constructor. Let's flesh that out:

1. We'll need a reference to the capacity
2. A count for the number of keys we have
3. The cache via a hash table itself
4. References to the heads and tails of the doubly linked list

class Cache {
  constructor(capacity) {
    this.count = 0;
    this.capacity = capacity;
    this.cache = {};
    this.head = new DLinkedNode();
    this.head.pre = null;
    this.tail = new DLinkedNode();
    this.tail.next = null;
    this.head.next = this.tail;
    this.tail.pre = this.head;
  }
}

class Cache:
    def __init__(capacity):
        self.count = 0
        self.capacity = capacity
        self.cache = {}
        self.head = DLinkedNode()
        self.head.pre = null
        self.tail = DLinkedNode()
        self.tail.next = None
        self.head.next = self.tail
        self.tail.pre = self.head

We're now in business. Let's start adding stuff by implementing the put method. put should check if the value exists or not in this.cache based on the key. If it doesn't, we can add it in.

However, it's not enough to just add it in-- the whole reason for using a doubly linked list is also to see the order of use. Thus, if we're adding a new value, it means that it's the most recently used, and we should thus move it to the front of the linked list. This serves to be an indication that we should NOT evict it.

put checks if the node is in the cache. If it's not, we create a new node in the doubly linked list (added to the head), and increment our length. We also check at this point if we're over capacity-- if we are, we get rid of the node at the tail, as it's the least recently used.

Alternatively, if the node already exists, we simply overwrite the existing node value and move it to the start.

class Cache {
  constructor(capacity) {
    this.count = 0;
    this.capacity = capacity;
    this.cache = {};
    this.head = new DLinkedNode();
    this.head.pre = null;
    this.tail = new DLinkedNode();
    this.tail.next = null;
    this.head.next = this.tail;
    this.tail.pre = this.head;
  }

  put(key, value) {
    const node = this.cache[key];
    if (!node) {
      const newNode = new DLinkedNode(key, value, null, null);
      this.cache[key] = newNode;
      this.addNode(newNode);
      this.count++;
      // the overcapacity scenario
      // evict the value at the end of the linked list
      if (this.count > this.capacity) {
        const tail = this.popTail();
        delete this.cache[tail.key];
        this.count--;
      }
    } else {
      node.val = value;
      // move to head as it's the most recently used
      this.moveToHead(node);
    }
  }
}

class Cache:
    def __init__(capacity):
        self.count = 0
        self.capacity = capacity
        self.cache = {}
        self.head = DLinkedNode()
        self.head.pre = null
        self.tail = DLinkedNode()
        self.tail.next = None
        self.head.next = self.tail
        self.tail.pre = self.head

    def put(key, value):
        node = self.cache[key]
        if not node:
            new_node = DLinkedNode(key, value, None, None)
            self.cache[key] = new_node
            self.addNode(new_node)
            self.count += 1
            # the overcapacity scenario
            # evict the value at the end of the linked list
            if self.count > self.capacity:
                tail = self.popTail()
                self.cache.pop(tail.key)
                self.count -= 1
        else:
            node.val = value
            # move to head as it's the most recently used
            self.moveToHead(node)

Two helper functions are used above, one of which is moveToHead. This simply removes the node and re-adds it to the front, moving it ahead and letting us know it was the most recently used key.

moveToHead(node) {
    this.removeNode(node);
    this.addNode(node);
};

def moveToHead(self, node):
    self.removeNode(node)
    self.addNode(node)

Notice we also used a popTail method-- this function will be used for evicting nodes.

popTail(node) {
  const pre = this.tail.pre;
  this.removeNode(pre);
  return pre;
}

def popTail(node):
    pre = self.tail.pre
    self.removeNode(pre)
    return pre

Let's implement get! All get needs to do is find a key in this.cache. If found, we moveToHead to let keep it as the most recently used key, and return it. Otherwise, we return -1.

get(key) {
    const node = this.cache[key];
    if (!node) {
        return -1;
    }
    this.moveToHead(node);
    return node.val;
};

def get(key):
    node = this.cache[key]
    if not node:
        return -1
    self.moveToHead(node)
    return node.val

Not too bad! Let's see it all put together.

One Pager Cheat Sheet

• Yes, it is possible to implement a LRU Cache with the mentioned constraints, where the put and get methods have a time complexity of O(1).
• We are setting up a cache that has a get and put method using a hash table and doubly linked list data structure for lookups and insertion in constant time.
• We can dynamically construct a DLinkedNode and use addNode and removeNode to add and remove nodes to/from the head of a doubly linked list.
• We need to new up a Cache instance with reference to the capacity, a count for keys, the cache itself, and references to the heads and tails of the doubly linked list.
• We put the new value in the cache and move it to the front of the doubly linked list if it exists, or create a new node if it doesn't, as well as evict nodes from the tail if we're over capacity to ensure the order of use is maintained.
• The moveToHead function removes and re-adds a node to the front of a list, letting us know it was the most recently used key.
• We get a key from the cache and moveToHead if found, otherwise return -1.
• The performance of the bold new product was "not too bad".