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.
The implementation uses an array of KeyValue structures, each holding a value and an expiration time, to simulate a hashmap. The expiration time is computed as the current time plus duration. The set operation checks if the key already exists by comparing expiration times. The get operation returns the value if the key is valid; otherwise, it returns -1. The count operation counts valid keys only.
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.