Watch 5 video solutions for Design Authentication Manager, a medium level problem involving Hash Table, Linked List, Design. This walkthrough by Programming Live with Larry has 1,230 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |