Expiring Cache
MediumCaching ยท TikTok
Implement ExpiringCache, a key-value cache holding at most capacity unexpired entries. Every call receives the current time t, which never decreases.
put(key, value, ttl, t)stores an entry that is unusable at any time>= t + ttl. Ifkeyalready has an unexpired entry, its value and expiry are replaced. The key becomes the most recently used.get(key, t)returns the value of an unexpired entry forkeyand marks it most recently used, or-1if there is none. It does not change the expiry.
A put for a key with no unexpired entry, while capacity unexpired entries exist, first removes the least recently used one.
Example 1
- Input:
- ExpiringCache(2), put(1, 10, 5, 0), put(2, 20, 50, 1), get(1, 3), put(3, 30, 10, 6), get(2, 7), get(1, 8), get(3, 9)
- Output:
- [null, null, null, 10, null, 20, -1, 30]
- Explanation
- Key
1expired at time 5, so the put at time 6 finds only key2and removes nothing, even though key2is the least recently used.
Example 2
- Input:
- ExpiringCache(1), put(7, 1, 4, 10), get(7, 13), get(7, 14)
- Output:
- [null, null, 1, -1]
Example 3
- Input:
- ExpiringCache(2), put(1, 1, 3, 0), put(2, 2, 20, 0), put(1, 5, 10, 2), put(3, 3, 5, 4), get(1, 5), get(2, 5), get(3, 5)
- Output:
- [null, null, null, null, null, 5, -1, 3]
Constraints
1 <= capacity <= 10000 <= key, value <= 10^91 <= ttl <= 10^90 <= t <= 10^9- At most
10^4calls are made