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.
using System.Collections.Generic;
class TimeLimitedCache {
private class CacheEntry {
public int Value { get; set; }
public DateTime ExpireAt { get; set; }
}
private Dictionary<int, CacheEntry> cache;
public TimeLimitedCache() {
cache = new Dictionary<int, CacheEntry>();
}
public bool Set(int key, int value, int duration) {
DateTime expirationTime = DateTime.Now.AddMilliseconds(duration);
bool exists = cache.ContainsKey(key) && cache[key].ExpireAt > DateTime.Now;
cache[key] = new CacheEntry { Value = value, ExpireAt = expirationTime };
return exists;
}
public int Get(int key) {
if (cache.ContainsKey(key) && cache[key].ExpireAt > DateTime.Now) {
return cache[key].Value;
}
return -1;
}
public int Count() {
DateTime currentTime = DateTime.Now;
int count = 0;
foreach (var entry in cache.Values) {
if (entry.ExpireAt > currentTime) {
count++;
}
}
return count;
}
}This C# solution uses a dictionary with a nested class CacheEntry, which contains the value and expiration time for each key. The Set method updates or inserts a new entry, returning whether the key was still valid; Get retrieves values if they are unexpired, and Count walks through the entries to determine unexpired ones.
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.