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.

💪
Level Up Your
Algo Skills

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.

Python Solution

1import time
2from typing import Dict, Tuple
3
4# Define a type alias for the tuple used to store cache values and their expiration timestamps.
5CacheValue = Tuple[int, float]
6
7# This dictionary will act as the cache storage.
8cache: Dict[int, CacheValue] = {}
9
10# A function to obtain the current time in seconds.
11def now() -> float:
12    return time.time()
13
14# A function to remove expired keys and their associated values from the cache.
15def remove_expired_keys() -> None:
16    # Get the current time for comparison.
17    current_time = now()
18    # List of keys to delete after iteration to avoid runtime error.
19    keys_to_delete = []
20    # Iterate over the items in the cache dictionary.
21    for key, (_, expire) in cache.items():
22        # If the expiration time is less or equal than the current time, mark for deletion.
23        if expire <= current_time:
24            keys_to_delete.append(key)
25    # Delete the marked keys.
26    for key in keys_to_delete:
27        del cache[key]
28
29# A function to set a value in the cache with a specific duration before it expires.
30# Returns True if the key was already present in the cache; otherwise, False.
31def set_value(key: int, value: int, duration: float) -> bool:
32    # Remove expired cache entries first.
33    remove_expired_keys()
34    # Check if the key is already present in the cache.
35    was_present = key in cache
36    # Set the key with its value and expiration time.
37    cache[key] = (value, now() + duration)
38    # Return whether the key was present.
39    return was_present
40
41# A function to get a value from the cache by its key.
42# Returns the value if the key is in the cache and hasn't expired; otherwise, returns -1.
43def get_value(key: int) -> int:
44    # Remove expired cache entries first.
45    remove_expired_keys()
46    # Return the value if the key exists and is not expired, otherwise return -1.
47    return cache[key][0] if key in cache else -1
48
49# A function to count the number of non-expired entries currently in the cache.
50def count_cache_entries() -> int:
51    # Cleanup expired cache entries first.
52    remove_expired_keys()
53    # Return the size of the cache dictionary, representing non-expired entries.
54    return len(cache)
55
56# Usage Example:
57# Note: This is a simple usage example.
58
59# Set a key-value pair in the cache with an expiry duration (should return False initially).
60set_value(1, 42, 5)  # Example: Store the value '42' with the key '1' for '5' seconds.
61# Get the value for a given key (should return 42 if not expired).
62get_value(1)
63# Count the number of non-expired cache entries (initially expected to be 1).
64count_cache_entries()
65

Java Solution

1import java.util.Iterator;
2import java.util.Map;
3import java.util.concurrent.ConcurrentHashMap;
4
5// Class CacheValue to store the cache value along with its expiration timestamp
6class CacheValue {
7    int value;
8    long expire;
9
10    CacheValue(int value, long expire) {
11        this.value = value;
12        this.expire = expire;
13    }
14}
15
16public class Cache {
17    // ConcurrentHashMap to act as the cache storage
18    private Map<Integer, CacheValue> cache = new ConcurrentHashMap<>();
19
20    // Method to obtain the current time in milliseconds
21    private long now() {
22        return System.currentTimeMillis();
23    }
24
25    // Method to remove the expired keys and their associated values from the cache
26    private void removeExpiredKeys() {
27        long currentTime = now();
28        Iterator<Map.Entry<Integer, CacheValue>> iterator = cache.entrySet().iterator();
29      
30        while (iterator.hasNext()) {
31            Map.Entry<Integer, CacheValue> entry = iterator.next();
32            if (entry.getValue().expire <= currentTime) {
33                iterator.remove();
34            }
35        }
36    }
37
38    // Method to set a value in the cache with a certain duration before it expires
39    // Returns true if the key was already present in the cache; otherwise, returns false
40    public boolean setValue(int key, int value, int duration) {
41        removeExpiredKeys();
42        boolean wasPresent = cache.containsKey(key);
43        cache.put(key, new CacheValue(value, now() + duration));
44        return wasPresent;
45    }
46
47    // Method to get a value from the cache by its key
48    // Returns the value if the key is in the cache and hasn't expired; otherwise, returns -1
49    public int getValue(int key) {
50        removeExpiredKeys();
51        CacheValue cacheValue = cache.get(key);
52        if (cacheValue != null) {
53            return cacheValue.value;
54        }
55        return -1;
56    }
57
58    // Method to count the number of non-expired entries currently in the cache
59    public int countCacheEntries() {
60        removeExpiredKeys();
61        return cache.size();
62    }
63
64    // Usage example (not for production use)
65    public static void main(String[] args) {
66        Cache myCache = new Cache();
67
68        boolean isPresent = myCache.setValue(1, 42, 1000); // Sets the key with a value and expiry duration, expected to return false initially
69        System.out.println(isPresent); // Expected to print `false`
70
71        int value = myCache.getValue(1); // Should return 42 if not expired
72        System.out.println(value); // Expected to print `42`
73
74        int count = myCache.countCacheEntries(); // Should return the count of non-expired cache entries, expected to be 1 initially
75        System.out.println(count); // Expected to print `1`
76    }
77}
78

C++ Solution

1#include <iostream>
2#include <map>
3#include <chrono>
4
5// We are defining a type alias for the pair that will be used to store the cache values along with their expiration timestamps
6using CacheValue = std::pair<int, long long>;
7
8// This map will act as the cache storage
9std::map<int, CacheValue> cache;
10
11// A function to obtain the current time in milliseconds
12long long now() {
13    return std::chrono::duration_cast<std::chrono::milliseconds>(
14        std::chrono::system_clock::now().time_since_epoch()
15    ).count();
16}
17
18// A function to remove the expired keys and their associated values from the cache
19void removeExpiredKeys() {
20    auto currentTime = now();
21    for (auto it = cache.begin(); it != cache.end(); ) {
22        if (it->second.second <= currentTime) {
23            it = cache.erase(it); // Erase and advance the iterator in one step
24        } else {
25            ++it; // Only advance the iterator
26        }
27    }
28}
29
30// A function to set a value in the cache with a certain duration before it expires.
31// Returns true if the key was already present in the cache; otherwise, returns false.
32bool setValue(int key, int value, int duration) {
33    removeExpiredKeys();
34    bool wasPresent = cache.find(key) != cache.end();
35    cache[key] = {value, now() + duration};
36    return wasPresent;
37}
38
39// A function to get a value from the cache by its key.
40// Returns the value if the key is in the cache and hasn't expired; otherwise, returns -1.
41int getValue(int key) {
42    removeExpiredKeys();
43    auto it = cache.find(key);
44    if (it != cache.end()) {
45        return it->second.first;
46    }
47    return -1;
48}
49
50// A function to count the number of non-expired entries currently in the cache.
51int countCacheEntries() {
52    removeExpiredKeys();
53    return cache.size();
54}
55
56// Usage example (main function)
57int main() {
58    // Sets the key with a value and an expiry duration, expected to return false initially
59    std::cout << std::boolalpha << setValue(1, 42, 1000) << std::endl;
60
61    // Should return 42 if not expired
62    std::cout << getValue(1) << std::endl;
63
64    // Should return the count of non-expired cache entries, expected to be 1 initially
65    std::cout << countCacheEntries() << std::endl;
66
67    return 0;
68}
69

Typescript Solution

1// We are defining a type alias for the tuple that will be used to store the cache values along with their expiration timestamps
2type CacheValue = [value: number, expire: number];
3
4// This map will act as the cache storage
5const cache: Map<number, CacheValue> = new Map();
6
7// A function to obtain the current time in milliseconds
8function now(): number {
9    return new Date().getTime();
10}
11
12// A function to remove the expired keys and their associated values from the cache
13function removeExpiredKeys(): void {
14    const currentTime = now();
15    for (const [key, [, expire]] of cache) {
16        if (expire <= currentTime) {
17            cache.delete(key);
18        }
19    }
20}
21
22// A function to set a value in the cache with a certain duration before it expires.
23// Returns true if the key was already present in the cache; otherwise, false.
24function setValue(key: number, value: number, duration: number): boolean {
25    removeExpiredKeys();
26    const wasPresent = cache.has(key);
27    cache.set(key, [value, now() + duration]);
28    return wasPresent;
29}
30
31// A function to get a value from the cache by its key.
32// Returns the value if the key is in the cache and hasn't expired; otherwise, returns -1.
33function getValue(key: number): number {
34    removeExpiredKeys();
35    return cache.get(key)?.[0] ?? -1;
36}
37
38// A function to count the number of non-expired entries currently in the cache.
39function countCacheEntries(): number {
40    removeExpiredKeys();
41    return cache.size;
42}
43
44// Usage
45// An example of usage is provided below.
46// Please remove this when implementing this logic in production as global state and functions
47// may collide with other parts of the system, and direct usage like this might not be recommended.
48
49setValue(1, 42, 1000); // Sets the key with a value and an expiry duration, expected to return false initially
50getValue(1); // Should return 42 if not expired
51countCacheEntries(); // Should return the count of non-expired cache entries, expected to be 1 initially
52

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.
😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫