How to Solve Design Authentication Manager

To solve this problem, maintain a hash map mapping tokenIds to their expiry times and a doubly-linked list to handle ordered expirations. Renewals and counts require careful pointer updates to ensure expired tokens are removed correctly. This approach avoids linear scans and supports fast generate, renew, and countUnexpiredTokens operations.

Problem Statement

You are asked to implement an authentication system that manages session tokens. Each token expires a fixed number of seconds after creation, defined by timeToLive, and can be renewed before expiration. The system should support generating new tokens, renewing existing tokens, and counting currently unexpired tokens, all while ensuring that expiration happens before any other operations at the same time.

Implement the AuthenticationManager class with these behaviors: generate(tokenId, currentTime) creates a new token; renew(tokenId, currentTime) extends a token's expiry if it is unexpired; countUnexpiredTokens(currentTime) returns the number of tokens that have not yet expired. Token IDs are unique and time values increase strictly across function calls.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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.

Solution Approach

Use a Hash Map for Token Lookup

Maintain a hash map mapping tokenId to its node in a doubly-linked list. This allows O(1) access for renew and checking expiration, linking the problem directly to hash table usage combined with linked-list pointer manipulation.

Maintain a Doubly-Linked List for Ordered Expiry

Store tokens in a doubly-linked list ordered by expiry time. Removing expired tokens is efficient because expired nodes are always at the head, aligning with the pointer manipulation pattern and preventing unnecessary linear scans during count operations.

Update Pointers Carefully on Renewals

When renewing a token, remove its node and append it at the new expiry position. Precise pointer updates prevent stale tokens from remaining in the list, a common failure mode when naive map-only solutions are used.

Complexity Analysis

Time complexity depends on how efficiently expired tokens are removed during generate, renew, and count operations, typically O(1) for hash map access and O(1) pointer updates in a doubly-linked list. Space complexity is O(n), proportional to the number of active tokens stored in the map and linked list.

What Interviewers Usually Probe

• Are you tracking expiry times efficiently for all operations?
• Can you remove expired tokens without scanning the entire data structure?
• How does your pointer manipulation prevent stale token counts?

Common Pitfalls or Variants

Common pitfalls

• Failing to remove expired tokens before renew or count operations, leading to incorrect results.
• Using only a hash map without ordering by expiry, resulting in inefficient countUnexpiredTokens operations.
• Incorrectly updating linked-list pointers during renew, leaving dangling nodes and inaccurate token state.

Follow-up variants

• Change the system to allow multiple tokens per user, requiring additional mapping from userId to token nodes.
• Implement the system using a min-heap instead of a linked list for ordered expiration.
• Support bulk renewal of all tokens before a given currentTime, requiring batch pointer updates.

How GhostInterview Helps

• Provides step-by-step guidance for maintaining the hash map and doubly-linked list together without missing pointer updates.
• Explains how to detect and remove expired tokens correctly before other operations to avoid failure modes.
• Offers code-level reasoning for generate, renew, and countUnexpiredTokens operations to ensure accurate and efficient implementation.

Topic Pages

• Hash Table
• Linked List
• Design
• Doubly-Linked List

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main data structure pattern for Design Authentication Manager?

The key pattern is linked-list pointer manipulation combined with a hash map to track token expiry efficiently.

How do I handle token renewals at the exact expiry time?

Always check and remove expired tokens before applying renew; if currentTime >= expiryTime, the token cannot be renewed.

Why use a doubly-linked list instead of a simple array?

A doubly-linked list allows O(1) removal and insertion at arbitrary positions, crucial for maintaining token order without scanning all elements.

What is the time complexity for countUnexpiredTokens?

With a hash map and ordered linked list, counting unexpired tokens is efficient, typically O(1) for removing expired tokens and O(1) per operation.

Can I use only a hash map for this problem?

Using only a hash map may lead to inefficient count operations because it cannot quickly determine which tokens have expired without scanning all entries.