⚡Flashcard Drill➔
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

  1. Store entries in a Map from key to an object holding the value and an absolute expiry timestamp (Date.now() + duration).
  2. set first checks whether an unexpired old entry exists (that decides the return value), then overwrites.
  3. get checks expire > Date.now() and returns -1 when the entry is missing or expired.
  4. count scans 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 null or undefined from get: 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.
🎯 Drill This Card Now➔

🧩 Related JavaScript Problems