← 返回 netflix 的题目列表Design a TTL Cache (cache with time limit)
类型：online_judge
Problem: Implement a TTL Cache (cache with time limit)
Implement a cache that supports key-based access where each entry has a time-to-live (TTL). Once an entry expires, reads should behave as a miss and the expired data must not be returned.
Required operations
set(key, value, ttl): store a key/value pair with an expiration time of ttl after “now”.
get(key): if key exists and is not expired, return the value; otherwise return a miss (e.g., null/-1).
Follow-up requirements (commonly asked)
Repeated set on the same key overwrites the previous value and expiry.
Explain how to clean up expired entries without blocking reads/writes (lazy deletion vs periodic cleanup) and analyze complexity.
I/O format (can be described verbally)
Given a sequence of operations, output the result of each get.
Constraints
Up to 2 * 10^5 operations
Keys/values are strings or integers
ttl is a positive integer (time unit can be seconds/milliseconds)
Test cases
input:
set a 1 5
get a
output:
1
input:
set a 1 1
(wait 2)
get a
output:
null
input:
set a 1 5
set a 2 5
get a
output:
2
input:
set a 1 2
set b 2 10
(wait 3)
get a
get b
output:
null
2
input:
set a 1 2
(wait 1)
get a
(wait 2)
get a
output:
1
null
Example
Input
set a 1 5
get a
Output
1