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): accepts an integer key, an integer value, and a duration in milliseconds. Once the duration has elapsed, the key should be inaccessible. The method should return true if the same un-expired key already exists and false otherwise. Both the value and duration should be overwritten if the key already exists.
get(key): if an un-expired key exists, it should return the associated value. Otherwise it should return -1.
count(): returns the count of un-expired keys.
Example 1:
Input: actions = ["TimeLimitedCache", "set", "get", "count", "get"] values = [[], [1, 42, 100], [1], [], [1]] timeDelays = [0, 0, 50, 50, 150] Output: [null, false, 42, 1, -1] Explanation: At t=0, the cache is constructed. At t=0, a key-value pair (1: 42) is added with a time limit of 100ms. The value doesn't exist so false is returned. At t=50, key=1 is requested and the value of 42 is returned. At t=50, count() is called and there is one active key in the cache. At t=100, key=1 expires. At t=150, get(1) is called but -1 is returned because the cache is empty.
Example 2:
Input: actions = ["TimeLimitedCache", "set", "set", "get", "get", "get", "count"] values = [[], [1, 42, 50], [1, 50, 100], [1], [1], [1], []] timeDelays = [0, 0, 40, 50, 120, 200, 250] Output: [null, false, true, 50, 50, -1, 0] Explanation: At t=0, the cache is constructed. At t=0, a key-value pair (1: 42) is added with a time limit of 50ms. The value doesn't exist so false is returned. At t=40, a key-value pair (1: 50) is added with a time limit of 100ms. A non-expired value already existed so true is returned and the old value was overwritten. At t=50, get(1) is called which returned 50. At t=120, get(1) is called which returned 50. At t=140, key=1 expires. At t=200, get(1) is called but the cache is empty so -1 is returned. At t=250, count() returns 0 because the cache is empty.
Constraints:
0 <= key, value <= 1090 <= duration <= 10001 <= actions.length <= 100actions.length === values.lengthactions.length === timeDelays.length0 <= timeDelays[i] <= 1450actions[i] is one of "TimeLimitedCache", "set", "get" and "count"The key idea in #2622 Cache With Time Limit is to design a cache where each key-value pair automatically expires after a specified duration. A common and efficient strategy is to use a hash map (or Map) to store the value along with its expiration timestamp.
When inserting with set(key, value, duration), compute the expiration time using the current timestamp plus the duration. If the key already exists and has not expired, return true; otherwise return false. The get(key) operation checks whether the stored expiration time is still valid before returning the value. The count() operation tracks how many keys are currently unexpired.
To keep the cache clean, some implementations also schedule removals using setTimeout, ensuring expired entries are automatically deleted. With a hash map and timestamp checks, each operation remains efficient while handling expiration logic cleanly.
Time Complexity: O(1) average per operation. Space Complexity: O(n) for storing active cache entries.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map with Expiration Timestamp | O(1) per set/get/count operation | O(n) for storing active cache entries |
Sahil & Sarra
Use these hints if you're stuck. Try solving on your own first.
You can delay execution of code with "ref = setTimeout(fn, delay)". You can abort the execution with "clearTimeout(ref)"
When storing the values in the cache, also store a reference to the timeout. The timeout should clear the key from the cache after the expiration has elapsed.
When you set a key that already exists, clear the existing timeout.
This approach involves using a HashMap (or dictionary in Python) to store the key-value pairs along with their expiration timestamps. The expiration timestamp is calculated at the time of insertion by adding the current time with the duration. Each time a get or count operation is performed, expired keys are ignored.
Time Complexity: O(1) on average for set, get, and count operations.
Space Complexity: O(n) where n is the capacity of the cache.
1from time import time
2
3class TimeLimitedCache:
4 def __init__(self):
5 self.cache = {}
6
7
This Python solution uses a dictionary to map keys to tuples containing the value and expiration timestamp. The set method updates the cache with the new expiration time, returning whether the key was previously valid. The get method checks current time against expiration. The count method uses a generator expression to count unexpired keys.
This approach combines a HashMap to store the values and their expiration time, with a PriorityQueue (or equivalent) to keep track of the order in which keys expire. Whenever a key is accessed or updated, expired keys at the front of the queue are removed to keep the cache up-to-date. This enables efficient removal of expired elements.
Time Complexity: O(log n) for cleanup and set due to the priority queue, but O(1) on average for get.
Space Complexity: O(n) where n is the size of the cache.
1import java.util.*;
2
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Yes, variations of time-based cache design appear in technical interviews, especially for roles requiring knowledge of system design and data structures. Interviewers often use such problems to evaluate understanding of hashing, time-based logic, and efficient state management.
Expiration can be handled by storing a timestamp indicating when the key should expire and checking it during access. Some implementations also use timers like setTimeout to automatically remove keys once the duration has passed.
A hash map (or Map in JavaScript) is the best data structure because it allows O(1) key lookups. Each entry stores both the value and its expiration time, enabling quick validation of whether the item is still active.
The optimal approach uses a hash map to store each key along with its value and expiration timestamp. Every operation checks whether the stored expiration time is still valid. This allows set, get, and count operations to run in constant time on average.
This Java solution employs a HashMap for quick access and a PriorityQueue for managing expiration. The queue allows quick determination of expired entries, and periodic cleanup ensures that the map holds only valid items.