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".

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

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;

  }

​

  get(key) {

    const node = this.cache[key];

    if (!node) {

      return -1;

    }

    this.moveToHead(node);

    return node.val;

  }

​

  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++;

      if (this.count > this.capacity) {

Got more time? Let's keep going.

If you had any problems with this tutorial, check out the main forum thread here.