Find the bug · Medium

Fix the TTL Cache Expiry

Medium Find the bug Seen at Stripe, Cloudflare

TTLCache(ttlMs) stores integer values that expire ttlMs milliseconds after they were set. Time is passed in explicitly (nowMs) so the cache is testable.

set(key, value, nowMs) stores the value; it is valid while nowMs < setTime + ttlMs.
get(key, nowMs) returns the value, or -1 if the key is missing or expired.

An entry set at time 0 with a 1,000 ms TTL must be gone at exactly 1,000 ms. The cache below still returns it. Find the bug and fix it.

Example 1

Input: ["TTLCache","set","get","get"]
[[1000],[1,10,0],[1,999],[1,1000]]
Output: [null,null,10,-1]
Explanation: The buggy version returns 10 at 1000 ms.

The buggy code

class TTLCache {
  constructor(ttlMs) {
    this.ttlMs = ttlMs;
    this.entries = new Map(); // key -> { value, expiresAt }
  }

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

  get(key, nowMs) {
    const entry = this.entries.get(key);
    if (!entry || nowMs > entry.expiresAt) return -1;
    return entry.value;
  }
}

class TTLCache {
  private entries = new Map<number, { value: number; expiresAt: number }>();

  constructor(private ttlMs: number) {}

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

  get(key: number, nowMs: number): number {
    const entry = this.entries.get(key);
    if (!entry || nowMs > entry.expiresAt) return -1;
    return entry.value;
  }
}

class TTLCache:
    def __init__(self, ttl_ms: int):
        self.ttl_ms = ttl_ms
        self.entries: dict[int, tuple[int, int]] = {}  # key -> (value, expires_at)

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

    def get(self, key: int, now_ms: int) -> int:
        entry = self.entries.get(key)
        if entry is None or now_ms > entry[1]:
            return -1
        return entry[0]

<?php

class TTLCache
{
    /** @var array<int, array{int, int}> key => [value, expiresAt] */
    private array $entries = [];

    public function __construct(private int $ttlMs)
    {
    }

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

    public function get(int $key, int $nowMs): int
    {
        $entry = $this->entries[$key] ?? null;
        if ($entry === null || $nowMs > $entry[1]) {
            return -1;
        }
        return $entry[0];
    }
}

class TTLCache {
    private final int ttlMs;
    private final Map<Integer, long[]> entries = new HashMap<>(); // key -> {value, expiresAt}

    public TTLCache(int ttlMs) {
        this.ttlMs = ttlMs;
    }

    public void set(int key, int value, long nowMs) {
        entries.put(key, new long[]{value, nowMs + ttlMs});
    }

    public int get(int key, long nowMs) {
        long[] entry = entries.get(key);
        if (entry == null || nowMs > entry[1]) return -1;
        return (int) entry[0];
    }
}

Hints

Hint 1

Write down the exact time interval during which the entry is valid. Is the end included?

Find and fix the bug

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

Solution and explanation

Show the bug and the fix

Time O(1) per operation · Space O(n)

The bug: the entry is valid on the half-open interval [setTime, setTime + ttl), but the check treats it as expired only when now > expiresAt. At exactly expiresAt the stale value is still served. With a 1 ms TTL the entry lives twice as long as it should.

The fix: expire when now >= expiresAt (and optionally delete the entry). Off-by-one errors at time boundaries are a favourite interview bug because tests with "round" times rarely hit the boundary.

Fixed version

class TTLCache {
  constructor(ttlMs) {
    this.ttlMs = ttlMs;
    this.entries = new Map(); // key -> { value, expiresAt }
  }

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

  get(key, nowMs) {
    const entry = this.entries.get(key);
    if (!entry) return -1;
    if (nowMs >= entry.expiresAt) { // valid on [setTime, expiresAt)
      this.entries.delete(key);
      return -1;
    }
    return entry.value;
  }
}

class TTLCache {
  private entries = new Map<number, { value: number; expiresAt: number }>();

  constructor(private ttlMs: number) {}

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

  get(key: number, nowMs: number): number {
    const entry = this.entries.get(key);
    if (!entry) return -1;
    if (nowMs >= entry.expiresAt) { // valid on [setTime, expiresAt)
      this.entries.delete(key);
      return -1;
    }
    return entry.value;
  }
}

class TTLCache:
    def __init__(self, ttl_ms: int):
        self.ttl_ms = ttl_ms
        self.entries: dict[int, tuple[int, int]] = {}  # key -> (value, expires_at)

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

    def get(self, key: int, now_ms: int) -> int:
        entry = self.entries.get(key)
        if entry is None:
            return -1
        if now_ms >= entry[1]:  # valid on [set_time, expires_at)
            del self.entries[key]
            return -1
        return entry[0]

<?php

class TTLCache
{
    /** @var array<int, array{int, int}> key => [value, expiresAt] */
    private array $entries = [];

    public function __construct(private int $ttlMs)
    {
    }

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

    public function get(int $key, int $nowMs): int
    {
        $entry = $this->entries[$key] ?? null;
        if ($entry === null) {
            return -1;
        }
        if ($nowMs >= $entry[1]) { // valid on [setTime, expiresAt)
            unset($this->entries[$key]);
            return -1;
        }
        return $entry[0];
    }
}

class TTLCache {
    private final int ttlMs;
    private final Map<Integer, long[]> entries = new HashMap<>(); // key -> {value, expiresAt}

    public TTLCache(int ttlMs) {
        this.ttlMs = ttlMs;
    }

    public void set(int key, int value, long nowMs) {
        entries.put(key, new long[]{value, nowMs + ttlMs});
    }

    public int get(int key, long nowMs) {
        long[] entry = entries.get(key);
        if (entry == null) return -1;
        if (nowMs >= entry[1]) { // valid on [setTime, expiresAt)
            entries.remove(key);
            return -1;
        }
        return (int) entry[0];
    }
}

Common mistakes

Not refreshing the expiry when an existing key is set again.
Reading the wall clock inside the class, which makes the boundary impossible to test.

Follow-up questions

Evict expired entries without scanning (min-heap or timing wheel).
Bound the size as well: combine with LRU eviction.

Fix the Binary Search · Easy
Fix the Two Sum Hash Map · Easy
Fix the Longest Substring Without Repeats · Medium
Fix Merge Intervals · Medium
Fix the Mutable Default Argument · Easy
Fix the Substring Check · Easy