You are given a token lifetime timeToLive and a sequence of queries to simulate a token manager. A token generated or renewed at time t expires at t + timeToLive, and it is considered unexpired only while expirationTime > currentTime. Support generate, renew, and count operations efficiently. For this problem, assume generate overwrites any existing token with the same tokenId.
Examples
Input: (5, [('generate', 'aaa', 1), ('renew', 'aaa', 2), ('count', 6), ('count', 7)])
Expected Output:
Explanation: The token is first set to expire at 6, then renewed to expire at 7. It is alive at time 6, but not at time 7.
Input: (1, [('generate', 'a', 1), ('generate', 'b', 1), ('count', 1), ('count', 2)])
Expected Output:
Explanation: Both tokens expire at time 2. They count as unexpired at time 1 but not at time 2.
Input: (4, [('generate', 'x', 1), ('count', 4), ('renew', 'x', 5), ('count', 5)])
Expected Output:
Explanation: The token expires at time 5. Renewing at time 5 does nothing because it is already expired at that moment.
Input: (3, [('generate', 'a', 1), ('generate', 'a', 2), ('count', 3), ('count', 4), ('count', 5)])
Expected Output:
Explanation: The second generate overwrites the first expiration, so the token survives through time 4 and expires at time 5.
Input: (10, [])
Expected Output:
Explanation: With no queries, there are no count results.
Solution
def solution(timeToLive, queries):
import heapq
expirations = {}
heap = []
result = []
def cleanup(currentTime):
while heap and heap[0][0] <= currentTime:
expiry, tokenId = heapq.heappop(heap)
if expirations.get(tokenId) == expiry:
del expirations[tokenId]
for query in queries:
op = query[0]
if op == 'count':
currentTime = query[1]
cleanup(currentTime)
result.append(len(expirations))
elif op == 'generate':
tokenId, currentTime = query[1], query[2]
cleanup(currentTime)
expiry = currentTime + timeToLive
expirations[tokenId] = expiry
heapq.heappush(heap, (expiry, tokenId))
elif op == 'renew':
tokenId, currentTime = query[1], query[2]
cleanup(currentTime)
if tokenId in expirations:
expiry = currentTime + timeToLive
expirations[tokenId] = expiry
heapq.heappush(heap, (expiry, tokenId))
else:
raise ValueError('Unknown operation: {}'.format(op))
return resultTime complexity: O(q log q). Space complexity: O(q).