#2622

Medium

auto_awesomeCache With Time Limit core interview pattern

LeetCode Problem Workspace

Cache With Time Limit

Implement a time-limited cache where keys expire after a given duration, with operations to set, get, and count active keys.

Problem Statement

You are tasked with implementing a time-limited cache that can store key-value pairs. Each key has an associated expiration time, defined in milliseconds. The cache should return values only if they have not expired.

The cache has three methods: set(key, value, duration) for adding key-value pairs with a time limit, get(key) to retrieve the value of a key, and count() to count the number of active (non-expired) keys. After the specified duration, a key is no longer accessible, and its value is discarded.

Examples

Example 1

Input: actions = ["TimeLimitedCache", "set", "get", "count", "get"] values = [[], [1, 42, 100], [1], [], [1]] timeDelays = [0, 0, 50, 50, 150]

Output: [null, false, 42, 1, -1]

At t=0, the cache is constructed. At t=0, a key-value pair (1: 42) is added with a time limit of 100ms. The value doesn't exist so false is returned. At t=50, key=1 is requested and the value of 42 is returned. At t=50, count() is called and there is one active key in the cache. At t=100, key=1 expires. At t=150, get(1) is called but -1 is returned because the cache is empty.

Example 2

Input: actions = ["TimeLimitedCache", "set", "set", "get", "get", "get", "count"] values = [[], [1, 42, 50], [1, 50, 100], [1], [1], [1], []] timeDelays = [0, 0, 40, 50, 120, 200, 250]

Output: [null, false, true, 50, 50, -1, 0]

At t=0, the cache is constructed. At t=0, a key-value pair (1: 42) is added with a time limit of 50ms. The value doesn't exist so false is returned. At t=40, a key-value pair (1: 50) is added with a time limit of 100ms. A non-expired value already existed so true is returned and the old value was overwritten. At t=50, get(1) is called which returned 50. At t=120, get(1) is called which returned 50. At t=140, key=1 expires. At t=200, get(1) is called but the cache is empty so -1 is returned. At t=250, count() returns 0 because the cache is empty.

Constraints

0 <= key, value <= 109
0 <= duration <= 1000
1 <= actions.length <= 100
actions.length === values.length
actions.length === timeDelays.length
0 <= timeDelays[i] <= 1450
actions[i] is one of "TimeLimitedCache", "set", "get" and "count"
First action is always "TimeLimitedCache" and must be executed immediately, with a 0-millisecond delay

Solution Approach

Use Timers for Expiration

To manage key expiration, use a timer mechanism such as setTimeout to track the time limit for each key. When a key is set, schedule its expiration by creating a timeout for the given duration, and store the timer reference for easy cancellation if the key is overwritten.

Efficient Data Structures

A hashmap (or dictionary) is suitable for storing key-value pairs, while an additional structure can hold expiration timestamps or timer references for each key. This ensures efficient lookups and expiration handling.

Handling Overwrites

When a new key is set, check if it already exists. If it does, overwrite both the value and expiration time, and reset the timer. This ensures the cache correctly reflects the latest data, even if the key has previously expired.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the final approach but generally involves O(1) for set, get, and count operations. Space complexity is also O(n), where n is the number of keys stored in the cache, as each key requires both storage and a timer reference.

What Interviewers Usually Probe

Can the candidate efficiently handle key expiration using timers?
Is the candidate able to optimize for both space and time complexity while managing cache expiration?
Does the candidate ensure that overwriting a key correctly updates both the value and the expiration timer?

Common Pitfalls or Variants

Common pitfalls

Not handling key overwrites properly and not resetting the expiration timer.
Failing to clean up expired keys efficiently, leading to memory leaks or slow performance.
Not accounting for the precise timing of expiration and the effect of delayed get or count operations.

Follow-up variants

Implementing a persistent cache where keys survive beyond program execution.
Handling different expiration durations for each key dynamically in more complex use cases.
Optimizing for large-scale caches where multiple operations need to be processed concurrently.

FAQ

What is the core challenge of the Cache With Time Limit problem?

The core challenge is managing key expiration and ensuring that keys are properly removed after their specified duration, without causing memory or performance issues.

How can I handle expired keys efficiently in this problem?

Expired keys can be tracked using timers and a cleanup mechanism, where the cache removes keys once their expiration time has passed.

Can I use a regular hashmap for storing keys in this problem?

Yes, a hashmap can be used for storing key-value pairs, but you also need a mechanism for tracking expiration times and managing timers for each key.

What happens if I try to get a key that has expired?

If you attempt to get a key that has expired, the method should return -1, indicating that the key is no longer accessible.

How does GhostInterview help with the Cache With Time Limit problem?

GhostInterview provides step-by-step assistance in implementing cache expiration logic, managing timers efficiently, and debugging common pitfalls, ensuring an optimized solution.

terminal

Solution

Solution 1: Hash Table

#### TypeScript

class TimeLimitedCache {
    #cache: Map<number, [value: number, expire: number]> = new Map();

    set(key: number, value: number, duration: number): boolean {
        const isExist = this.#cache.has(key);

        if (!this.#isExpired(key)) {
            this.#cache.set(key, [value, Date.now() + duration]);
        }

        return isExist;
    }

    get(key: number): number {
        if (this.#isExpired(key)) return -1;
        const res = this.#cache.get(key)?.[0] ?? -1;
        return res;
    }

    count(): number {
        const xs = Array.from(this.#cache).filter(([key]) => !this.#isExpired(key));
        return xs.length;
    }

    #isExpired = (key: number) =>
        this.#cache.has(key) &&
        (this.#cache.get(key)?.[1] ?? Number.NEGATIVE_INFINITY) < Date.now();
}

/**
 * Your TimeLimitedCache object will be instantiated and called as such:
 * var obj = new TimeLimitedCache()
 * obj.set(1, 42, 1000); // false
 * obj.get(1) // 42
 * obj.count() // 1
 */

Explore more problems →

auto_awesome

Continue Pattern

Cache With Time Limit core interview pattern

Expand the same solving frame across more problems.

arrow_forward signal_cellular_alt

Same Difficulty Track

Medium

Stay on this level to stabilize interview delivery.

arrow_forward