There is an authentication system that works with authentication tokens. For each session, the user will receive a new authentication token that will expire timeToLive seconds after the currentTime. If the token is renewed, the expiry time will be extended to expire timeToLive seconds after the (potentially different) currentTime.
Implement the AuthenticationManager class:
AuthenticationManager(int timeToLive) constructs the AuthenticationManager and sets the timeToLive.generate(string tokenId, int currentTime) generates a new token with the given tokenId at the given currentTime in seconds.renew(string tokenId, int currentTime) renews the unexpired token with the given tokenId at the given currentTime in seconds. If there are no unexpired tokens with the given tokenId, the request is ignored, and nothing happens.countUnexpiredTokens(int currentTime) returns the number of unexpired tokens at the given currentTime.Note that if a token expires at time t, and another action happens on time t (renew or countUnexpiredTokens), the expiration takes place before the other actions.
Example 1:
Input ["AuthenticationManager", "renew", "generate", "countUnexpiredTokens", "generate", "renew", "renew", "countUnexpiredTokens"] [[5], ["aaa", 1], ["aaa", 2], [6], ["bbb", 7], ["aaa", 8], ["bbb", 10], [15]] Output [null, null, null, 1, null, null, null, 0] Explanation AuthenticationManager authenticationManager = new AuthenticationManager(5); // Constructs the AuthenticationManager withtimeToLive= 5 seconds. authenticationManager.renew("aaa", 1); // No token exists with tokenId "aaa" at time 1, so nothing happens. authenticationManager.generate("aaa", 2); // Generates a new token with tokenId "aaa" at time 2. authenticationManager.countUnexpiredTokens(6); // The token with tokenId "aaa" is the only unexpired one at time 6, so return 1. authenticationManager.generate("bbb", 7); // Generates a new token with tokenId "bbb" at time 7. authenticationManager.renew("aaa", 8); // The token with tokenId "aaa" expired at time 7, and 8 >= 7, so at time 8 therenewrequest is ignored, and nothing happens. authenticationManager.renew("bbb", 10); // The token with tokenId "bbb" is unexpired at time 10, so therenewrequest is fulfilled and now the token will expire at time 15. authenticationManager.countUnexpiredTokens(15); // The token with tokenId "bbb" expires at time 15, and the token with tokenId "aaa" expired at time 7, so currently no token is unexpired, so return 0.
Constraints:
1 <= timeToLive <= 1081 <= currentTime <= 1081 <= tokenId.length <= 5tokenId consists only of lowercase letters.generate will contain unique values of tokenId.currentTime across all the function calls will be strictly increasing.2000 calls will be made to all functions combined.Problem Overview: Design an authentication system that issues tokens with a fixed timeToLive. Each token can be generated, renewed before expiration, and counted if still valid at a given time. The system must support efficient lookup and expiration handling across multiple operations.
Approach 1: Using HashMap for Token Management (O(1) average time)
Store each tokenId in a hash map with its expiration timestamp. When generate is called, insert tokenId → currentTime + timeToLive. For renew, first check if the token exists and whether its expiration is greater than the current time; if valid, update the expiration timestamp. For countUnexpiredTokens, iterate through the map and count entries whose expiration time is still greater than currentTime. Hash lookup and updates run in O(1) average time using a hash table, though counting requires scanning all stored tokens. Space complexity is O(n) where n is the number of active tokens ever created.
Approach 2: Ordered Dictionary to Maintain Token Expiration Order (O(n) cleanup, O(1) amortized ops)
Maintain tokens in insertion or expiration order using an ordered dictionary or a structure backed by a doubly-linked list. Each node stores tokenId and expiration time, while a hash map points to nodes for constant-time access. When a token expires, remove it from the front of the structure since expirations occur in chronological order. Renewing a token removes its node and reinserts it with an updated expiration timestamp. This approach reduces repeated scanning during countUnexpiredTokens because expired tokens are cleaned up incrementally. Time complexity for updates remains O(1) amortized, and space complexity is O(n).
Recommended for interviews: Start with the HashMap approach since it directly models the problem and shows you understand token validation with constant-time lookups. Interviewers often accept this design because operations like generate and renew remain efficient. The ordered structure variant demonstrates stronger system design thinking by handling expiration cleanup proactively and combining a hash map with a linked structure, a common pattern in design problems such as LRU caches.
In this approach, we utilize a hash map (or dictionary) to store each token's expiration time. This allows for efficient lookups, renewals, and expirations.
The C solution uses a simple hash map approach, where tokens are stored in a linked list to handle collisions. Each node in the linked list stores a token with its expiration time. When generating or renewing tokens, it calculates the expiration time based on the given current time.
The time complexity of each operation (generate, renew, and countUnexpiredTokens) is approximately O(1) on average, given a good hash function. The space complexity is O(n), where n is the number of tokens generated.
In this second approach, we introduce an ordered dictionary to help maintain the order of token expirations, which can make count operations more efficient by stopping early when no more unexpired tokens are found.
Python's OrderedDict maintains the order of insertion, providing ordered iteration that helps manage token expiration. When counting unexpired tokens, we can efficiently remove expired tokens by iterating in order of expiration.
Python
The time complexities for generate and renew remain O(1) on average with ordered dictionary. The count_unexpired_tokens generally performs better than unordered approaches, as early stopping can reduce average time complexity.
We can simply maintain a hash table d, where the key is tokenId and the value is the expiration time.
generate operation, we store tokenId as the key and currentTime + timeToLive as the value in the hash table d.renew operation, if tokenId is not in the hash table d, or currentTime >= d[tokenId], we ignore this operation; otherwise, we update d[tokenId] to currentTime + timeToLive.countUnexpiredTokens operation, we traverse the hash table d and count the number of unexpired tokenId.In terms of time complexity, both generate and renew operations have a time complexity of O(1), and the countUnexpiredTokens operation has a time complexity of O(n), where n is the number of key-value pairs in the hash table d.
The space complexity is O(n), where n is the number of key-value pairs in the hash table d.
| Approach | Complexity |
|---|---|
| Using HashMap for Token Management | The time complexity of each operation ( |
| Using Ordered Dictionary to Maintain Token Expiration Order | The time complexities for |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap for Token Management | O(1) generate/renew, O(n) count | O(n) | General implementation when token count is moderate and simplicity is preferred |
| Ordered Dictionary with Expiration Order | O(1) amortized operations | O(n) | When frequent expiration cleanup is required and you want to avoid scanning all tokens |
1797. Design Authentication Manager (Leetcode Medium) • Programming Live with Larry • 1,230 views views
Watch 4 more video solutions →Practice Design Authentication Manager with our built-in code editor and test cases.
Practice on FleetCode