Cache With Time Limit
Build a TimeLimitedCache class with three methods:
set(key, value, duration)stores the pair fordurationms and returns whether an unexpired entry for that key already existed.get(key)returns the value if it is still alive, otherwise-1.count()returns how many entries are currently alive.
Examples
const cache = new TimeLimitedCache();
cache.set(1, 42, 100); // false
cache.get(1); // 42
// 150ms later
cache.get(1);-1Constraints
- 0 <= key, value <= 10^9
- 0 <= duration <= 1000
- At most 100 calls
Notes
- Setting an existing key must clear the previous timer, or the earlier timeout deletes an entry that was just refreshed.
Hints
Cache With Time Limit (reference solution)
One way to do it. The Editorial tab walks through why it is written this way.
Solution
1class TimeLimitedCache {
2 constructor() { this.entries = new Map(); }
3 set(key, value, duration) {
4 const existing = this.entries.get(key);
5 if (existing) clearTimeout(existing.timer);
6 const timer = setTimeout(() => this.entries.delete(key), duration);
7 this.entries.set(key, { value, timer });
8 return Boolean(existing);
9 }
10 get(key) {
11 const entry = this.entries.get(key);
12 return entry ? entry.value : -1;
13 }
14 count() { return this.entries.size; }
15}Editorial: Cache With Time Limit
Letting the timer do the work
The tempting design stores an expiry timestamp and checks it on every read. That works, but then count() has to filter, get has to compare, and expired entries linger in memory until something happens to touch them.
Approach
Store the timeout id beside the value and let the timer delete the entry itself. Now the map only ever contains live entries, so get is a lookup and count is map.size.
Implementation
class TimeLimitedCache { constructor() { this.entries = new Map(); } set(key, value, duration) { const existing = this.entries.get(key); if (existing) clearTimeout(existing.timer); const timer = setTimeout(() => this.entries.delete(key), duration); this.entries.set(key, { value, timer }); return Boolean(existing); } get(key) { const entry = this.entries.get(key); return entry ? entry.value : -1; } count() { return this.entries.size; } }
Worth knowing
The subtlety is re-setting an existing key. Its old timer is still scheduled and still pointing at that key, so unless you clear it the earlier timeout fires and deletes an entry that was just refreshed. Clear first, then schedule.
set returns whether it overwrote a live entry, which falls out of checking the map before writing.