# Design Authentication Manager **Difficulty:** MEDIUM [External](https://leetcode.com/problems/design-authentication-manager) Canonical: https://scaleengineer.com/dsa/problems/design-authentication-manager **Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design) **Data structures:** Hash Table, Linked List, Doubly-Linked List **Companies:** [Docusign](https://scaleengineer.com/companies/docusign), [Confluent](https://scaleengineer.com/companies/confluent), [X](https://scaleengineer.com/companies/x), [Genpact](https://scaleengineer.com/companies/genpact) --- ## Problem 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:** ![](https://assets.glich.co/dsa/design-authentication-manager/image0.png) **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 with `timeToLive` = 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 the `renew` request is ignored, and nothing happens. authenticationManager.`renew`("bbb", 10); // The token with tokenId "bbb" is unexpired at time 10, so the `renew` request 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 <= 108` * `1 <= currentTime <= 108` * `1 <= tokenId.length <= 5` * `tokenId` consists only of lowercase letters. * All calls to `generate` will contain unique values of `tokenId`. * The values of `currentTime` across all the function calls will be **strictly increasing**. * At most `2000` calls will be made to all functions combined. # Approaches ## Brute-force with HashMap 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. **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. **Pros:** Very simple to understand and implement.; The `generate` and `renew` operations are very fast, with an average time complexity of O(1). **Cons:** The `countUnexpiredTokens` operation 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. ### Explanation In this approach, we use a `HashMap` 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 than `currentTime` (meaning it's unexpired), we update its expiry time to `currentTime + 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 to `currentTime`, and increments a counter. The map contains all tokens ever generated, so this scan becomes progressively slower as more tokens are created. ```java import java.util.HashMap; import java.util.Map; class AuthenticationManager { private int timeToLive; private Map 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; } } ``` ### Algorithm - Initialize a `HashMap` named `tokens` to store `tokenId` to `expiryTime` mappings, and store the `timeToLive`. - **For `generate(tokenId, currentTime)`:** - Calculate the expiry time: `expiry = currentTime + timeToLive`. - Add or update the token in the `tokens` map: `tokens.put(tokenId, expiry)`. - **For `renew(tokenId, currentTime)`:** - Check if the `tokenId` exists in the `tokens` map. - If it exists, retrieve its current `expiryTime`. - If `currentTime < expiryTime`, the token is unexpired. Update its expiry time in the map to `currentTime + timeToLive`. - **For `countUnexpiredTokens(currentTime)`:** - Initialize a counter `unexpiredCount` to 0. - Iterate through all the values (expiry times) in the `tokens` map. - For each `expiryTime`, if `expiryTime > currentTime`, increment `unexpiredCount`. - Return `unexpiredCount`. ## HashMap with Lazy Eviction 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. **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. **Pros:** Simple to implement.; `generate` and `renew` operations 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 `countUnexpiredTokens` can 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. ### Explanation This method uses a `HashMap` to map each `tokenId` to its `expiryTime`. The key improvement is the lazy cleanup mechanism. - **`generate` and `renew`**: 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 given `currentTime`. Because the problem states that `currentTime` is 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. ```java import java.util.HashMap; import java.util.Map; class AuthenticationManager { private int timeToLive; private Map 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(); } } ``` ### Algorithm - Initialize a `HashMap` named `tokens` and store `timeToLive`. - **For `generate(tokenId, currentTime)`:** - Calculate `expiry = currentTime + timeToLive`. - Put `(tokenId, expiry)` into the `tokens` map. - **For `renew(tokenId, currentTime)`:** - Check if `tokenId` is in `tokens`. - Get its `expiry`. If `expiry > currentTime`, update its expiry to `currentTime + timeToLive`. - **For `countUnexpiredTokens(currentTime)`:** - Iterate through the entries of the `tokens` map and remove all entries `(tokenId, expiry)` where `expiry <= currentTime`. A concise way is to use `Map.entrySet().removeIf()`. - After the cleanup, return the current size of the `tokens` map. ## Optimized with HashMap and TreeMap 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. **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`. **Pros:** `countUnexpiredTokens` is 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 `count` operations. **Cons:** More complex to implement due to the need to keep two data structures synchronized.; `generate` and `renew` operations 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., `Set` objects). ### Explanation To achieve better performance, we maintain two data structures in sync: 1. `HashMap tokenToExpiry`: Provides O(1) average time lookup of a token's expiry time, which is essential for the `renew` operation. 2. `TreeMap> expiryToTokens`: Maps an `expiryTime` to a `Set` of `tokenId`s that expire at that time. A `TreeMap` keeps its keys (the expiry times) sorted, which is the core of this optimization. - **`generate` and `renew`**: These operations now involve updating both data structures. An insertion or update in a `TreeMap` takes `O(log K)` time, where K is the number of distinct expiry times. For `renew`, we must remove the token from its old expiry bucket in the `TreeMap` and add it to the new one. - **`countUnexpiredTokens(currentTime)`**: The `TreeMap` makes 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 their `expiryTime <= 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 the `tokenToExpiry` map. ```java 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 tokenToExpiry; private TreeMap> 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 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>> it = expiryToTokens.entrySet().iterator(); while (it.hasNext()) { Map.Entry> 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(); } } ``` ### Algorithm - Initialize `timeToLive`, a `HashMap tokenToExpiry`, and a `TreeMap> expiryToTokens`. - **For `generate(tokenId, currentTime)`:** - Calculate `expiry = currentTime + timeToLive`. - Put `(tokenId, expiry)` into `tokenToExpiry`. - Add `tokenId` to the set associated with `expiry` in `expiryToTokens`. Create a new set if one doesn't exist. - **For `renew(tokenId, currentTime)`:** - If `tokenId` is in `tokenToExpiry` and is not expired (`tokenToExpiry.get(tokenId) > currentTime`): - Get `oldExpiry`. Remove `tokenId` from the set at `expiryToTokens.get(oldExpiry)`. If the set becomes empty, remove the key `oldExpiry` from `expiryToTokens`. - Calculate `newExpiry = currentTime + timeToLive`. - Update `tokenToExpiry` with `(tokenId, newExpiry)`. - Add `tokenId` to the set for `newExpiry` in `expiryToTokens`. - **For `countUnexpiredTokens(currentTime)`:** - Get an iterator for `expiryToTokens.entrySet()`. - Iterate while the next entry's key (expiry time) is `<= currentTime`: - For each `tokenId` in the entry's value set, remove it from `tokenToExpiry`. - Remove the entry from `expiryToTokens` using the iterator. - Since the `TreeMap` is sorted, break the loop once an expiry time `> currentTime` is found. - Return the size of the `tokenToExpiry` map. # Solutions ### Java ```java 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); */ ``` ### CPP ```cpp 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); */ ``` ### Python ```python 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) ```