Skip to main content
Talentd

Design Authentication Manager - Solution & Explanation

MediumHash TableLinked ListDesignDoubly-Linked List18 min readAsked at: Amazon, Microsoft, Oracle +8
Practice this problem

Problem Statement

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 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.

Approach Overview

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 1: Using HashMap for Token Management

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.

  • generate: Simply add the token's expiration time to the map.
  • renew: Only renew if the token is unexpired by checking the current time against the stored expiration time.
  • countUnexpiredTokens: Iterate through the values of the map, counting tokens that have not yet expired. Clean up any expired tokens in the process.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Using Ordered Dictionary to Maintain Token Expiration Order

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.

  • generate: Insert token in the ordered dictionary with expiration time as the value.
  • renew: Remove the token if expired, otherwise update its expiration time.
  • countUnexpiredTokens: Traverse through tokens in order; stop counting when an expired token is encountered.

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.

Code

Python

Python

Complexity

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.

Try this approach in the editor →

Approach 3: Hash Table

We can simply maintain a hash table d, where the key is tokenId and the value is the expiration time.

  • During the generate operation, we store tokenId as the key and currentTime + timeToLive as the value in the hash table d.
  • During the 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.
  • During the 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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using HashMap for Token Management

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.

Using Ordered Dictionary to Maintain Token Expiration Order

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.

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap for Token ManagementO(1) generate/renew, O(n) countO(n)General implementation when token count is moderate and simplicity is preferred
Ordered Dictionary with Expiration OrderO(1) amortized operationsO(n)When frequent expiration cleanup is required and you want to avoid scanning all tokens

Video Solution

1797. Design Authentication Manager (Leetcode Medium) • Programming Live with Larry • 1,298 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Design Authentication Manager easy or hard?
Design Authentication Manager is considered a Medium difficulty problem. The logic is straightforward with a hash map, but handling renewals, expirations, and efficient counting requires careful reasoning about timestamps and data structure design.
Design Authentication Manager Python/Java solution
In Python, the solution typically uses a dictionary mapping tokenId to expiration timestamps. In Java, a HashMap<String, Integer> is commonly used. Both implementations perform constant-time insert, lookup, and update operations for generate and renew.
How to solve Design Authentication Manager in O(n)?
Store token IDs in a hash map with their expiration times. When generating a token, record currentTime + timeToLive. For renew, update the expiration only if the token has not expired. Counting valid tokens iterates through the map and counts entries with expiration greater than the current time, resulting in O(n) time.
What is the best approach for Design Authentication Manager?
The common solution uses a HashMap that maps tokenId to its expiration timestamp. Token generation and renewal are constant-time operations using hash lookups, while counting valid tokens scans the map. A more advanced design combines a hash map with an ordered structure such as a doubly linked list to remove expired tokens incrementally.
Is Design Authentication Manager asked at Google/Amazon/Meta?
Design-style problems involving token systems, caching, and expiration logic are common in interviews at companies like Amazon, Google, and Meta. This problem tests hash table usage and object-oriented design patterns similar to LRU cache implementations.
What data structure is used in Design Authentication Manager?
The primary data structure is a hash table mapping tokenId to expiration time. Some optimized solutions also use a doubly linked list or ordered dictionary to maintain tokens by expiration order for faster cleanup.
What is the time complexity of Design Authentication Manager?
With a HashMap implementation, generate and renew operations run in O(1) average time, while countUnexpiredTokens requires O(n) time to check all tokens. Space complexity is O(n) to store token IDs and expiration timestamps.

Ready to solve this problem?

Practice Design Authentication Manager with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters