2622. Cache With Time Limit

Problem Description

In this problem, we are tasked with designing a class TimeLimitedCache that supports setting and getting key-value pairs with an expiration time. When you set a key with a value, you also specify how long (in milliseconds) that key should be valid. After this duration has elapsed, the key should be considered expired and should not be accessible.

There are three public methods we need to implement:

1. set(key, value, duration): Saves a key with associated value and an expiration time in milliseconds. If this key already exists and has not yet expired, update the value and duration, returning true; if the key is new or has expired, return false. After duration milliseconds, the key should expire and no longer be accessible.

2. get(key): Retrieves the value associated with a key if the key is unexpired. If the key does not exist or has expired, it should return -1.

3. count(): Returns the number of keys that are currently unexpired in the cache.

Every time we interact with the cache (through set, get, or count), we must also ensure that any expired keys are removed.

Intuition

The solution requires us to keep track of the expiration time for each key, in addition to the value associated with it. The simplest approach is to use a data structure that provides efficient access to the keys, values, and their respective expiration times. A Map is a suitable data structure for this, which in TypeScript can be used to map a key to a tuple containing the value and the expiration time (calculated as the current time plus the duration).

Here is the thought process behind the solution:

1. Storing Key-Value Pairs with Expiration: A Map object is used to store the key paired with a tuple of value and the expiration timestamp.

2. Handling Expiration: Every time the set, get, or count method is called, we first remove expired keys. This is done by iterating over the map entries and checking the current time against the expiration time of each key. If the current time is greater than or equal to the expiration time, the key is deleted.

3. Set Method: For the set method, we first remove expired keys, then we check if the key already exists in the cache. If it does exist, we overwrite its value and expiration time and return true. If it doesn't exist or has expired and was removed, we set the new value and expiration time and return false.

4. Get Method: For the get method, we first remove expired keys. Then we attempt to retrieve the value associated with the key. If the key is found and isn't expired, we return the value; if not, we return -1.

5. Count Method: For the count method, we first remove expired keys, then simply return the number of keys currently in the cache (which doesn't include expired keys as they have been removed).

The solution is straightforward, ensuring that at each operation, the cache automatically cleans up expired keys. This keeps the cache's size in check and ensures that all the accessible keys are valid according to the duration that was specified when they were set.

Solution Approach

In our solution, we've crafted a TimeLimitedCache class that employs algorithmic patterns and data structures to achieve the desired functionality. Let's walk through the implementation step by step.

1. Using a Map Data Structure: We use a Map to store the keys and their associated values and expiration times. The Map's key is the integer key provided by the user, and the value is a tuple consisting of the value given by the user and the calculated expiration timestamp. This makes retrieval, updating, and deletion operations efficient.

2. Timestamp Calculation: To determine when a key should expire, we compute an expiration timestamp by adding the current time (new Date().getTime()) to the duration (in milliseconds).

3. Automatic Expiration Handling: Each public method (set, get, and count) starts by invoking the removeExpire method. This method iterates through all entries in the map, compares the current time with the stored expiration timestamp, and removes any entry that has expired.

4. set Method:

   • Invoke removeExpire to ensure we're working with a fresh, unexpired set of keys.
   • Check if the key exists with the method this.cache.has(key).
   • Update the map with the new value and expiration timestamp.
   • Return the result of the has check which indicates if the key already existed.

   1set(key: number, value: number, duration: number): boolean {
   2    this.removeExpire();
   3    const ans = this.cache.has(key);
   4    this.cache.set(key, [value, this.now() + duration]);
   5    return ans;
   6}

5. get Method:

   • Invoke removeExpire to clear expired keys.
   • Retrieve the value associated with key if it exists and return it.
   • If the key does not exist or has expired, return -1.

   1get(key: number): number {
   2    this.removeExpire();
   3    return this.cache.get(key)?.[0] ?? -1;
   4}

6. count Method:

   • Call removeExpire to remove expired keys.
   • Return the count of the entries in the map, which now only includes unexpired keys.

   1count(): number {
   2    this.removeExpire();
   3    return this.cache.size;
   4}

7. Private Helper Methods:

   • now(): Returns the current time in milliseconds since the Unix epoch.
   • removeExpire(): Removes expired keys from the map by iterating over the entries and deleting those with an expiration date that has passed.

Overall, this implementation is efficient because it performs cleanup lazily, only when necessary. By leveraging the Map data structure and calculating the expiration dynamically, this approach keeps the usage straightforward while managing the time-sensitive aspect of the key-value store.

Example Walkthrough

Let's illustrate the solution approach by walking through a small example step by step.

1. Instantiate TimeLimitedCache: First, we create an instance of the TimeLimitedCache class.

   1const cache = new TimeLimitedCache();

2. Setting a Value with Expiration: We save a key-value pair with a specific expiration duration in the cache. For instance, we set the key 1 to the value 10 with an expiration of 3000 milliseconds (or 3 seconds).

   1cache.set(1, 10, 3000); // returns false as the key is new and therefore not already existing

   At this point, the cache will contain one key, 1, which will expire after 3 seconds.

3. Setting an Existing Key Before Expiry: Suppose we quickly set another value to the same key before it expires, let's say after 1 second with a new duration.

   1setTimeout(() => cache.set(1, 15, 4000), 1000); // returns true as the key existed before and was updated

   The key 1 now has a new value, 15, and its expiration is extended by another 4 seconds from the point of this set operation.

4. Getting a Value Before Expiry: We attempt to get the value of key 1 while it is still unexpired.

   1setTimeout(() => console.log(cache.get(1)), 1500); // outputs 15, since the key is still valid

   Since the key is still valid, it returns the value 15.

5. Count Unexpired Keys: If we want to know how many unexpired keys are in our cache, we could call count.

   1console.log(cache.count()); // outputs 1 as there is only one unexpired key

6. Attempting to Get Value After Expiry: If we wait for longer than the expiration duration and then try to get the value of key 1, it should be expired and hence return -1.

   1setTimeout(() => console.log(cache.get(1)), 5000); // outputs -1, since the key has expired

7. Count After Expiry: After key 1 has expired and we check the count of unexpired keys, it should now be 0.

   1setTimeout(() => console.log(cache.count()), 5000); // outputs 0 since key `1` has expired

This example demonstrates how the TimeLimitedCache works in practice. Keys are set with a value and an expiration duration, and they can be updated as long as they haven't expired. The get method will retrieve the value for a key if it is still within its validity period, and the count method will return the number of unexpired keys. The cache is cleaned up automatically on any interaction, ensuring that expired keys don't linger in the system.

Solution Implementation

Time and Space Complexity

Time Complexity:

• set operation:

  • This operation involves checking the presence of a key, setting a new value for the key, and removing expired elements.
  • The check and set operations on the map are O(1) on average (amortized time).
  • The removeExpire operation iterates over the entire cache to remove expired entries, leading to an O(n) complexity where n is the number of entries.
  • Therefore, the overall time complexity for set is O(n).

• get operation:

  • Similar to set, get first calls removeExpire, which is O(n).
  • Retrieving the value for a key from the map is O(1).
  • Thus, the time complexity for get is also O(n).

• count operation:

  • This operation only calls removeExpire before returning the cache size.
  • The time complexity for removeExpire is O(n), so the same holds for the count operation.

• now operation:

  • Simply returns the current time, which is a constant-time operation, O(1).

• removeExpire operation:

  • This operation has to iterate through each element in the cache, checking expiration, and possibly deleting the entry.
  • The worst-case complexity for this operation is O(n).

Space Complexity:

• The space complexity of the TimeLimitedCache class depends on the number of key-value pairs stored in the cache map. Since each key maps to a fixed-size array of two numbers (the value and the expiration time), the space complexity is O(n), where n is the number of unique keys that have been inserted into the cache.