132. Design a TTL (Time to Live) Cache

Design a TTL (Time to Live) Cache

Design a TTL based Cache.

The cache stores key-value pairs, where each key is associated with a time-to-live (TTL). A key is available only for its valid TTL window and becomes expired after that.

To keep the behavior deterministic for interviews and testing, every cache operation that depends on time receives an explicit currentTime value (in seconds) instead of reading the system clock. This includes both write and read operations.

When a key is inserted at time t with ttlSeconds, it remains valid for all times currentTime < t + ttlSeconds and becomes expired when currentTime >= t + ttlSeconds.

If an existing key is inserted again, its old value and expiration time are replaced by the new value and TTL. Expired keys should not be returned by read operations and should not be counted as active keys.

Across a single test sequence, all currentTime values passed to cache methods are guaranteed to be monotonically increasing, that is, non-decreasing.

Method Signatures

Constructor

TTLCache()

Initializes an empty TTL cache.
No key exists in the cache immediately after construction.

Insert or Update

void put(String key, String value, int ttlSeconds, int currentTime)

key is the cache key to insert or update.
value is the value associated with the key.
ttlSeconds >= 1
currentTime >= 0
If key already exists, its value and expiration time are replaced.
The key remains valid for any query time t such that t < currentTime + ttlSeconds.

Read Value

String get(String key, int currentTime)

key is the cache key to read.
currentTime >= 0
This method also receives explicit time as input and does not read the system clock.
Returns the stored value if the key exists and is not expired at currentTime.
Returns empty string "" if the key does not exist or has already expired.

Count Active Keys

int getActiveKeyCount(int currentTime)

currentTime >= 0
Returns the number of keys that are still valid at currentTime.
Expired keys must not be counted.

Rules

A key inserted at time t with TTL d is valid for all times < t + d.
A key is expired starting from time t + d.
Re-inserting the same key resets both its value and expiration time.
Reading an expired key returns "".
Only non-expired keys are included in getActiveKeyCount.
All parameter values are non-null.
For every method call that takes currentTime, the provided time is explicit input.
Across all method calls in one test sequence, currentTime values are non-decreasing.

Constraints

0 <= currentTime <= 10^8
1 <= ttlSeconds <= 10^6
1 <= key.length() <= 100
1 <= value.length() <= 100
key and value contain printable characters.
All method calls in a test sequence use non-decreasing currentTime.
At most 10^5 total method calls are made.

Examples

Example 1

TTLCache cache = new TTLCache()
cache.put(key = "A", value = "apple", ttlSeconds = 5, currentTime = 10)
cache.get(key = "A", currentTime = 12) returns "apple"
cache.getActiveKeyCount(currentTime = 12) returns 1

The key "A" expires at time 15, so it is still valid at time 12.

Example 2

TTLCache cache = new TTLCache()
cache.put(key = "A", value = "apple", ttlSeconds = 5, currentTime = 10)
cache.get(key = "A", currentTime = 15) returns ""
cache.getActiveKeyCount(currentTime = 15) returns 0

The key expires exactly at time 15, so it is no longer available at that time.

Example 3

TTLCache cache = new TTLCache()
cache.put(key = "A", value = "apple", ttlSeconds = 5, currentTime = 10)
cache.put(key = "A", value = "apricot", ttlSeconds = 10, currentTime = 12)
cache.get(key = "A", currentTime = 16) returns "apricot"
cache.get(key = "A", currentTime = 22) returns ""

The second put replaces both the value and the expiration time. After the update at time 12 with TTL 10, the new expiration time becomes 22.

Example 4

TTLCache cache = new TTLCache()
cache.put(key = "A", value = "apple", ttlSeconds = 4, currentTime = 1)
cache.put(key = "B", value = "banana", ttlSeconds = 3, currentTime = 2)
cache.put(key = "C", value = "carrot", ttlSeconds = 10, currentTime = 3)
cache.getActiveKeyCount(currentTime = 4) returns 3
cache.getActiveKeyCount(currentTime = 5) returns 1
cache.getActiveKeyCount(currentTime = 13) returns 0

Key "A" expires at time 5, key "B" expires at time 5, and key "C" expires at time 13. So at time 5, only "C" is still active.

Example 5

TTLCache cache = new TTLCache()
cache.get(key = "missing", currentTime = 7) returns ""
cache.getActiveKeyCount(currentTime = 7) returns 0

Reading a key that was never inserted returns "".

Example 6

TTLCache cache = new TTLCache()
cache.put(key = "X", value = "x1", ttlSeconds = 3, currentTime = 5)
cache.get(key = "X", currentTime = 5) returns "x1"
cache.get(key = "X", currentTime = 7) returns "x1"
cache.get(key = "X", currentTime = 8) returns ""

The read operation also uses the provided currentTime. The key is valid at times 5 and 7, and expires at time 8.