We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Cache With Time Limit

Number: 2762

Difficulty: Medium

Paid? No

Companies: Amazon, ThousandEyes

Problem Description

Design and implement a cache that associates each key with a value and a time-to-live duration (in milliseconds). The cache should support the following operations:

  • set(key, value, duration): Inserts or updates the key with its associated value and time until expiration. Returns true if the key already existed and had not expired (in which case the value and duration are overwritten) and false otherwise.
  • get(key): Retrieves the value for an unexpired key, or returns -1 if the key does not exist or has expired.
  • count(): Returns the number of unexpired keys currently stored in the cache.

Key Insights

  • Utilize a hash map (or dictionary) to store key-value pairs along with their expiration timestamps.
  • Compute the expiration time as (current time in ms + duration). This makes checking for expiration straightforward.
  • For the set method, first check if the key exists and is still unexpired. Then update the key with the new value and expiration time.
  • Lazy deletion: Instead of immediately removing expired keys, check expiration during get and count operations, then remove entries as needed.
  • All operations (set, get, count) can be implemented with O(1) average time complexity using hash maps.

Space and Time Complexity

Time Complexity: O(1) average for set and get operations. The count operation may iterate over all keys in the worst-case scenario, so its complexity is O(n) in that case. Space Complexity: O(n), where n is the number of keys stored in the cache.

Solution

The solution uses a hash map to store each key along with a pair containing its value and the expiration timestamp. For every operation, the current system time (in milliseconds) is compared with the stored expiration time. This allows the implementation to determine whether a key is valid or expired. The set method checks if the key already exists and is unexpired; then it overwrites the value and expiration regardless of this check, returning the appropriate boolean. The get method retrieves the value if the key is unexpired, or returns -1 after cleaning up expired keys. The count method cleans up all expired keys via iteration and then returns the count of valid keys.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with explanatory comments.

import time

class TimeLimitedCache:
    def __init__(self):
        # Dictionary to store key -> (value, expiration_time)
        self.cache = {}
    
    def set(self, key, value, duration):
        # Get current time in milliseconds
        current_time = int(time.time() * 1000)
        # Calculate expiration time as current time plus duration
        expiration = current_time + duration
        existed = False
        
        # Check if the key exists and is unexpired
        if key in self.cache:
            stored_value, stored_expiration = self.cache[key]
            if current_time < stored_expiration:
                existed = True
        
        # Overwrite or add the key with new value and expiration time
        self.cache[key] = (value, expiration)
        return existed

    def get(self, key):
        current_time = int(time.time() * 1000)
        
        # Check if key exists
        if key in self.cache:
            value, expiration = self.cache[key]
            # If expired, remove the key and return -1
            if current_time >= expiration:
                del self.cache[key]
                return -1
            return value
        return -1

    def count(self):
        current_time = int(time.time() * 1000)
        # Remove all expired keys
        keys_to_remove = [k for k, (_, exp) in self.cache.items() if current_time >= exp]
        for k in keys_to_remove:
            del self.cache[k]
        return len(self.cache)
← Back to All Questions