Problem
Write a class that allows getting and setting key-value pairs, however a time until expiration is associated with each key.
The class has three public methods:
set(key, value, duration)
: accepts an integer key
, an integer value
, and a duration
in milliseconds. Once the duration
has elapsed, the key should be inaccessible. The method should return true
if the same un-expired key already exists and false
otherwise. Both the value and duration should be overwritten if the key already exists.
get(key)
: if an un-expired key exists, it should return the associated value. Otherwise it should return -1
.
count()
: returns the count of un-expired keys.
Examples
Example 1
|
|
Example 2
|
|
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”- First action is always “TimeLimitedCache” and must be executed immediately, with a 0-millisecond delay
Solution
Method 1 – Hash Map with Expiry Tracking
Intuition
We use a hash map to store each key’s value and its expiry timestamp. When setting a key, we update its value and expiry. When getting a key or counting, we check if the key is expired and remove it if so. This ensures all operations are efficient and expired keys are not accessible.
Approach
- Use a hash map to store key → { value, expiry }.
- For
set(key, value, duration)
, check if the key exists and is not expired:- If so, return true; otherwise, return false.
- Update the value and expiry to now + duration.
- For
get(key)
, check if the key exists and is not expired:- If so, return the value.
- If expired, remove it and return -1.
- For
count()
, iterate through all keys and count those not expired, removing expired ones.
Code
|
|
|
|
Complexity
- ⏰ Time complexity: O(1) for set and get, O(n) for count (where n is the number of keys in the cache)
- 🧺 Space complexity: O(n)