Problem Description

This problem asks you to implement a cache data structure with time-based expiration for stored key-value pairs. The cache should store integer keys and values, where each entry automatically expires after a specified duration.

The TimeLimitedCache class needs to implement three methods:

1. set(key, value, duration): Stores or updates a key-value pair with an expiration time. The duration parameter specifies how long (in milliseconds) the entry should remain valid. The method returns true if the key already existed and was not expired before this operation, and false otherwise. If the key already exists, both its value and expiration time should be updated.

2. get(key): Retrieves the value associated with a given key. If the key exists and hasn't expired, it returns the stored value. If the key doesn't exist or has expired, it returns -1.

3. count(): Returns the total number of keys currently in the cache that haven't expired yet.

The key challenge is managing the expiration logic - entries should become inaccessible once their duration has elapsed, even if they're still stored in the underlying data structure. The implementation uses a hash table (Map) to store each key with its value and expiration timestamp. When accessing entries, the code checks if the current time has passed the expiration time to determine if the entry is still valid.

For example, if you call set(1, 42, 1000), the key 1 with value 42 will be accessible for 1000 milliseconds. After that time passes, calling get(1) would return -1, and the key wouldn't be counted in count().

Intuition

When dealing with time-based expiration, we need a way to track both the data and when it becomes invalid. The natural approach is to store the expiration timestamp alongside each value. Instead of actively removing expired entries (which would require a background process or timer), we can use a "lazy evaluation" strategy - checking if an entry is expired only when we try to access it.

The core insight is that we can calculate the expiration time when setting a value by adding the duration to the current timestamp: expiration = Date.now() + duration. This gives us an absolute point in time when the entry expires, making it easy to check validity later by comparing against the current time.

For the data structure, a hash table (Map) is the obvious choice since we need O(1) access to keys. We store each entry as a tuple [value, expirationTime], keeping both pieces of information together.

The tricky part is handling the set method's return value. We need to know if a key existed and was valid before updating it. This requires checking expiration status before overwriting the entry. Even if a key exists in the map, it might be expired, so we treat expired keys as if they don't exist.

For counting valid keys, we must iterate through all entries and filter out expired ones. While this is O(n), there's no way around checking each entry's expiration status without maintaining additional data structures or using active cleanup, which would complicate the implementation.

The solution elegantly handles expiration checking through a helper method #isExpired that encapsulates the logic of verifying both key existence and comparing timestamps, making the main methods cleaner and avoiding code duplication.

Solution Approach

The solution uses a hash table (Map) to store key-value pairs along with their expiration timestamps. Here's how each component works:

Data Structure:

• A private Map #cache stores entries as Map<number, [value: number, expire: number]>
• Each entry contains a tuple with the value and its expiration timestamp

Helper Method - #isExpired:

#isExpired = (key: number) =>
    this.#cache.has(key) &&
    (this.#cache.get(key)?.[1] ?? Number.NEGATIVE_INFINITY) < Date.now();

This method checks if a key exists and if its expiration time has passed. It returns true only if the key exists in the map AND the current time exceeds the stored expiration time.

set Method Implementation:

1. First, check if the key exists and is not expired to determine the return value
2. Store the new entry with expiration time calculated as Date.now() + duration
3. Return true if the key previously existed (regardless of update), false otherwise

set(key: number, value: number, duration: number): boolean {
    const isExist = this.#cache.has(key) && !this.#isExpired(key);
    this.#cache.set(key, [value, Date.now() + duration]);
    return isExist;
}

get Method Implementation:

1. Check if the key is expired using the helper method
2. If expired, return -1
3. Otherwise, retrieve the value from the tuple stored in the map

get(key: number): number {
    if (this.#isExpired(key)) return -1;
    const res = this.#cache.get(key)?.[0] ?? -1;
    return res;
}

count Method Implementation:

1. Convert the Map to an array of entries
2. Filter out expired keys by checking each one
3. Return the length of the filtered array

count(): number {
    const xs = Array.from(this.#cache).filter(([key]) => !this.#isExpired(key));
    return xs.length;
}

The approach leverages TypeScript's private fields (denoted by #) for encapsulation and uses optional chaining (?.) and nullish coalescing (??) operators for safe property access. The solution avoids active cleanup of expired entries, instead checking expiration status on-demand, which simplifies the implementation while maintaining correct behavior.

Example Walkthrough

Let's walk through a simple example to illustrate how the TimeLimitedCache works:

const cache = new TimeLimitedCache();

// Time T=0ms: Set key 1 with value 10, expires in 50ms
cache.set(1, 10, 50);  // returns false (key didn't exist before)
// Cache state: {1: [10, T+50ms]}

// Time T=20ms: Set key 2 with value 20, expires in 30ms (at T+50ms)
cache.set(2, 20, 30);  // returns false
// Cache state: {1: [10, T+50ms], 2: [20, T+50ms]}

// Time T=25ms: Get key 1
cache.get(1);  // returns 10 (not expired yet, T+25 < T+50)

// Time T=30ms: Count active keys
cache.count();  // returns 2 (both keys still valid)

// Time T=40ms: Update key 1 with new value 15, expires in 40ms (at T+80ms)
cache.set(1, 15, 40);  // returns true (key 1 existed and wasn't expired)
// Cache state: {1: [15, T+80ms], 2: [20, T+50ms]}

// Time T=55ms: Try to get key 2
cache.get(2);  // returns -1 (expired at T+50ms)

// Time T=60ms: Count active keys
cache.count();  // returns 1 (only key 1 is still valid)

// Time T=85ms: Try to get key 1
cache.get(1);  // returns -1 (expired at T+80ms)

Step-by-step breakdown:

1. Initial set: When we first add key 1, the cache stores [10, currentTime + 50]. Since the key didn't exist, it returns false.

2. Checking expiration: When we call get(1) at T=25ms, the #isExpired helper checks if T+50 < T+25, which is false, so the key is still valid and returns 10.

3. Updating existing key: At T=40ms, when we call set(1, 15, 40), the method first checks if key 1 exists and isn't expired (true), then updates both the value and expiration time to [15, T+80], returning true.

4. Expired access: At T=55ms, key 2 has expired (T+50 < T+55), so get(2) returns -1 even though the entry still exists in the Map.

5. Counting valid keys: The count() method iterates through all entries and filters out expired ones using the #isExpired helper, returning only the count of valid keys.

Solution Implementation

Time and Space Complexity

Time Complexity:

• set(key, value, duration): O(1) - The method performs hash map operations (has, get, set) which are constant time operations on average.
• get(key): O(1) - The method performs hash map operations (has, get) which are constant time operations on average.
• count(): O(n) - The method iterates through all entries in the cache using Array.from() and filter(), where n is the number of entries in the cache.

Space Complexity:

• Overall space: O(n) - The cache stores up to n key-value pairs along with their expiration times.
• set(): O(1) - Only stores or updates a single entry.
• get(): O(1) - No additional space is used beyond temporary variables.
• count(): O(n) - Creates a new array from the cache entries during the filtering operation.

Note: The implementation has a bug in the set method. The condition !this.#isExpired(key) should likely be reversed or removed entirely, as it prevents setting values when the key doesn't exist or is expired. The current logic only sets a value if the key exists and is NOT expired, which contradicts the expected behavior of always setting the value regardless of expiration status.

Common Pitfalls

1. Time Unit Mismatch Between time.time() and Duration Parameter

The most critical pitfall in this implementation is the inconsistent handling of time units. Python's time.time() returns the current time in seconds since the epoch, but the problem specification requires the duration parameter to be in milliseconds.

The Bug:

def set(key, value, duration):
    import time
    # time.time() returns seconds, but duration is in milliseconds
    expiration_time = time.time() * 1000 + duration  # Mixing units incorrectly

While the code multiplies time.time() by 1000 to convert to milliseconds, this creates precision issues due to floating-point arithmetic and makes the code error-prone.

The Solution: Use time.time_ns() for nanosecond precision or consistently work with milliseconds:

import time

def get_current_time_ms():
    """Returns current time in milliseconds with proper precision"""
    return int(time.time() * 1000)

def set(key, value, duration):
    exists_and_not_expired = key in cache and not is_expired(key)
    expiration_time = get_current_time_ms() + duration
    cache[key] = (value, expiration_time)
    return exists_and_not_expired

def is_expired(key):
    if key not in cache:
        return False
    expiration_time = cache[key][1]
    return expiration_time < get_current_time_ms()

2. Global State Management

Using a global cache dictionary can cause issues in concurrent environments or when multiple cache instances are needed.

The Problem:

cache = {}  # Global variable - shared across all usages

The Solution: Encapsulate the cache in a class:

class TimeLimitedCache:
    def __init__(self):
        self.cache = {}
  
    def set(self, key, value, duration):
        exists_and_not_expired = key in self.cache and not self._is_expired(key)
        expiration_time = self._get_current_time_ms() + duration
        self.cache[key] = (value, expiration_time)
        return exists_and_not_expired
  
    def get(self, key):
        if key not in self.cache or self._is_expired(key):
            return -1
        return self.cache[key][0]
  
    def count(self):
        return sum(1 for key in self.cache if not self._is_expired(key))
  
    def _is_expired(self, key):
        if key not in self.cache:
            return False
        return self.cache[key][1] < self._get_current_time_ms()
  
    def _get_current_time_ms(self):
        import time
        return int(time.time() * 1000)

3. Memory Leak from Never Cleaning Expired Entries

The current implementation never removes expired entries from the dictionary, leading to unbounded memory growth.

The Solution: Add periodic cleanup or clean on access:

def get(key):
    if key not in cache:
        return -1
  
    if is_expired(key):
        # Clean up expired entry when detected
        del cache[key]
        return -1
  
    return cache[key][0]

def count():
    # Clean up expired entries during count
    expired_keys = [key for key in cache if is_expired(key)]
    for key in expired_keys:
        del cache[key]
  
    return len(cache)