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.
1import java.util.*;
2
3class TimeLimitedCache {
4 private static class ExpiryEntry implements Comparable<ExpiryEntry> {
5 int key;
6 long expireAt;
7
8 ExpiryEntry(int key, long expireAt) {
9 this.key = key;
10 this.expireAt = expireAt;
11 }
12
13 @Override
14 public int compareTo(ExpiryEntry other) {
15 return Long.compare(this.expireAt, other.expireAt);
16 }
17 }
18
19 private Map<Integer, int[]> cache;
20 private PriorityQueue<ExpiryEntry> expiryQueue;
21
22 public TimeLimitedCache() {
23 cache = new HashMap<>();
24 expiryQueue = new PriorityQueue<>();
25 }
26
27 private void cleanup() {
28 long currentTime = System.currentTimeMillis();
29 while (!expiryQueue.isEmpty() && expiryQueue.peek().expireAt <= currentTime) {
30 ExpiryEntry entry = expiryQueue.poll();
31 if (cache.containsKey(entry.key) && cache.get(entry.key)[1] <= entry.expireAt) {
32 cache.remove(entry.key);
33 }
34 }
35 }
36
37 public boolean set(int key, int value, int duration) {
38 cleanup();
39 long expireAt = System.currentTimeMillis() + duration;
40 boolean exists = cache.containsKey(key) && cache.get(key)[1] > System.currentTimeMillis();
41 cache.put(key, new int[]{value, (int) expireAt});
42 expiryQueue.add(new ExpiryEntry(key, expireAt));
43 return exists;
44 }
45
46 public int get(int key) {
47 cleanup();
48 if (cache.containsKey(key)) {
49 int[] entry = cache.get(key);
50 if (entry[1] > System.currentTimeMillis()) {
51 return entry[0];
52 }
53 }
54 return -1;
55 }
56
57 public int count() {
58 cleanup();
59 return cache.size();
60 }
61}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.