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.
This Python solution uses a dictionary to map keys to tuples containing the value and expiration timestamp. The set method updates the cache with the new expiration time, returning whether the key was previously valid. The get method checks current time against expiration. The count method uses a generator expression 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.