[Medium] LeetCode JS 30 - 2622. Cache with Time Limit

Question Prompt

Write a class that allows getting and setting key-value pairs, however a time until expiration is associated with each key.

The class has three public methods:

• set(key, value, duration): accepts an integer key, an integer value, and a duration in milliseconds. Once the duration has elapsed, the key should be inaccessible. The method should return true if the same un-expired key already exists and false otherwise. Both the value and duration should be overwritten if the key already exists.
• get(key): if an un-expired key exists, it should return the associated value. Otherwise it should return -1.
• count(): returns the count of un-expired keys.

Example 1:

Input:
actions = ["TimeLimitedCache", "set", "get", "count", "get"]
values = [[], [1, 42, 100], [1], [], [1]]
timeDelays = [0, 0, 50, 50, 150]
Output: [null, false, 42, 1, -1]
Explanation:
At t=0, the cache is constructed.
At t=0, a key-value pair (1: 42) is added with a time limit of 100ms. The value doesn't exist so false is returned.
At t=50, key=1 is requested and the value of 42 is returned.
At t=50, count() is called and there is one active key in the cache.
At t=100, key=1 expires.
At t=150, get(1) is called but -1 is returned because the cache is empty.

Solutions

Looking to practice more questions like these? We recommend GreatFrontEnd, the best platform for honing your frontend interview skills!

To implement the TimeLimitedCach, we will need to first have a Map to store the key-value pairs. Then, in the set method, we store a value in the cache, associated with a key, and sets a timer to remove it after a specified duration.

In addition, as the question prompt specified, we need to checks if the key already exists in the cache. Thus, we use const found = this.cache.has(key) to see if it’s already existed. If yes, clear any existing timer associated with that key (to overwrite with a new duration) by doing clearTimeout(this.cache.get(key).timerId).

Then, we use this.cache.set(key, { ... }) to store or update the key with an object containing: value (the actual data to be cached) and the timerId (a reference to the timeout created using setTimeout.). We need to use setTimeout here because we need to set a timer that will automatically remove the key (and the associated data) from the cache after the duration

For the get method, it is used to retrieve the value associated with a key from the cache. We first check if the key exists in the cache by doing if (this.cache.has(key)) { ... }. If yes, we return it. If not, we return -1

Last, the count method simply return the current number of items within the cache. Since we use Map as the cache, we can directly use the size property to get the cound.

var TimeLimitedCache = function () {
  this.cache = new Map();
};

TimeLimitedCache.prototype.set = function (key, value, duration) {
  const found = this.cache.has(key);
  if (found) {
    clearTimeout(this.cache.get(key).timerId);
  }
  this.cache.set(key, {
    value,
    timerId: setTimeout(() => this.cache.delete(key), duration),
  });
  return found;
};

TimeLimitedCache.prototype.get = function (key) {
  if (this.cache.has(key)) {
    return this.cache.get(key).value;
  } else {
    return -1;
  }
};

TimeLimitedCache.prototype.count = function () {
  return this.cache.size;
};

Or we can rewrite it using the class syntax

class TimeLimitedCache {
  constructor() {
    this.cache = new Map();
  }

  set(key, value, duration) {
    const found = this.cache.has(key);

    if (found) {
      clearTimeout(this.cache.get(key).timerId);
    }

    this.cache.set(key, {
      value,
      value,
      timerId: setTimeout(() => {
        this.cache.delete(key);
      }, duration),
    });

    return found;
  }

  get(key) {
    return this.cache.has(key) ? this.cache.get(key).value : -1;
  }

  count() {
    return this.cache.size;
  }
}