2622. Cache With Time Limit Solution

Q: Is Cache With Time Limit easy or hard?

Cache With Time Limit is rated Medium because it combines data structure design with time-based logic. The implementation itself is straightforward, but handling expiration correctly and keeping operations efficient requires careful design.

Q: Cache With Time Limit Python/Java solution

In Python or Java, store entries in a dictionary or HashMap with fields for value and expiry time. Use the current system time to determine whether a key is still valid. This keeps lookups constant time while enforcing time-based expiration.

Q: How to solve Cache With Time Limit in O(1)?

Store each key in a HashMap along with its expiration timestamp. On set, compute expiry as current time plus duration. On get or count, compare the stored timestamp with the current time and ignore expired entries. Hash lookups keep operations O(1) on average.

Q: What is the best approach for Cache With Time Limit?

The most practical solution uses a HashMap that stores both the value and an expiration timestamp for each key. Every operation checks the current time against the stored expiry. This keeps set and get operations O(1) on average while using O(n) space for stored entries.

Q: Is Cache With Time Limit asked at Google/Amazon/Meta?

Cache design with expiration (TTL) appears frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the underlying concepts of hash maps, expiration timestamps, and cache invalidation are common interview topics.

Q: What data structure is used in Cache With Time Limit?

The core structure is a HashMap that maps keys to value and expiration timestamp pairs. Some implementations also use a priority queue (min-heap) to track the next key that will expire and automatically remove outdated entries.

Q: What is the time complexity of Cache With Time Limit?

Using a HashMap with timestamps gives O(1) average time for set and get operations. The count operation may scan all keys, which is O(n). A priority queue design increases updates to O(log n) due to heap operations.

The problem

Write a class that allows getting and setting key-value pairs, however a time until expiration is associated with each key.

The class has three public methods:

set(key, value, duration): accepts an integer key, an integer value, and a duration in milliseconds. Once the duration has elapsed, the key should be inaccessible. The method should return true if the same un-expired key already exists and false otherwise. Both the value and duration should be overwritten if the key already exists.

get(key): if an un-expired key exists, it should return the associated value. Otherwise it should return -1.

count(): returns the count of un-expired keys.

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]
Explanation:
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]
Explanation:
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 <= 10⁹
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

Approach overview

Problem Overview: Design a cache where each key-value pair expires after a given time limit. You must implement set, get, and count so expired entries are ignored while active entries behave like a normal key-value store.

Approach 1: Using HashMap with Timestamps (Time: O(1), Space: O(n))

The straightforward solution stores each key in a hash map along with its value and expiration timestamp. When set(key, value, duration) runs, compute the expiry time using the current timestamp plus duration. Store both the value and expiry in the map. If the key already exists and hasn't expired yet, return true; otherwise overwrite it and return false.

For get(key), perform a constant-time hash lookup. If the key does not exist or the stored expiration time is less than the current time, treat it as expired and return -1. Otherwise return the stored value. The count() method iterates over stored entries and counts only those with expiry timestamps greater than the current time.

The key insight is lazy expiration. Instead of actively removing expired entries, the cache checks expiration only when the key is accessed or counted. This keeps set and get operations at O(1) average time while using O(n) space for stored entries. This design is common in lightweight in-memory caches and interview settings.

Approach 2: Using Priority Queue for Automatic Expiry (Time: O(log n), Space: O(n))

A more structured design tracks expirations using a priority queue (min-heap). Each entry pushed into the heap contains (expiryTime, key). The heap always keeps the earliest expiration at the top.

Before executing any cache operation, repeatedly remove heap entries whose expiry time is less than the current timestamp. When an item expires, remove its key from the map as well. This keeps the active cache clean without relying on lazy checks.

The hash map still stores the actual key-value pairs for constant-time retrieval, while the heap efficiently identifies the next item that should expire. Heap insertion and removal cost O(log n), which slightly increases runtime compared to the pure hash map solution, but it keeps the structure strictly synchronized with expiration events.

This pattern appears frequently in system design problems involving TTL caches, task scheduling, or delayed execution queues. Combining a hash map with a priority queue provides both fast lookups and efficient expiration management.

Recommended for interviews: The HashMap with timestamps approach is typically expected. It demonstrates strong understanding of constant-time lookups and lazy expiration logic. The priority queue version shows deeper design thinking and is closer to how production systems manage timed events, but the simpler hash map approach is usually sufficient in interviews.

Approach 1: Approach 1: Using HashMap with Timestamps

This approach involves using a HashMap (or dictionary in Python) to store the key-value pairs along with their expiration timestamps. The expiration timestamp is calculated at the time of insertion by adding the current time with the duration. Each time a get or count operation is performed, expired keys are ignored.

Python

from time import time

class TimeLimitedCache:
    def __init__(self):
        self.cache = {}

    def set(self, key, value, duration) -> bool:
        expiration = time() + duration / 1000.0
        exists = key in self.cache and self.cache[key][1] > time()
        self.cache[key] = (value, expiration)
        return exists

    def get(self, key) -> int:
        if key in self.cache:
            value, expiration = self.cache[key]
            if expiration > time():
                return value
        return -1

    def count(self) -> int:
        current_time = time()
        return sum(expiration > current_time for _, expiration in self.cache.values())

Java

import java.util.HashMap;
import java.util.Map;

class TimeLimitedCache {
    private class ValueEntry {
        int value;
        long expireAt;

        ValueEntry(int value, long expireAt) {
            this.value = value;
            this.expireAt = expireAt;
        }
    }

    private Map<Integer, ValueEntry> cache;

    public TimeLimitedCache() {
        cache = new HashMap<>();
    }

    public boolean set(int key, int value, int duration) {
        long expireTime = System.currentTimeMillis() + duration;
        boolean exists = cache.containsKey(key) && cache.get(key).expireAt > System.currentTimeMillis();
        cache.put(key, new ValueEntry(value, expireTime));
        return exists;
    }

    public int get(int key) {
        if (cache.containsKey(key)) {
            ValueEntry entry = cache.get(key);
            if (entry.expireAt > System.currentTimeMillis()) {
                return entry.value;
            }
        }
        return -1;
    }

    public int count() {
        int count = 0;
        long currentTime = System.currentTimeMillis();
        for (ValueEntry entry : cache.values()) {
            if (entry.expireAt > currentTime) {
                count++;
            }
        }
        return count;
    }
}

C++

#include <unordered_map>
#include <chrono>

using namespace std;
using namespace std::chrono;

class TimeLimitedCache {
private:
    unordered_map<int, pair<int, long long>> cache;

    long long currentTimeMillis() {
        return duration_cast<milliseconds>(steady_clock::now().time_since_epoch()).count();
    }

public:
    bool set(int key, int value, int duration) {
        long long expiration = currentTimeMillis() + duration;
        bool exists = cache.find(key) != cache.end() && cache[key].second > currentTimeMillis();
        cache[key] = {value, expiration};
        return exists;
    }

    int get(int key) {
        if (cache.find(key) != cache.end() && cache[key].second > currentTimeMillis()) {
            return cache[key].first;
        }
        return -1;
    }

    int count() {
        long long current_time = currentTimeMillis();
        int count = 0;
        for (const auto& entry : cache) {
            if (entry.second.second > current_time) {
                count++;
            }
        }
        return count;
    }
};

JavaScript

class TimeLimitedCache {
    constructor() {
        this.cache = new Map();
    }

    set(key, value, duration) {
        const expirationTime = Date.now() + duration;
        const exists = this.cache.has(key) && this.cache.get(key).expiration > Date.now();
        this.cache.set(key, { value, expiration: expirationTime });
        return exists;
    }

    get(key) {
        if (this.cache.has(key)) {
            const entry = this.cache.get(key);
            if (entry.expiration > Date.now()) {
                return entry.value;
            }
        }
        return -1;
    }

    count() {
        const currentTime = Date.now();
        let activeCount = 0;
        for (let [key, entry] of this.cache.entries()) {
            if (entry.expiration > currentTime) {
                activeCount++;
            }
        }
        return activeCount;
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#include <sys/time.h>

typedef struct {
    int value;
    long expiration_time;
} KeyValue;

typedef struct {
    KeyValue* hashmap;
    int capacity;
} TimeLimitedCache;

// Helper function to get the current time in milliseconds
long current_time_millis() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec * 1000 + tv.tv_usec / 1000;
}

TimeLimitedCache* timeLimitedCacheCreate(int capacity) {
    TimeLimitedCache* obj = (TimeLimitedCache*)malloc(sizeof(TimeLimitedCache));
    obj->hashmap = (KeyValue*)calloc(capacity, sizeof(KeyValue));
    obj->capacity = capacity;
    return obj;
}

bool timeLimitedCacheSet(TimeLimitedCache* obj, int key, int value, int duration) {
    long expiration_time = current_time_millis() + duration;
    bool exists = obj->hashmap[key % obj->capacity].expiration_time > current_time_millis();
    obj->hashmap[key % obj->capacity].value = value;
    obj->hashmap[key % obj->capacity].expiration_time = expiration_time;
    return exists;
}

int timeLimitedCacheGet(TimeLimitedCache* obj, int key) {
    KeyValue kv = obj->hashmap[key % obj->capacity];
    if (kv.expiration_time > current_time_millis()) {
        return kv.value;
    }
    return -1;
}

int timeLimitedCacheCount(TimeLimitedCache* obj) {
    int count = 0;
    long current_time = current_time_millis();
    for (int i = 0; i < obj->capacity; i++) {
        if (obj->hashmap[i].expiration_time > current_time) {
            count++;
        }
    }
    return count;
}

void timeLimitedCacheFree(TimeLimitedCache* obj) {
    free(obj->hashmap);
    free(obj);
}

using System;
using System.Collections.Generic;

class TimeLimitedCache {
    private class CacheEntry {
        public int Value { get; set; }
        public DateTime ExpireAt { get; set; }
    }

    private Dictionary<int, CacheEntry> cache;

    public TimeLimitedCache() {
        cache = new Dictionary<int, CacheEntry>();
    }

    public bool Set(int key, int value, int duration) {
        DateTime expirationTime = DateTime.Now.AddMilliseconds(duration);
        bool exists = cache.ContainsKey(key) && cache[key].ExpireAt > DateTime.Now;
        cache[key] = new CacheEntry { Value = value, ExpireAt = expirationTime };
        return exists;
    }

    public int Get(int key) {
        if (cache.ContainsKey(key) && cache[key].ExpireAt > DateTime.Now) {
            return cache[key].Value;
        }
        return -1;
    }

    public int Count() {
        DateTime currentTime = DateTime.Now;
        int count = 0;
        foreach (var entry in cache.Values) {
            if (entry.ExpireAt > currentTime) {
                count++;
            }
        }
        return count;
    }
}

This Python solution uses a dictionary to map keys to tuples containing the value and expiration timestamp. The set method updates the cache with the new expiration time, returning whether the key was previously valid. The get method checks current time against expiration. The count method uses a generator expression to count unexpired keys.

Complexity

Time Complexity: O(1) on average for set and get operations, O(n) for count operation.
Space Complexity: O(n), where n is the number of active keys.

Try this approach in the editor

Approach 2: Approach 2: Using Priority Queue for Automatic Expiry

This approach combines a HashMap to store the values and their expiration time, with a PriorityQueue (or equivalent) to keep track of the order in which keys expire. Whenever a key is accessed or updated, expired keys at the front of the queue are removed to keep the cache up-to-date. This enables efficient removal of expired elements.

Java

import java.util.*;

class TimeLimitedCache {
    private static class ExpiryEntry implements Comparable<ExpiryEntry> {
        int key;
        long expireAt;

        ExpiryEntry(int key, long expireAt) {
            this.key = key;
            this.expireAt = expireAt;
        }

        @Override
        public int compareTo(ExpiryEntry other) {
            return Long.compare(this.expireAt, other.expireAt);
        }
    }

    private Map<Integer, int[]> cache;
    private PriorityQueue<ExpiryEntry> expiryQueue;

    public TimeLimitedCache() {
        cache = new HashMap<>();
        expiryQueue = new PriorityQueue<>();
    }

    private void cleanup() {
        long currentTime = System.currentTimeMillis();
        while (!expiryQueue.isEmpty() && expiryQueue.peek().expireAt <= currentTime) {
            ExpiryEntry entry = expiryQueue.poll();
            if (cache.containsKey(entry.key) && cache.get(entry.key)[1] <= entry.expireAt) {
                cache.remove(entry.key);
            }
        }
    }

    public boolean set(int key, int value, int duration) {
        cleanup();
        long expireAt = System.currentTimeMillis() + duration;
        boolean exists = cache.containsKey(key) && cache.get(key)[1] > System.currentTimeMillis();
        cache.put(key, new int[]{value, (int) expireAt});
        expiryQueue.add(new ExpiryEntry(key, expireAt));
        return exists;
    }

    public int get(int key) {
        cleanup();
        if (cache.containsKey(key)) {
            int[] entry = cache.get(key);
            if (entry[1] > System.currentTimeMillis()) {
                return entry[0];
            }
        }
        return -1;
    }

    public int count() {
        cleanup();
        return cache.size();
    }
}

C++

#include <unordered_map>
#include <queue>
#include <utility>
#include <chrono>

using namespace std;
using namespace std::chrono;

struct ExpiryEntry {
    int key;
    long long expireAt;
    bool operator>(const ExpiryEntry& other) const {
        return expireAt > other.expireAt;
    }
};

class TimeLimitedCache {
private:
    unordered_map<int, pair<int, long long>> cache;
    priority_queue<ExpiryEntry, vector<ExpiryEntry>, greater<>> expiryQueue;

    long long currentTimeMillis() {
        return duration_cast<milliseconds>(steady_clock::now().time_since_epoch()).count();
    }

    void cleanup() {
        while (!expiryQueue.empty() && expiryQueue.top().expireAt < currentTimeMillis()) {
            int key = expiryQueue.top().key;
            if (cache[key].second <= expiryQueue.top().expireAt) {
                cache.erase(key);
            }
            expiryQueue.pop();
        }
    }

public:
    bool set(int key, int value, int duration) {
        cleanup();
        long long current_time = currentTimeMillis();
        long long expireAt = current_time + duration;
        bool exists = cache.find(key) != cache.end() && cache[key].second > current_time;
        cache[key] = {value, expireAt};
        expiryQueue.push({key, expireAt});
        return exists;
    }

    int get(int key) {
        cleanup();
        if (cache.find(key) != cache.end() && cache[key].second > currentTimeMillis()) {
            return cache[key].first;
        }
        return -1;
    }

    int count() {
        cleanup();
        return cache.size();
    }
};

This Java solution employs a HashMap for quick access and a PriorityQueue for managing expiration. The queue allows quick determination of expired entries, and periodic cleanup ensures that the map holds only valid items.

Complexity

Time Complexity: O(log n) for set and cleanup due to the priority queue, with O(1) average time for get.
Space Complexity: O(n), where n is the number of active keys.

Try this approach in the editor

Approach 3: 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
 */

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Using HashMap with Timestamps	Time Complexity: `O(1)` on average for set and get operations, `O(n)` for count operation. Space Complexity: `O(n)`, where `n` is the number of active keys.
Approach 2: Using Priority Queue for Automatic Expiry	Time Complexity: `O(log n)` for set and cleanup due to the priority queue, with `O(1)` average time for get. Space Complexity: `O(n)`, where `n` is the number of active keys.
Hash Table	–

Complexity analysis

Approach	Time	Space	When to Use
HashMap with Timestamps	O(1) average for set/get, O(n) for count	O(n)	Best general solution. Simple implementation with lazy expiration checks.
HashMap + Priority Queue (Min Heap)	O(log n) per insertion/expiry	O(n)	Useful when automatic cleanup of expired entries is required.

Frequently asked questions

Is Cache With Time Limit easy or hard?

Cache With Time Limit is rated Medium because it combines data structure design with time-based logic. The implementation itself is straightforward, but handling expiration correctly and keeping operations efficient requires careful design.

Cache With Time Limit Python/Java solution

In Python or Java, store entries in a dictionary or HashMap with fields for value and expiry time. Use the current system time to determine whether a key is still valid. This keeps lookups constant time while enforcing time-based expiration.

How to solve Cache With Time Limit in O(1)?

Store each key in a HashMap along with its expiration timestamp. On set, compute expiry as current time plus duration. On get or count, compare the stored timestamp with the current time and ignore expired entries. Hash lookups keep operations O(1) on average.

What is the best approach for Cache With Time Limit?

The most practical solution uses a HashMap that stores both the value and an expiration timestamp for each key. Every operation checks the current time against the stored expiry. This keeps set and get operations O(1) on average while using O(n) space for stored entries.

Is Cache With Time Limit asked at Google/Amazon/Meta?

Cache design with expiration (TTL) appears frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the underlying concepts of hash maps, expiration timestamps, and cache invalidation are common interview topics.

What data structure is used in Cache With Time Limit?

The core structure is a HashMap that maps keys to value and expiration timestamp pairs. Some implementations also use a priority queue (min-heap) to track the next key that will expire and automatically remove outdated entries.

What is the time complexity of Cache With Time Limit?

Using a HashMap with timestamps gives O(1) average time for set and get operations. The count operation may scan all keys, which is O(n). A priority queue design increases updates to O(log n) due to heap operations.

Cache With Time Limit solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Using HashMap with Timestamps

Approach 2: Approach 2: Using Priority Queue for Automatic Expiry

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Cache With Time Limit solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Using HashMap with Timestamps

Approach 2: Approach 2: Using Priority Queue for Automatic Expiry

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems