Design Authentication Manager

Implement an AuthenticationManager using linked-list pointer manipulation and a hash map to track token expirations efficiently.

hash table linked list design doubly linked list

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

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

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.

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.

terminal

Solution

Solution 1: Hash Table

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

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)

Continue Practicing

#1472 design browser history #460 lfu cache #432 all oone data structure