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