Cache With Time Limit – 2622

🔗LC2622 🟡 Medium 🧩 Pattern – Promises and Time, Map

📅 Day 17/30 Days of JavaScript

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

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

I have solved this problem in three ways.

1. Using Object to store key, value pairs
2. Map data structure – map has inbuilt methods to manage keys
3. Class with methods to solve the same

Solution using Object

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

/** 
 * @param {number} key
 * @param {number} value
 * @param {number} duration time until expiration in ms
 * @return {boolean} if un-expired key already existed
 */
TimeLimitedCache.prototype.set = function (key, value, duration) {
    const cache = this.cache
    const existingKey = cache[key];
    if (existingKey) {
        clearTimeout(existingKey.timeoutId);
    }
    const timeoutId = setTimeout(() => delete cache[key], duration)
    cache[key] = {
        value,
        timeoutId
    };
    return !!existingKey;
};

/** 
 * @param {number} key
 * @return {number} value associated with key
 */
TimeLimitedCache.prototype.get = function (key) {
    const entry = this.cache[key];
    return entry ? entry.value : -1;
};

/** 
 * @return {number} count of non-expired keys
 */
TimeLimitedCache.prototype.count = function () {
    return Object.keys(this.cache).length
};

/**
 * const timeLimitedCache = new TimeLimitedCache()
 * timeLimitedCache.set(1, 42, 1000); // false
 * timeLimitedCache.get(1) // 42
 * timeLimitedCache.count() // 1
 */

Solution using Map

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

/** * @param {number} key
 * @param {number} value
 * @param {number} duration time until expiration in ms
 * @return {boolean} if un-expired key already existed
 */
TimeLimitedCache.prototype.set = function (key, value, duration) {
    const cache = this.cache;
    const existingEntry = cache.has(key);
    if (existingEntry) {
        clearTimeout(cache.get(key).timeoutId);
    }
    const timeoutId = setTimeout(() => cache.delete(key), duration);
    cache.set(key, { value, timeoutId });
    return existingEntry;
};

/** * @param {number} key
 * @return {number} value associated with key
 */
TimeLimitedCache.prototype.get = function (key) {
    const entry = this.cache.get(key);
    return entry ? entry.value : -1;
};

/** * @return {number} count of non-expired keys
 */
TimeLimitedCache.prototype.count = function () {
    return this.cache.size;
};

Solution using Class

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

    /**
     * @param {number} key
     * @param {number} value
     * @param {number} duration time until expiration in ms
     * @return {boolean} if un-expired key already existed
     */
    set(key, value, duration) {
        const existingEntry = this.cache.has(key);
        if (existingEntry) {
            clearTimeout(this.cache.get(key).timeoutId);
        }
        const timeoutId = setTimeout(() => this.cache.delete(key), duration);
        this.cache.set(key, { value, timeoutId });
        return existingEntry;
    }

    /**
     * @param {number} key
     * @return {number} value associated with key
     */
    get(key) {
        const entry = this.cache.get(key);
        return entry ? entry.value : -1;
    }

    /**
     * @return {number} count of non-expired keys
     */
    count() {
        return this.cache.size;
    }
}