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 JavaScript solution leverages a Map to handle the cache storage. Each entry contains a value and expiration timestamp. The set method places an entry in the map updating its expiration, returning if it was unexpired before; get verifies expiration before pulling the value; count iterates through the map counting only active entries.
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.