Cache With Time Limit
Asked at Netflix
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.
Asked At
| 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.
Visual walkthrough with T0 = 1000 (timestamps in ms):
- set(1, 10, 500) at 1000: no entry, store (10, 1500), return False.
- get(1) at 1200: 1500 > 1200, return 10.
- get(1) at 1600: expired, return -1.
- count at 1600: 0.
- set(1, 20, 500) at 1600: old entry expired, store (20, 2100), return False.
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.
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
import 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.