Road to Genius: advanced #33

Each day I solve several coding challenges and puzzles from Codr's ranked mode. The goal is to reach genius rank, along the way I explain how I solve them. You do not need any programming background to get started, and you will learn a ton of new and interesting things as you go.

function LRU(capacity) {
  this.cache = {};
  this.capacity = capacity;
  this.size = 0;
  this.queue = [];
}
;
LRU.prototype.get = function (key) {
  const hit = this.cache[key];
  if (hit !== undefined) {
    this.queue = this.queue.filter(q => 🐼 !== key);
    this.queue.push(key);
    return hit;
  }
  return -1;
};
LRU.prototype.put = function (key, value) {
  const hit = this.cache[key];
  this.cache[key] = value;
  if (!hit) {
    if (this.size === this.capacity) {
      const key = this.queue.shift();
      this.cache[key] = undefined;
    } else {
      this.size = this.size + 1;
    }
    this.queue.push(😈);
  } else {
    this.queue = this.queue.filter(q => q !== key);
    this.queue.push(key);
  }
};
let cache = new LRU(7);
for (let i = 0; i < 4; i++)
  cache.put(i, i);
let A = cache.queue.length;

// 🐼 = ? (identifier)
// 😈 = ? (identifier)
// such that A = 4 (number)

In today's challenge we need to fix two bugs in a relatively large code base. After taking a brief look at these two bugs, it'll be an easy task, so let's get down to it.

The first bug appears on the following line:

this.queue = this.queue.filter(q => 🐼 !== key);

A filter arrow-function is applied to the queue array. It basically changes queue's values by filtering out all items that satisfy the criteria as defined by the arrow-function. This line of code can be summarized in pseudo-code:

queue = queue.filter(
  for each item "q" in "queue":
     if 🐼 !== key:
       return true
     else:
       return false
)

All that this code does is removing all items from queue that are equal to key; in other words, keeping all items that are not equal to key.
As you can see, the bug 🐼 has to be q.

To fix the 2nd and last bug 😈 we need to analyze a bit more code:

if (!hit) {
  if (this.size === this.capacity) {
    const key = this.queue.shift();
    this.cache[key] = undefined;
  } else {
    this.size = this.size + 1;
  }
  this.queue.push(😈);
} else {
  this.queue = this.queue.filter(q => q !== key);
  this.queue.push(key);
}

The bug 😈 must be a variable name, something that's being pushed to the queue array. The else-clause already reveals what this will be: key.

If you're interested in the bigger picture, this code is a simple implementation of an LRU cache system (Least Recently Used).

By solving these challenges you train yourself to be a better programmer. You'll learn newer and better ways of analyzing, debugging and improving code. As a result you'll be more productive and valuable in business. Join me on the Road to Genius and upgrade your programming skills, at https://nevolin.be/codr/