NeetCode #957LC-2622MediumJavaScript
← Back to All Problems#957 · #2622 · Cache With Time Limit(有时间限制的缓存)
📌 Problem Statement & Constraints
Implement a
TimeLimitedCache class: set(key, value, duration) stores an entry and returns whether the key already existed and was unexpired; get(key) returns the value if unexpired, otherwise -1; count() returns the number of unexpired entries. Constraints: at most 2 * 10^5 calls.💡 Core Algorithmic Approaches
- Store entries in a
Mapfrom key to an object holding the value and an absolute expiry timestamp (Date.now() + duration). setfirst checks whether an unexpired old entry exists (that decides the return value), then overwrites.getchecksexpire > Date.now()and returns -1 when the entry is missing or expired.countscans the entries and tallies the unexpired ones. This is lazy expiration: no timers, just a check at query time.
💻 Benchmark Python3 Implementation
var TimeLimitedCache = function() {
this.cache = new Map(); // key -> { value, expire }
};
TimeLimitedCache.prototype.set = function(key, value, duration) {
const now = Date.now();
const old = this.cache.get(key);
const existed = old !== undefined && old.expire > now;
this.cache.set(key, { value, expire: now + duration });
return existed;
};
TimeLimitedCache.prototype.get = function(key) {
const e = this.cache.get(key);
return e !== undefined && e.expire > Date.now() ? e.value : -1;
};
TimeLimitedCache.prototype.count = function() {
const now = Date.now();
let cnt = 0;
for (const e of this.cache.values()) {
if (e.expire > now) cnt++;
}
return cnt;
};⚡ Complexity Deep Dive
⏱️ Time Complexity
set and get are O(1); count is O(k) over k entries.
💾 Space Complexity
O(k): the cached entries.
⚠️ Interview Pitfalls & Follow-ups
- Basing
set's return value on mere key presence: an already-expired entry must be treated as absent. - Scheduling a timer per entry to delete it: many entries means many timers; lazy expiration is lighter.
- Writing
expire >= now: exactly-at-expiry should count as expired, so the strict comparison is correct. - Returning
nullorundefinedfromget: the problem requires -1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.