Cache With Time Limit

Problem Statement

The task is to build a class that manages key-value pairs with a unique twist: each key has an associated expiration time specified in milliseconds. The class exposes three primary methods to interact with the key-value pairs:

1. set(key, value, duration): This method registers a key with a corresponding value and a duration. If the key already exists and hasn't expired, the method updates the value and resets the duration, returning true. If the key doesn't exist or has expired, it adds the new key-value pair with the specified duration, returning false.

2. get(key): Retrieves the value associated with a key if the key is active (not expired). If the key is not found or has expired, it returns -1.

3. count(): Counts and returns the number of keys that are currently active and have not yet expired.

This class functionality is critical in scenarios where data validity is time-sensitive, such as caching temporary user session information or limited-time offers in an e-commerce setting.

Examples

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.

Example 2

Input:

actions = ["TimeLimitedCache", "set", "set", "get", "get", "get", "count"]
values = [[], [1, 42, 50], [1, 50, 100], [1], [1], [1], []]
timeDelays = [0, 0, 40, 50, 120, 200, 250]

Output:

[null, false, true, 50, 50, -1, 0]

Explanation:

At t=0, the cache is constructed.
At t=0, a key-value pair (1: 42) is added with a time limit of 50ms. The value doesn't exist so false is returned.
At t=40, a key-value pair (1: 50) is added with a time limit of 100ms. A non-expired value already existed so true is returned and the old value was overwritten.
At t=50, get(1) is called which returned 50.
At t=120, get(1) is called which returned 50.
At t=140, key=1 expires.
At t=200, get(1) is called but the cache is empty so -1 is returned.
At t=250, count() returns 0 because the cache is empty.

Constraints

• 0 <= key, value <= 109
• 0 <= duration <= 1000
• 1 <= actions.length <= 100
• actions.length === values.length
• actions.length === timeDelays.length
• 0 <= timeDelays[i] <= 1450
• actions[i] is one of "TimeLimitedCache", "set", "get" and "count"
• First action is always "TimeLimitedCache" and must be executed immediately, with a 0-millisecond delay

Approach and Intuition

Given the functionality explained through the examples, the underlying mechanism and approach can be dissected as follows:

• Initialization: A primary object of the class TimeLimitedCache is constructed without requiring initial values. This setup phase will likely involve preparing internal storage mechanisms such as a dictionary or a hash map to store keys, values, and expiration metadata.

• Handling Set Operation:

  • When a new key-value pair is set along with its duration, the system checks if the key already exists and has not expired.
  • If the key exists and is valid, its value and duration are updated. If not, a new entry is created.
  • The return value (true or false) indicates whether an unexpired key was already present.

• Retrieving Data:

  • The get method involves checking the key's validity (i.e., it hasn't expired).
  • If valid, the value is returned; otherwise, -1 is returned indicating that the key is expired or does not exist.
  • The system needs to manage the passage of time efficiently to know when keys expire, likely using timestamps or a scheduling mechanism to update the status of keys.

• Counting Active Keys:

  • The count method involves scanning the current keys to see how many have not reached their expiration.

In both examples provided:

• The pattern demonstrates setting keys with different durations and attempting to retrieve values post their expiration to showcase the behavior when keys expire. It also deals with updating existing keys with new values and durations, highlighting how new settings effectively overwrite old ones.

• The operation's integrity depends significantly on the accurate management of time and the precision in checking and updating the expiry status of each key.

This time-limited data storage could be implemented with various data structures, but likely a combination of hashmaps (for quick access and retrieval) with min-heaps or similar structures (for efficiently managing expiration based on the least time remaining) would be ideal. Furthermore, adjusting system clocks or implementing a simulated time progression (as seen with timeDelays) is crucial for testing such time-dependent features.

Solutions

class TimedCache {
  dataStore = {};
  priorityQueue = new MinPriorityQueue();
  currentSize = 0;

  cleanseExpiredEntries() {
    const currentTime = Date.now();
    while (this.priorityQueue.size() > 0 && this.priorityQueue.front().priority < currentTime) {
      const expiredEntry = this.priorityQueue.dequeue().element;
      if (!expiredEntry.overwritten) {
        delete this.dataStore[expiredEntry.key];
        this.currentSize -= 1;
      }
    }
  };

  put(key, value, lifespan) {
    this.cleanseExpiredEntries();
    const inCache = key in this.dataStore;
    if (inCache) {
      this.dataStore[key].overwritten = true;
    } else {
      this.currentSize += 1;
    }
    const expiryTime = Date.now() + lifespan;
    const cacheEntry = { key, value, expiration: expiryTime, overwritten: false };
    this.dataStore[key] = cacheEntry;
    this.priorityQueue.enqueue(cacheEntry, expiryTime);
    return inCache;
  }

  fetch(key) {
    this.cleanseExpiredEntries();
    if (this.dataStore[key] === undefined) return -1;
    return this.dataStore[key].value;
  }

  totalItems() {
    this.cleanseExpiredEntries();
    return this.currentSize;
  }
};