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.
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.