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.
1#include <unordered_map>
2#include <chrono>
3
4using namespace std;
5using namespace std::chrono;
6
7class TimeLimitedCache {
8private:
9 unordered_map<int, pair<int, long long>> cache;
10
11 long long currentTimeMillis() {
12 return duration_cast<milliseconds>(steady_clock::now().time_since_epoch()).count();
13 }
14
public:
bool set(int key, int value, int duration) {
long long expiration = currentTimeMillis() + duration;
bool exists = cache.find(key) != cache.end() && cache[key].second > currentTimeMillis();
cache[key] = {value, expiration};
return exists;
}
int get(int key) {
if (cache.find(key) != cache.end() && cache[key].second > currentTimeMillis()) {
return cache[key].first;
}
return -1;
}
int count() {
long long current_time = currentTimeMillis();
int count = 0;
for (const auto& entry : cache) {
if (entry.second.second > current_time) {
count++;
}
}
return count;
}
};This C++ solution uses an unordered_map to store key-value pairs where each value is a pair consisting of the actual value and its expiration time. The set function inserts or updates the expiration time of a key-value pair, returning true if an unexpired key existed; get checks the current time before returning values; count iterates over the map 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.
1#include <unordered_map>
2#include <queue>
3#include <utility>
4#include <chrono>
using namespace std;
using namespace std::chrono;
struct ExpiryEntry {
int key;
long long expireAt;
bool operator>(const ExpiryEntry& other) const {
return expireAt > other.expireAt;
}
};
class TimeLimitedCache {
private:
unordered_map<int, pair<int, long long>> cache;
priority_queue<ExpiryEntry, vector<ExpiryEntry>, greater<>> expiryQueue;
long long currentTimeMillis() {
return duration_cast<milliseconds>(steady_clock::now().time_since_epoch()).count();
}
void cleanup() {
while (!expiryQueue.empty() && expiryQueue.top().expireAt < currentTimeMillis()) {
int key = expiryQueue.top().key;
if (cache[key].second <= expiryQueue.top().expireAt) {
cache.erase(key);
}
expiryQueue.pop();
}
}
public:
bool set(int key, int value, int duration) {
cleanup();
long long current_time = currentTimeMillis();
long long expireAt = current_time + duration;
bool exists = cache.find(key) != cache.end() && cache[key].second > current_time;
cache[key] = {value, expireAt};
expiryQueue.push({key, expireAt});
return exists;
}
int get(int key) {
cleanup();
if (cache.find(key) != cache.end() && cache[key].second > currentTimeMillis()) {
return cache[key].first;
}
return -1;
}
int count() {
cleanup();
return cache.size();
}
};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 C++ approach uses an unordered_map for storage and a priority_queue for expiration handling. Before any operation, expired items are removed using the priority queue to ensure correctness. This allows lazy expiration checking without iterating over the entire map for each check.