Cache With Time Limit - Practice Coding Problems

Cache With Time Limit - Problem

JavaScript Medium

Design a time-based cache class that allows getting and setting key-value pairs with expiration times.

The class should have three public methods:

set(key, value, duration): Accepts an integer key, integer value, and duration in milliseconds. Returns true if the same unexpired key already exists, false otherwise. Overwrites both value and duration if key exists.
get(key): Returns the associated value if an unexpired key exists, otherwise returns -1.
count(): Returns the count of unexpired keys.

Keys automatically become inaccessible once their duration has elapsed.

Input & Output

Example 1 — Basic Cache Operations

$ Input: operations = [["set", 1, 42, 1000], ["get", 1], ["count"], ["get", 1]]

› Output: [false, 42, 1, 42]

💡 Note: Set key 1 to 42 with 1000ms TTL (returns false - no existing key). Get key 1 returns 42. Count returns 1 active key. Get key 1 again still returns 42.

Example 2 — Key Overwrite

$ Input: operations = [["set", 1, 10, 1000], ["set", 1, 20, 2000], ["get", 1]]

› Output: [false, true, 20]

💡 Note: First set returns false (no existing key). Second set returns true (key 1 exists and is valid). Get returns new value 20.

Example 3 — Expiration Test

$ Input: operations = [["set", 1, 100, 50], ["count"], ["count"]]

› Output: [false, 1, 0]

💡 Note: Set key 1 with 50ms TTL. First count returns 1. After 50ms delay, second count returns 0 (expired).

Constraints

1 ≤ operations.length ≤ 100
0 ≤ key ≤ 10⁵
1 ≤ value ≤ 10⁸
1 ≤ duration ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Operations

Set key 1 to value 42 with 1000ms TTL

Cache Storage

Store with current timestamp + duration as expiration

Access & Validation

Check if current time < expiration time on get/count

Key Takeaway

🎯 Key Insight: Store expiration timestamp with each entry and validate on every access for automatic TTL behavior

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Facebook 18

The key insight is to store each cache entry with its expiration timestamp and validate on access. Use a Map to store key-value pairs along with expiration times, checking current time vs expiration on every operation. Best approach uses lazy cleanup with periodic maintenance for memory efficiency. Time: O(1), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Lazy Cleanup with Background Timer	O(1)	O(n)	Same approach but with periodic cleanup to prevent memory buildup
Store with Expiration Check	O(1)	O(n)	Use Map to store values with expiration timestamps, check validity on each operation

Lazy Cleanup with Background Timer — Algorithm Steps

Store entries with expiration timestamps
Validate on access as before
Periodically clean up expired entries to save memory

Visualization

Tap to expand

Step-by-Step Walkthrough

Normal Operations

Fast timestamp-based validation

Periodic Cleanup

Remove expired entries every 5 seconds

Memory Efficiency

Lower memory usage over time

Code -

solution.c — C

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

#define MAX_CACHE_SIZE 1000

typedef struct {
    int key;
    int value;
    long long expires;
    int active;
} CacheItem;

typedef struct {
    CacheItem items[MAX_CACHE_SIZE];
    int size;
    long long lastCleanup;
    long long cleanupInterval;
} TimeLimitedCache;

long long getCurrentTime() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec * 1000 + tv.tv_usec / 1000;
}

TimeLimitedCache* createCache() {
    TimeLimitedCache* cache = malloc(sizeof(TimeLimitedCache));
    cache->size = 0;
    cache->lastCleanup = getCurrentTime();
    cache->cleanupInterval = 5000;
    for (int i = 0; i < MAX_CACHE_SIZE; i++) {
        cache->items[i].active = 0;
    }
    return cache;
}

void cleanupExpired(TimeLimitedCache* cache) {
    long long currentTime = getCurrentTime();
    for (int i = 0; i < cache->size; i++) {
        if (cache->items[i].active && cache->items[i].expires <= currentTime) {
            cache->items[i].active = 0;
        }
    }
    cache->lastCleanup = currentTime;
}

void maybeCleanup(TimeLimitedCache* cache) {
    long long currentTime = getCurrentTime();
    if (currentTime - cache->lastCleanup > cache->cleanupInterval) {
        cleanupExpired(cache);
    }
}

int findKey(TimeLimitedCache* cache, int key) {
    for (int i = 0; i < cache->size; i++) {
        if (cache->items[i].active && cache->items[i].key == key) {
            return i;
        }
    }
    return -1;
}

int cacheSet(TimeLimitedCache* cache, int key, int value, int duration) {
    maybeCleanup(cache);
    long long currentTime = getCurrentTime();
    int index = findKey(cache, key);
    int exists = (index != -1 && cache->items[index].expires > currentTime);
    
    if (index == -1) {
        index = cache->size++;
        cache->items[index].key = key;
        cache->items[index].active = 1;
    }
    
    cache->items[index].value = value;
    cache->items[index].expires = currentTime + duration;
    
    return exists;
}

int cacheGet(TimeLimitedCache* cache, int key) {
    maybeCleanup(cache);
    long long currentTime = getCurrentTime();
    int index = findKey(cache, key);
    
    if (index != -1) {
        if (cache->items[index].expires > currentTime) {
            return cache->items[index].value;
        }
        cache->items[index].active = 0;
    }
    
    return -1;
}

int cacheCount(TimeLimitedCache* cache) {
    maybeCleanup(cache);
    long long currentTime = getCurrentTime();
    int count = 0;
    
    for (int i = 0; i < cache->size; i++) {
        if (cache->items[i].active) {
            if (cache->items[i].expires > currentTime) {
                count++;
            } else {
                cache->items[i].active = 0;
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    TimeLimitedCache* cache = createCache();
    
    printf("[]");
    
    free(cache);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Individual operations remain O(1), cleanup is amortized

✓ Linear Growth

Space Complexity

O(n)

Map stores n active entries, expired entries cleaned periodically

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Lazy Cleanup with Background Timer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler