Coding problem · Medium · Design & Data Structures

Key-Value Store with TTL

Medium Practical tasks Seen at Amazon, Stripe, Shopify, Datadog

Build an in-memory key-value store where every entry has a time-to-live. Time is passed in (milliseconds) so behaviour is deterministic.

set(key, value, ttlMs, nowMs) stores value; it expires at nowMs + ttlMs. Setting an existing key replaces its value and expiry.
get(key, nowMs) returns the value, or null if missing or expired (an entry is expired when nowMs >= expiresAt).
count(nowMs) returns how many keys are not expired at nowMs.

Example 1

Input: ["TTLStore","set","get","get","count"]
[[],["a","1",100,0],["a",50],["a",100],[100]]
Output: [null,null,"1",null,0]

Hints

Hint 1

Store (value, expiresAt) per key.

Hint 2

get can lazily delete expired entries. For count, think about how real caches avoid scanning everything (expiry heaps, sampled eviction).

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(1) get/set, O(n) count · Space O(n)

Keep a map key → (value, expiresAt). get checks expiry and deletes stale entries lazily. count here scans and purges expired keys (O(n)); production caches combine lazy deletion with periodic cleanup — Redis samples random keys with a TTL, and a min-heap ordered by expiresAt lets you purge in O(log n) per expired key.

Reference solution

class TTLStore {
  constructor() {
    this.items = new Map(); // key -> { value, expiresAt }
  }

  set(key, value, ttlMs, nowMs) {
    this.items.set(key, { value, expiresAt: nowMs + ttlMs });
  }

  get(key, nowMs) {
    const e = this.items.get(key);
    if (!e) return null;
    if (nowMs >= e.expiresAt) {
      this.items.delete(key);
      return null;
    }
    return e.value;
  }

  count(nowMs) {
    for (const [k, e] of this.items) if (nowMs >= e.expiresAt) this.items.delete(k);
    return this.items.size;
  }
}

class TTLStore {
  private items = new Map<string, { value: string; expiresAt: number }>();

  set(key: string, value: string, ttlMs: number, nowMs: number): void {
    this.items.set(key, { value, expiresAt: nowMs + ttlMs });
  }

  get(key: string, nowMs: number): string | null {
    const e = this.items.get(key);
    if (!e || nowMs >= e.expiresAt) {
      this.items.delete(key);
      return null;
    }
    return e.value;
  }

  count(nowMs: number): number {
    for (const [k, e] of this.items) if (nowMs >= e.expiresAt) this.items.delete(k);
    return this.items.size;
  }
}

class TTLStore:
    def __init__(self):
        self.items: dict[str, tuple[str, int]] = {}

    def set(self, key: str, value: str, ttl_ms: int, now_ms: int) -> None:
        self.items[key] = (value, now_ms + ttl_ms)

    def get(self, key: str, now_ms: int) -> str | None:
        entry = self.items.get(key)
        if entry is None:
            return None
        value, expires_at = entry
        if now_ms >= expires_at:
            del self.items[key]
            return None
        return value

    def count(self, now_ms: int) -> int:
        self.items = {k: e for k, e in self.items.items() if now_ms < e[1]}
        return len(self.items)

<?php

class TTLStore
{
    /** @var array<string, array{0: string, 1: int}> */
    private array $items = [];

    public function set(string $key, string $value, int $ttlMs, int $nowMs): void
    {
        $this->items[$key] = [$value, $nowMs + $ttlMs];
    }

    public function get(string $key, int $nowMs): ?string
    {
        if (!isset($this->items[$key])) {
            return null;
        }
        [$value, $expiresAt] = $this->items[$key];
        if ($nowMs >= $expiresAt) {
            unset($this->items[$key]);
            return null;
        }
        return $value;
    }

    public function count(int $nowMs): int
    {
        $this->items = array_filter($this->items, fn($e) => $nowMs < $e[1]);
        return count($this->items);
    }
}

class TTLStore {
    private record Entry(String value, long expiresAt) {}
    private final Map<String, Entry> items = new HashMap<>();

    public TTLStore() {}

    public void set(String key, String value, int ttlMs, int nowMs) {
        items.put(key, new Entry(value, (long) nowMs + ttlMs));
    }

    public String get(String key, int nowMs) {
        Entry e = items.get(key);
        if (e == null) return null;
        if (nowMs >= e.expiresAt()) { items.remove(key); return null; }
        return e.value();
    }

    public int count(int nowMs) {
        items.values().removeIf(e -> nowMs >= e.expiresAt());
        return items.size();
    }
}

Follow-up questions

Bound memory: combine TTL with LRU eviction.
Make it safe for concurrent access.
Use a heap of expiry times to purge without scanning.

LRU Cache · Medium
Token Bucket Rate Limiter · Medium
URL Shortener Codes (Base62) · Easy
Build an EventEmitter · Medium
Row Lock Manager with Deadlock Detection · Hard
Versioned Store with Optimistic Locking · Easy