Sponsored
Sponsored
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.
#include <chrono>
using namespace std;
using namespace std::chrono;
class TimeLimitedCache {
private:
unordered_map<int, pair<int, long long>> cache;
long long currentTimeMillis() {
return duration_cast<milliseconds>(steady_clock::now().time_since_epoch()).count();
}
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>
5
6using namespace std;
7using namespace std::chrono;
8
9struct ExpiryEntry {
10 int key;
11 long long expireAt;
12 bool operator>(const ExpiryEntry& other) const {
13 return expireAt > other.expireAt;
14 }
15};
16
17class TimeLimitedCache {
18private:
19 unordered_map<int, pair<int, long long>> cache;
20 priority_queue<ExpiryEntry, vector<ExpiryEntry>, greater<>> expiryQueue;
21
22 long long currentTimeMillis() {
23 return duration_cast<milliseconds>(steady_clock::now().time_since_epoch()).count();
24 }
25
26 void cleanup() {
27 while (!expiryQueue.empty() && expiryQueue.top().expireAt < currentTimeMillis()) {
28 int key = expiryQueue.top().key;
29 if (cache[key].second <= expiryQueue.top().expireAt) {
30 cache.erase(key);
31 }
32 expiryQueue.pop();
33 }
34 }
35
36public:
37 bool set(int key, int value, int duration) {
38 cleanup();
39 long long current_time = currentTimeMillis();
40 long long expireAt = current_time + duration;
41 bool exists = cache.find(key) != cache.end() && cache[key].second > current_time;
42 cache[key] = {value, expireAt};
43 expiryQueue.push({key, expireAt});
44 return exists;
45 }
46
47 int get(int key) {
48 cleanup();
49 if (cache.find(key) != cache.end() && cache[key].second > currentTimeMillis()) {
50 return cache[key].first;
51 }
52 return -1;
53 }
54
55 int count() {
56 cleanup();
57 return cache.size();
58 }
59};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.