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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Cache With Time Limit

Difficulty: Medium

Problem Description

Write a class that allows getting and setting key-value pairs, however a time until expiration is associated with each key. The class has three public methods: set(key, value, duration), get(key), and count().

Key Insights

  • Each key in the cache has an associated expiration time, calculated as the current time plus the duration.
  • The set method should update the value of an existing key if it already exists and return whether the key was previously un-expired.
  • The get method should return the value of a key if it is still valid, or -1 if it has expired.
  • The count method should return the number of keys that have not expired.

Space and Time Complexity

Time Complexity: O(1) for set, get, and count operations.
Space Complexity: O(n) where n is the number of keys stored in the cache.

Solution

To solve the problem, we can utilize a hash map (dictionary) to store the keys along with their values and expiration times. The hash map will allow us to efficiently check if a key exists and to retrieve or update its associated value and expiration time. Specifically, we will store each key as the dictionary key and a tuple containing its value and expiration time as the dictionary value. The approach allows us to quickly determine if a key is expired during retrieval operations.

Code Solutions

class TimeLimitedCache:
    def __init__(self):
        self.cache = {}
        
    def set(self, key: int, value: int, duration: int) -> bool:
        current_time = self._current_time()
        expired = key in self.cache and self.cache[key][1] > current_time
        self.cache[key] = (value, current_time + duration)
        return expired
    
    def get(self, key: int) -> int:
        current_time = self._current_time()
        if key in self.cache and self.cache[key][1] > current_time:
            return self.cache[key][0]
        return -1
    
    def count(self) -> int:
        current_time = self._current_time()
        return sum(1 for exp in self.cache.values() if exp[1] > current_time)
    
    def _current_time(self):
        # Placeholder for the actual current time retrieval
        pass
← Back to All Questions