Time To Live Key Data Structure
Design a data structure that stores key instances with a fixed time-to-live value. Each added key instance has a creation timestamp, and timestamps are monotonically increasing, meaning every new currentTimeStamp received by any method is greater than or equal to the previous timestamp received by the data structure.
A key instance added at timestamp createdTimeStamp is active while createdTimeStamp + ttl > currentTimeStamp. Once this condition is false, that key instance is expired and must not be counted.
The same key may be added multiple times. Each call to addKey creates one separate instance of that key. Counts are based on active key instances, not distinct key names.
Every method receives a currentTimeStamp. Before performing its main operation, the data structure must remove all expired key instances using that currentTimeStamp.
Class
TimeToLiveKeyStore
TimeToLiveKeyStore(int ttl)
- Initializes the data structure with a fixed TTL.
ttl is measured in the same unit as currentTimeStamp.
Methods
Add Key
void addKey(String key, int currentTimeStamp)
- Removes all expired key instances using
currentTimeStamp.
- Adds one new instance of
key at currentTimeStamp.
currentTimeStamp is always greater than or equal to the timestamp received in any earlier method call.
Count Active Key Instances
int countActive(String key, int currentTimeStamp)
- Removes all expired key instances using
currentTimeStamp.
- Returns the number of active instances of
key.
- The count is based on active key instances after expiration cleanup at the given
currentTimeStamp.
- If
key has no active instances, returns 0.
Count All Active Keys
int countAllActiveKeys(int currentTimeStamp)
- Removes all expired key instances using
currentTimeStamp.
- Returns the total number of active key instances across all keys.
- The count is based on active key instances after expiration cleanup at the given
currentTimeStamp.
- If there are no active key instances, returns
0.
Constraints
1 ≤ ttl ≤ 100,000,0001 ≤ key.length() ≤ 1000 ≤ currentTimeStamp ≤ 100,000,000currentTimeStamp values are monotonically increasing, non-decreasing across all method calls.key contains only lowercase English letters, uppercase English letters, and digits.
Examples
Example 1
TimeToLiveKeyStore store = new TimeToLiveKeyStore(ttl = 5)
store.addKey(key = "A", currentTimeStamp = 1)
store.addKey(key = "B", currentTimeStamp = 2)
store.countAllActiveKeys(currentTimeStamp = 2) returns 2.
store.countActive(key = "A", currentTimeStamp = 2) returns 1.
Both key instances are active at timestamp 2.
Example 2
TimeToLiveKeyStore store = new TimeToLiveKeyStore(ttl = 4)
store.addKey(key = "cat", currentTimeStamp = 10)
store.addKey(key = "cat", currentTimeStamp = 11)
store.countActive(key = "cat", currentTimeStamp = 11) returns 2.
store.countActive(key = "cat", currentTimeStamp = 14) returns 1.
store.addKey(key = "dog", currentTimeStamp = 14)
store.countAllActiveKeys(currentTimeStamp = 14) returns 2.
At timestamp 14, the "cat" instance from timestamp 10 has expired because 10 + 4 is not greater than 14. The "cat" instance from timestamp 11 and the "dog" instance from timestamp 14 are active.
Example 3
TimeToLiveKeyStore store = new TimeToLiveKeyStore(ttl = 3)
store.countAllActiveKeys(currentTimeStamp = 0) returns 0.
store.addKey(key = "x", currentTimeStamp = 5)
store.countActive(key = "x", currentTimeStamp = 7) returns 1.
store.countActive(key = "x", currentTimeStamp = 8) returns 0.
store.countAllActiveKeys(currentTimeStamp = 8) returns 0.
At timestamp 8, the "x" instance from timestamp 5 has expired because 5 + 3 is not greater than 8.
Expected Approach
Use a queue ordered by insertion time, where each entry stores createdTimeStamp and key. Also maintain a map from key to active instance count and one global active counter. Since timestamps are monotonically non-decreasing across all method calls, expired entries can be removed from the front of the queue before each operation while createdTimeStamp + ttl <= currentTimeStamp.