Cache With Time Limit
Cache With Time Limit is a medium design data structures problem solved with the hash map + heap pattern.
The best approach, optimal (hash map + min-heap of expiries), runs in O(log n) amortized per call time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan on count) up.
Problem
Design a key-value cache where every entry has its own lifetime. The class TimeLimitedCache supports three operations, and each call carries the current clock value time (the clock never goes backwards between calls):
set(time, key, value, duration)storesvalueunder the integerkeyand makes it valid fordurationtime units, so it expires attime + duration. Returntrueifkeyalready held a live (not yet expired) entry, in which case both its value and its timer are replaced; otherwise returnfalse.get(time, key)returns the value ofkeyif it is still live, or-1if it was never set or has expired.count(time)returns how many keys are live right now.
An entry that expires at e is live at every time t < e and gone from t = e onward.
Examples
Example 1
- Input
TimeLimitedCache(), set(0, 7, 40, 100), get(50, 7), count(60), get(100, 7), count(100)- Output
false, 40, 1, -1, 0- Why
- Key 7 is stored at time 0 for 100 units, so it lives while the clock is below 100. At time 100 it has expired.
Example 2
- Input
TimeLimitedCache(), set(5, 1, 10, 50), set(20, 1, 99, 10), get(25, 1), get(30, 1), set(31, 2, 3, 5), count(33)- Output
false, true, 99, -1, false, 1- Why
- The second set finds key 1 still alive, so it returns true and replaces both the value and the timer: the key now expires at 30, not at 55.
Example 3
- Input
TimeLimitedCache(), set(1, 4, 8, 3), set(2, 5, 9, 10), count(3), count(4), get(4, 4), set(4, 4, 6, 2), count(5)- Output
false, false, 2, 1, -1, false, 2- Why
- Key 4 expires at time 4, so setting it again at time 4 counts as a fresh insert and returns false.
Constraints
0 <= time <= 10^9, and thetimearguments never decrease from one call to the next.0 <= key, value <= 10^91 <= duration <= 10^6- At most
3 * 10^4calls in total.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (scan on count) | O(1) for get/set, O(k) for count | O(k) |
| Optimal (hash map + min-heap of expiries) | O(log n) amortized per call | O(n) |
1Brute force (scan on count)
O(1) for get/set, O(k) for countEvery `count` visits all k keys ever stored, including long-dead ones.O(k)Expired entries are never removed, so the map holds every key seen.Keep a hash map from key to {value, expiresAt}. get and set check a single entry; count walks the whole map and counts the entries whose expiry is still in the future.
- set(t, key, value, d): look up key; remember whether it exists with expiresAt > t; store {value, t + d}; return that flag.
- get(t, key): if the entry exists and t < expiresAt return its value, else -1.
- count(t): loop over all entries and count those with t < expiresAt.
class TimeLimitedCache {
private final Map<Integer, int[]> map = new HashMap<>(); // key -> {value, expiresAt}
public TimeLimitedCache() {}
public boolean set(int time, int key, int value, int duration) {
int[] e = map.get(key);
boolean alive = e != null && time < e[1];
map.put(key, new int[] { value, time + duration });
return alive;
}
public int get(int time, int key) {
int[] e = map.get(key);
return (e != null && time < e[1]) ? e[0] : -1;
}
public int count(int time) {
int c = 0;
for (int[] e : map.values()) {
if (time < e[1]) c++;
}
return c;
}
}class TimeLimitedCache:
def __init__(self):
self.map = {} # key -> [value, expires_at]
def set(self, time: int, key: int, value: int, duration: int) -> bool:
e = self.map.get(key)
alive = e is not None and time < e[1]
self.map[key] = [value, time + duration]
return alive
def get(self, time: int, key: int) -> int:
e = self.map.get(key)
return e[0] if e is not None and time < e[1] else -1
def count(self, time: int) -> int:
c = 0
for _, exp in self.map.values():
if time < exp:
c += 1
return cclass TimeLimitedCache {
unordered_map<int, pair<int, int>> mp; // key -> {value, expiresAt}
public:
TimeLimitedCache() {}
bool set(int time, int key, int value, int duration) {
auto it = mp.find(key);
bool alive = it != mp.end() && time < it->second.second;
mp[key] = {value, time + duration};
return alive;
}
int get(int time, int key) {
auto it = mp.find(key);
return (it != mp.end() && time < it->second.second) ? it->second.first : -1;
}
int count(int time) {
int c = 0;
for (auto& [k, e] : mp) {
if (time < e.second) c++;
}
return c;
}
};class TimeLimitedCache {
constructor() {
this.map = new Map(); // key -> [value, expiresAt]
}
set(time, key, value, duration) {
const e = this.map.get(key);
const alive = e !== undefined && time < e[1];
this.map.set(key, [value, time + duration]);
return alive;
}
get(time, key) {
const e = this.map.get(key);
return e !== undefined && time < e[1] ? e[0] : -1;
}
count(time) {
let c = 0;
for (const [, exp] of this.map.values()) {
if (time < exp) c++;
}
return c;
}
}2Optimal (hash map + min-heap of expiries)
O(log n) amortized per callEach `set` pushes one heap entry, and every entry is popped at most once over the whole run.O(n)The heap holds at most one entry per `set` call; the map holds only live keys.Because the clock never goes backwards, an entry that has expired stays expired. Push {expiresAt, key} into a min-heap on every set. Before any operation, pop heap entries whose expiry is <= time and delete the key from the map, but only if the map still holds that same expiry (otherwise the heap entry is stale: the key was overwritten later). After this cleanup the map contains exactly the live keys, so count is just its size.
- purge(t): while the heap top has expiresAt <= t, pop it; if map[key].expiresAt equals that value, remove key from the map.
- set(t, key, value, d): purge(t); alive = key in map; store {value, t + d}; push {t + d, key}; return alive.
- get(t, key): purge(t); return map[key].value if present, else -1.
- count(t): purge(t); return map size.
class TimeLimitedCache {
private final Map<Integer, int[]> map = new HashMap<>(); // key -> {value, expiresAt}
private final PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); // {expiresAt, key}
public TimeLimitedCache() {}
private void purge(int time) {
while (!heap.isEmpty() && heap.peek()[0] <= time) {
int[] top = heap.poll();
int[] e = map.get(top[1]);
if (e != null && e[1] == top[0]) map.remove(top[1]);
}
}
public boolean set(int time, int key, int value, int duration) {
purge(time);
boolean alive = map.containsKey(key);
int exp = time + duration;
map.put(key, new int[] { value, exp });
heap.offer(new int[] { exp, key });
return alive;
}
public int get(int time, int key) {
purge(time);
int[] e = map.get(key);
return e == null ? -1 : e[0];
}
public int count(int time) {
purge(time);
return map.size();
}
}class TimeLimitedCache:
def __init__(self):
self.map = {} # key -> [value, expires_at]
self.heap = [] # (expires_at, key)
def _purge(self, time: int) -> None:
while self.heap and self.heap[0][0] <= time:
exp, key = heapq.heappop(self.heap)
e = self.map.get(key)
if e is not None and e[1] == exp:
del self.map[key]
def set(self, time: int, key: int, value: int, duration: int) -> bool:
self._purge(time)
alive = key in self.map
exp = time + duration
self.map[key] = [value, exp]
heapq.heappush(self.heap, (exp, key))
return alive
def get(self, time: int, key: int) -> int:
self._purge(time)
e = self.map.get(key)
return -1 if e is None else e[0]
def count(self, time: int) -> int:
self._purge(time)
return len(self.map)class TimeLimitedCache {
unordered_map<int, pair<int, int>> mp; // key -> {value, expiresAt}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap; // {expiresAt, key}
void purge(int time) {
while (!heap.empty() && heap.top().first <= time) {
auto [exp, key] = heap.top();
heap.pop();
auto it = mp.find(key);
if (it != mp.end() && it->second.second == exp) mp.erase(it);
}
}
public:
TimeLimitedCache() {}
bool set(int time, int key, int value, int duration) {
purge(time);
bool alive = mp.count(key) > 0;
int exp = time + duration;
mp[key] = {value, exp};
heap.push({exp, key});
return alive;
}
int get(int time, int key) {
purge(time);
auto it = mp.find(key);
return it == mp.end() ? -1 : it->second.first;
}
int count(int time) {
purge(time);
return (int)mp.size();
}
};class MinHeap {
constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }
size() { return this.a.length; }
isEmpty() { return this.a.length === 0; }
peek() { return this.a[0]; }
push(x) {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.cmp(a[i], a[p]) >= 0) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length > 0) {
a[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
class TimeLimitedCache {
constructor() {
this.map = new Map(); // key -> [value, expiresAt]
this.heap = new MinHeap((a, b) => a[0] - b[0]); // [expiresAt, key]
}
purge(time) {
while (!this.heap.isEmpty() && this.heap.peek()[0] <= time) {
const [exp, key] = this.heap.pop();
const e = this.map.get(key);
if (e !== undefined && e[1] === exp) this.map.delete(key);
}
}
set(time, key, value, duration) {
this.purge(time);
const alive = this.map.has(key);
const exp = time + duration;
this.map.set(key, [value, exp]);
this.heap.push([exp, key]);
return alive;
}
get(time, key) {
this.purge(time);
const e = this.map.get(key);
return e === undefined ? -1 : e[0];
}
count(time) {
this.purge(time);
return this.map.size;
}
}Edge cases to test
- Calling
getexactly at the expiry time: the key is already gone - Overwriting a live key resets its timer to the new duration, which may be shorter than before
- Setting a key again right after it expired returns false
counton an empty cache returns 0
Hints
Hint 1
Store, for each key, its value together with the absolute time it stops being valid: time + duration.
Hint 2
A key is alive at time t exactly when t < expiresAt. get and set only need that one check.
Hint 3
For a fast count, keep the expiry times in a min-heap and throw away expired entries from the top before answering. Watch out for heap entries that belong to an older version of a key.
FAQ
What is the best time complexity for Cache With Time Limit?
Optimal (hash map + min-heap of expiries) runs in O(log n) amortized per call time and O(n) extra space. Each `set` pushes one heap entry, and every entry is popped at most once over the whole run.
Which pattern does Cache With Time Limit use?
It is a design data structures problem that uses the hash map + heap pattern.
Is there a brute force solution for Cache With Time Limit?
Yes. Brute force (scan on count) takes O(1) for get/set, O(k) for count time and O(k) space. Keep a hash map from key to {value, expiresAt}.
Which edge cases should I test for Cache With Time Limit?
Calling get exactly at the expiry time: the key is already gone; Overwriting a live key resets its timer to the new duration, which may be shorter than before; Setting a key again right after it expired returns false; count on an empty cache returns 0.