Cache With Time Limit
Asked at Netflix
Difficulty
Medium
Time
O(1) for set and get; O(k) for c
Space
O(n)
Pattern
—
Companies
1
Problem
Design a class called TimeLimitedCache. It stores key-value pairs, but every key also gets a time limit: after that many milliseconds pass, the key is gone.
Implement three methods:
set(key, value, duration)— storevalueunderkeyfordurationmilliseconds. Returntrueif an unexpired entry already existed for this key, andfalseotherwise. If the key already exists, replace both the value and the time limit.get(key)— return the stored value if the key is still alive. Otherwise return-1.count()— return how many keys are still alive right now.
A key expires when the current time reaches its deadline. So an entry whose deadline equals the current time is already dead. An expired entry is treated as if it never existed: set on it returns false, and get on it returns -1.
A key has a deadline
Constraints
- ●
0 <= key, value <= 10^9 - ●
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" - ●
The first action is always "TimeLimitedCache" and runs immediately at time 0
Examples
actions = ["TimeLimitedCache", "set", "get", "count", "get"]
values = [[], [1, 42, 100], [1], [], [1]]
timeDelays = [0, 0, 50, 50, 150][null, false, 42, 1, -1]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][null, false, true, 50, 50, -1, 0]actions = ["TimeLimitedCache", "set", "get"]
values = [[], [7, 99, 0], [7]]
timeDelays = [0, 0, 0][null, false, -1]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Netflix | Medium | View all Netflix questions → |
How to Think About It
Baseline: keep a hash map from key to value; every operation is O(1). The difficulty is not speed but correctness - deciding the exact expiry comparison rule at the moment of each call.
Key insight: store the absolute expiry timestamp (now + duration) beside each value, not the raw duration. Comparing the current clock against an absolute expiry makes get and count trivial.
set semantics: return True only if an unexpired entry already exists under that key. An expired entry behaves like no entry at all - overwrite it and return False. This subtle edge decides a correct answer.
count semantics: count entries whose stored expiry is strictly greater than the current time. Keep the map untouched - no lazy deletion - because purging during count would force a O(n) scan anyway.
Edge cases: a zero duration expires immediately, so a read right after the write already returns -1; reading a key that was never written returns -1; repeatedly setting the same key just replaces the entry and expiry.
Optimal Approach
Back the cache with a hash map from key to a pair of (value, absolute expiry timestamp). In set, snapshot the current time t, compute existed = an entry exists whose expiry is strictly greater than t, overwrite the entry with (value, t + duration), and return existed. In get, fetch the entry and return its value only while the expiry is strictly greater than now, otherwise -1. In count, iterate all entries and tally those whose expiry exceeds now, never deleting in place.
Walkthrough with timestamps in milliseconds, starting at t = 1000:
- set(1, 5, 500) at 1000: no prior entry, store (5, 1500), return False.
- get(1) at 1200: 1500 > 1200, return 5.
- get(1) at 1600: 1500 <= 1600, expired, return -1.
- count at 1600: 0.
- set(1, 9, 300) at 1600: old entry expired, store (9, 1900), return False.
Time: O(1) for set and get; count walks the map in O(k) for k distinct keys. Space: O(n) for n keys ever written.
Store the deadline, not the duration
What Trips People Up in Real Interviews
Storing the remaining duration instead of the absolute deadline. Remaining time goes stale the instant it is stored, and comparing stored remnants is wrong. Store now + duration.
Returning True in set when only an expired value exists under the key. The spec defines "existed" as an unexpired value, so an expired key behaves like a fresh write: overwrite and return False.
Using inconsistent boundary comparisons. If get treats a key at exactly the expiry as dead, then count and the "existed" check in set must use the same strict rule, or results disagree under the same clock.
Physically deleting entries to "clean up". Deletion forces a O(n) sweep or complicates the write path. Compare expiry timestamps in place and let stale entries linger until overwritten.
Trying to fake time with a per-call counter. The duration is real wall-clock time, so simulation with a counter breaks. Use Date.now() or a monotonic clock to compute deadlines.
Solution Code
O(1) for set and get; O(k) for c timeimport time
class TimeLimitedCache:
def __init__(self):
self.cache = {}
def set(self, key, value, duration):
now = time.time()
existed = key in self.cache and self.cache[key][1] > now
self.cache[key] = (value, now + duration)
return existed
def get(self, key):
if key not in self.cache:
return -1
value, expire = self.cache[key]
if time.time() >= expire:
return -1
return value
def count(self):
now = time.time()
return sum(1 for value, expire in self.cache.values() if expire > now)Frequently Asked Questions
What is the Cache With Time Limit problem?
Design a `TimeLimitedCache` where writing a key stores a value with a duration in milliseconds, reading returns -1 once the key expires, and an instant count reports how many keys are still alive. `set` also returns whether an unexpired value already existed - a time-aware data-structure design question from Netflix.
How do you solve Cache With Time Limit?
The optimal approach runs in O(1) for set and get; O(k) for c time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Cache With Time Limit?
Cache With Time Limit is asked at Netflix. It is a medium difficulty problem.
What are common mistakes on Cache With Time Limit?
- Storing the remaining duration instead of the absolute deadline. Remaining time goes stale the instant it is stored, and comparing stored remnants is wrong. Store `now + duration`.
- Returning True in `set` when only an expired value exists under the key. The spec defines "existed" as an unexpired value, so an expired key behaves like a fresh write: overwrite and return False.
- Using inconsistent boundary comparisons. If `get` treats a key at exactly the expiry as dead, then `count` and the "existed" check in `set` must use the same strict rule, or results disagree under the same clock.
- Physically deleting entries to "clean up". Deletion forces a `O(n)` sweep or complicates the write path. Compare expiry timestamps in place and let stale entries linger until overwritten.
- Trying to fake time with a per-call counter. The duration is real wall-clock time, so simulation with a counter breaks. Use `Date.now()` or a monotonic clock to compute deadlines.