How do you solve Cache With Time Limit on LeetCode?

Cache With Time Limit (LeetCode #2622) can be solved using Brute Force. The optimal approach is Brute Force with undefined time complexity and undefined space complexity. Key insight: In the brute force approach, we can simply store the key-value pairs along with their expiration time. Each time we access the cache, we check if the key is expired by comparing the current time with the stored expiration time.

What is the time complexity of Cache With Time Limit?

The optimal solution for Cache With Time Limit runs in undefined time and uses undefined space. undefined

#2622

Cache With Time Limit

Medium

LeetCode ↗

Approaches

💡

Intuition

Time Space

In the brute force approach, we can simply store the key-value pairs along with their expiration time. Each time we access the cache, we check if the key is expired by comparing the current time with the stored expiration time.

⚙️

Algorithm

4 steps

1Step 1: Create a dictionary to store key-value pairs and their expiration times.
2Step 2: In the set method, calculate the expiration time and store it in the dictionary.
3Step 3: In the get method, check if the key exists and if it is expired. If not expired, return the value; otherwise, return -1.
4Step 4: In the count method, iterate through the dictionary and count un-expired keys.

solution.py23 lines

1class TimeLimitedCache:
2    def __init__(self):
3        self.cache = {}
4
5    def set(self, key, value, duration):
6        expired = self.get_expiration_time(duration)
7        existed = key in self.cache and self.cache[key][1] > 0
8        self.cache[key] = (value, expired)
9        return existed
10
11    def get(self, key):
12        if key in self.cache:
13            value, expired = self.cache[key]
14            if expired > 0:
15                return value
16        return -1
17
18    def count(self):
19        return sum(1 for key in self.cache if self.cache[key][1] > 0)
20
21    def get_expiration_time(self, duration):
22        import time
23        return int(time.time() * 1000) + duration

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.