Design Authentication Manager
MedPrompt
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 theAuthenticationManagerand sets thetimeToLive.generate(string tokenId, int currentTime)generates a new token with the giventokenIdat the givencurrentTimein seconds.renew(string tokenId, int currentTime)renews the unexpired token with the giventokenIdat the givencurrentTimein seconds. If there are no unexpired tokens with the giventokenId, 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:
renew
Constraints:
1 <= timeToLive <= 1081 <= currentTime <= 1081 <= tokenId.length <= 5tokenIdconsists only of lowercase letters.- All calls to
generatewill contain unique values oftokenId. - The values of
currentTimeacross all the function calls will be strictly increasing. - At most
2000calls will be made to all functions combined.
Approaches
3 approaches with complexity analysis and trade-offs.
This is a straightforward approach using a single HashMap to store tokens and their expiry times. To count unexpired tokens, it iterates through all tokens ever stored in the map and checks if they are expired at the given time. No tokens are ever removed from the map, making it simple but inefficient in both time and space for the counting operation.
Algorithm
- Initialize a
HashMap<String, Integer>namedtokensto storetokenIdtoexpiryTimemappings, and store thetimeToLive. - For
generate(tokenId, currentTime):- Calculate the expiry time:
expiry = currentTime + timeToLive. - Add or update the token in the
tokensmap:tokens.put(tokenId, expiry).
- Calculate the expiry time:
- For
renew(tokenId, currentTime):- Check if the
tokenIdexists in thetokensmap. - If it exists, retrieve its current
expiryTime. - If
currentTime < expiryTime, the token is unexpired. Update its expiry time in the map tocurrentTime + timeToLive.
- Check if the
- For
countUnexpiredTokens(currentTime):- Initialize a counter
unexpiredCountto 0. - Iterate through all the values (expiry times) in the
tokensmap. - For each
expiryTime, ifexpiryTime > currentTime, incrementunexpiredCount. - Return
unexpiredCount.
- Initialize a counter
Walkthrough
In this approach, we use a HashMap<String, Integer> to map each tokenId to its calculated expiryTime. The timeToLive provided in the constructor is stored for these calculations.
-
generate(tokenId, currentTime): A new token is created by simply adding an entry to the map:(tokenId, currentTime + timeToLive). This is an O(1) operation. -
renew(tokenId, currentTime): We first look up the token in the map. If it exists and its current expiry time is greater thancurrentTime(meaning it's unexpired), we update its expiry time tocurrentTime + timeToLive. This is also an O(1) operation. -
countUnexpiredTokens(currentTime): This is the main performance bottleneck. The method iterates through every single entry in the map, checks if its expiry time is in the future relative tocurrentTime, and increments a counter. The map contains all tokens ever generated, so this scan becomes progressively slower as more tokens are created.
import java.util.HashMap;import java.util.Map; class AuthenticationManager { private int timeToLive; private Map<String, Integer> tokens; public AuthenticationManager(int timeToLive) { this.timeToLive = timeToLive; this.tokens = new HashMap<>(); } public void generate(String tokenId, int currentTime) { tokens.put(tokenId, currentTime + timeToLive); } public void renew(String tokenId, int currentTime) { if (tokens.containsKey(tokenId)) { if (tokens.get(tokenId) > currentTime) { tokens.put(tokenId, currentTime + timeToLive); } } } public int countUnexpiredTokens(int currentTime) { int unexpiredCount = 0; for (int expiryTime : tokens.values()) { if (expiryTime > currentTime) { unexpiredCount++; } } return unexpiredCount; }}Complexity
Time
`generate` and `renew` are O(1) on average. `countUnexpiredTokens` is O(N_total), where N_total is the total number of tokens ever generated.
Space
O(N_total), where N_total is the total number of unique tokens ever generated. The map grows indefinitely.
Trade-offs
Pros
Very simple to understand and implement.
The
generateandrenewoperations are very fast, with an average time complexity of O(1).
Cons
The
countUnexpiredTokensoperation is inefficient, with a time complexity of O(N), where N is the total number of tokens ever generated. This is because it iterates through all tokens, including those that have long expired.The space complexity is O(N), as the map stores all tokens ever created and never removes them. This can lead to high memory usage if many tokens are generated over time.
This approach improves upon the brute-force method by introducing a lazy eviction strategy. It still uses a single HashMap to store tokens, but it cleans up expired tokens whenever countUnexpiredTokens is called. This keeps the map size manageable and improves overall performance.
Algorithm
- Initialize a
HashMap<String, Integer>namedtokensand storetimeToLive. - For
generate(tokenId, currentTime):- Calculate
expiry = currentTime + timeToLive. - Put
(tokenId, expiry)into thetokensmap.
- Calculate
- For
renew(tokenId, currentTime):- Check if
tokenIdis intokens. - Get its
expiry. Ifexpiry > currentTime, update its expiry tocurrentTime + timeToLive.
- Check if
- For
countUnexpiredTokens(currentTime):- Iterate through the entries of the
tokensmap and remove all entries(tokenId, expiry)whereexpiry <= currentTime. A concise way is to useMap.entrySet().removeIf(). - After the cleanup, return the current size of the
tokensmap.
- Iterate through the entries of the
Walkthrough
This method uses a HashMap<String, Integer> to map each tokenId to its expiryTime. The key improvement is the lazy cleanup mechanism.
-
generateandrenew: These operations work similarly to the brute-force approach, taking O(1) average time. They add or update token expiry times in the map. -
countUnexpiredTokens(currentTime): This is where the optimization occurs. Before counting, we perform a cleanup pass. We iterate through all the entries in the map and remove any token whose expiry time is less than or equal to the givencurrentTime. Because the problem states thatcurrentTimeis strictly increasing, we know that any token removed will stay expired forever. After the cleanup, the number of unexpired tokens is simply the current size of the map. While a single call can take O(U) time (where U is the number of tokens before cleanup), each token is processed for removal at most once across all calls. This makes the amortized cost very efficient.
import java.util.HashMap;import java.util.Map; class AuthenticationManager { private int timeToLive; private Map<String, Integer> tokens; public AuthenticationManager(int timeToLive) { this.timeToLive = timeToLive; this.tokens = new HashMap<>(); } public void generate(String tokenId, int currentTime) { int expiryTime = currentTime + timeToLive; tokens.put(tokenId, expiryTime); } public void renew(String tokenId, int currentTime) { if (tokens.containsKey(tokenId)) { int expiryTime = tokens.get(tokenId); if (expiryTime > currentTime) { tokens.put(tokenId, currentTime + timeToLive); } } } public int countUnexpiredTokens(int currentTime) { // Using removeIf is a clean way to remove entries based on a condition. // It avoids ConcurrentModificationException. tokens.entrySet().removeIf(entry -> entry.getValue() <= currentTime); return tokens.size(); }}Complexity
Time
`generate` and `renew` are O(1) on average. `countUnexpiredTokens` is O(U) in the worst case, where U is the number of tokens in the map before cleanup. The amortized time complexity is efficient as each token is removed at most once.
Space
O(U), where U is the maximum number of unexpired tokens at any given time. This is much better than the brute-force approach.
Trade-offs
Pros
Simple to implement.
generateandrenewoperations are very fast (O(1) on average).Improves on the brute-force approach by cleaning up expired tokens, leading to better space complexity and better amortized time for counting.
Cons
A single call to
countUnexpiredTokenscan be slow (O(U) in the worst case, where U is the number of unexpired tokens) if no tokens are expired and the map is large.
This approach significantly optimizes the process of counting unexpired tokens by using two data structures: a HashMap for fast token lookups and a TreeMap to keep tokens sorted by their expiry time. This allows for a much faster cleanup process, as we can efficiently find and remove all expired tokens without scanning the unexpired ones.
Algorithm
- Initialize
timeToLive, aHashMap<String, Integer> tokenToExpiry, and aTreeMap<Integer, Set<String>> expiryToTokens. - For
generate(tokenId, currentTime):- Calculate
expiry = currentTime + timeToLive. - Put
(tokenId, expiry)intotokenToExpiry. - Add
tokenIdto the set associated withexpiryinexpiryToTokens. Create a new set if one doesn't exist.
- Calculate
- For
renew(tokenId, currentTime):- If
tokenIdis intokenToExpiryand is not expired (tokenToExpiry.get(tokenId) > currentTime):- Get
oldExpiry. RemovetokenIdfrom the set atexpiryToTokens.get(oldExpiry). If the set becomes empty, remove the keyoldExpiryfromexpiryToTokens. - Calculate
newExpiry = currentTime + timeToLive. - Update
tokenToExpirywith(tokenId, newExpiry). - Add
tokenIdto the set fornewExpiryinexpiryToTokens.
- Get
- If
- For
countUnexpiredTokens(currentTime):- Get an iterator for
expiryToTokens.entrySet(). - Iterate while the next entry's key (expiry time) is
<= currentTime:- For each
tokenIdin the entry's value set, remove it fromtokenToExpiry. - Remove the entry from
expiryToTokensusing the iterator.
- For each
- Since the
TreeMapis sorted, break the loop once an expiry time> currentTimeis found. - Return the size of the
tokenToExpirymap.
- Get an iterator for
Walkthrough
To achieve better performance, we maintain two data structures in sync:
HashMap<String, Integer> tokenToExpiry: Provides O(1) average time lookup of a token's expiry time, which is essential for therenewoperation.TreeMap<Integer, Set<String>> expiryToTokens: Maps anexpiryTimeto aSetoftokenIds that expire at that time. ATreeMapkeeps its keys (the expiry times) sorted, which is the core of this optimization.
-
generateandrenew: These operations now involve updating both data structures. An insertion or update in aTreeMaptakesO(log K)time, where K is the number of distinct expiry times. Forrenew, we must remove the token from its old expiry bucket in theTreeMapand add it to the new one. -
countUnexpiredTokens(currentTime): TheTreeMapmakes this operation highly efficient. Since expiry times are sorted, all expired tokens are located at the beginning of the map. We can iterate from the start and remove entries as long as theirexpiryTime <= currentTime. We stop as soon as we encounter the first unexpired entry, avoiding any work on the (potentially large) set of unexpired tokens. After this targeted cleanup, the count is simply the size of thetokenToExpirymap.
import java.util.HashMap;import java.util.HashSet;import java.util.Map;import java.util.Set;import java.util.TreeMap;import java.util.Iterator; class AuthenticationManager { private int timeToLive; private Map<String, Integer> tokenToExpiry; private TreeMap<Integer, Set<String>> expiryToTokens; public AuthenticationManager(int timeToLive) { this.timeToLive = timeToLive; this.tokenToExpiry = new HashMap<>(); this.expiryToTokens = new TreeMap<>(); } public void generate(String tokenId, int currentTime) { int expiryTime = currentTime + timeToLive; tokenToExpiry.put(tokenId, expiryTime); expiryToTokens.computeIfAbsent(expiryTime, k -> new HashSet<>()).add(tokenId); } public void renew(String tokenId, int currentTime) { Integer oldExpiryTime = tokenToExpiry.get(tokenId); if (oldExpiryTime != null && oldExpiryTime > currentTime) { // Remove from old expiry bucket in TreeMap Set<String> oldBucket = expiryToTokens.get(oldExpiryTime); oldBucket.remove(tokenId); if (oldBucket.isEmpty()) { expiryToTokens.remove(oldExpiryTime); } // Add to new expiry bucket int newExpiryTime = currentTime + timeToLive; tokenToExpiry.put(tokenId, newExpiryTime); // Update HashMap expiryToTokens.computeIfAbsent(newExpiryTime, k -> new HashSet<>()).add(tokenId); } } public int countUnexpiredTokens(int currentTime) { Iterator<Map.Entry<Integer, Set<String>>> it = expiryToTokens.entrySet().iterator(); while (it.hasNext()) { Map.Entry<Integer, Set<String>> entry = it.next(); if (entry.getKey() <= currentTime) { for (String tokenId : entry.getValue()) { tokenToExpiry.remove(tokenId); } it.remove(); // Safely remove from TreeMap while iterating } else { // Since TreeMap is sorted, we can stop early break; } } return tokenToExpiry.size(); }}Complexity
Time
`generate` and `renew` are O(log K), where K is the number of distinct expiry times. `countUnexpiredTokens` is O(E * log K + T_E), where E is the number of expired time buckets and T_E is the total number of tokens in those buckets. The amortized cost is excellent.
Space
O(U), where U is the maximum number of unexpired tokens. The space is used for both the `HashMap` and the `TreeMap`.
Trade-offs
Pros
countUnexpiredTokensis highly optimized. The cleanup process only inspects expired tokens and stops as soon as it finds the first unexpired one.Excellent overall time complexity, especially in scenarios with many
countoperations.
Cons
More complex to implement due to the need to keep two data structures synchronized.
generateandrenewoperations are slightly slower (O(log K)) compared to the O(1) of the simpler approaches.Higher constant factor in space usage due to two data structures and object overhead (e.g.,
Setobjects).
Solutions
Solution
class AuthenticationManager { private int t ; private Map < String , Integer > d = new HashMap <>(); public AuthenticationManager ( int timeToLive ) { t = timeToLive ; } public void generate ( String tokenId , int currentTime ) { d . put ( tokenId , currentTime + t ); } public void renew ( String tokenId , int currentTime ) { if ( d . getOrDefault ( tokenId , 0 ) <= currentTime ) { return ; } generate ( tokenId , currentTime ); } public int countUnexpiredTokens ( int currentTime ) { int ans = 0 ; for ( int exp : d . values ()) { if ( exp > currentTime ) { ++ ans ; } } return ans ; } } /** * Your AuthenticationManager object will be instantiated and called as such: * AuthenticationManager obj = new AuthenticationManager(timeToLive); * obj.generate(tokenId,currentTime); * obj.renew(tokenId,currentTime); * int param_3 = obj.countUnexpiredTokens(currentTime); */class AuthenticationManager { public: AuthenticationManager ( int timeToLive ) { t = timeToLive ; } void generate ( string tokenId , int currentTime ) { d [ tokenId ] = currentTime + t ; } void renew ( string tokenId , int currentTime ) { if ( d [ tokenId ] <= currentTime ) return ; generate ( tokenId , currentTime ); } int countUnexpiredTokens ( int currentTime ) { int ans = 0 ; for ( auto & [ _ , v ] : d ) ans += v > currentTime ; return ans ; } private: int t ; unordered_map < string , int > d ; }; /** * Your AuthenticationManager object will be instantiated and called as such: * AuthenticationManager* obj = new AuthenticationManager(timeToLive); * obj->generate(tokenId,currentTime); * obj->renew(tokenId,currentTime); * int param_3 = obj->countUnexpiredTokens(currentTime); */class AuthenticationManager : def __init__ ( self , timeToLive : int ): self . t = timeToLive self . d = defaultdict ( int ) def generate ( self , tokenId : str , currentTime : int ) -> None : self . d [ tokenId ] = currentTime + self . t def renew ( self , tokenId : str , currentTime : int ) -> None : if self . d [ tokenId ] <= currentTime : return self . d [ tokenId ] = currentTime + self . t def countUnexpiredTokens ( self , currentTime : int ) -> int : return sum ( exp > currentTime for exp in self . d . values ()) # Your AuthenticationManager object will be instantiated and called as such: # obj = AuthenticationManager(timeToLive) # obj.generate(tokenId,currentTime) # obj.renew(tokenId,currentTime) # param_3 = obj.countUnexpiredTokens(currentTime)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.