Design Authentication Manager #7 Most Asked

Medium

1 view

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 <= 10⁸
1 <= currentTime <= 10⁸
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.

Try coding it in LeetCode

Design Authentication Manager #7 Most Asked

Medium

Confluent

1 view

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 <= 10⁸
1 <= currentTime <= 10⁸
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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on `tokenId`? Can it be an empty string or null? What is the maximum length?
What is the expected range for `currentTime` and `timeToLive`? Can `currentTime` ever be smaller than the creation time of a token, or negative?
What should happen if I try to generate a token with a `tokenId` that already exists? Should I overwrite the old token, throw an error, or return without creating a new token?
If I call `renew` on a `tokenId` that doesn't exist, what should happen? Should I throw an error, or simply do nothing?
What should the `countUnexpiredTokens` method return if there are no unexpired tokens at the given `currentTime`?

Brute Force Solution

Approach

The brute force method for managing authentication is like trying every single possible login and logout action to see if they are valid. It means we meticulously check each scenario without being smart or efficient. We're just checking everything.

Here's how the algorithm would work step-by-step:

Whenever a new authentication token is requested, create it and store it along with its expiration time.
When an existing token needs to be refreshed, first go through every stored token to see if it exists.
If the token exists and isn't expired, update the expiration time of this token.
When asked to count the number of unexpired tokens, go through every single stored token and check if it's still valid (not expired).
Keep a running count of all the valid tokens.
The expiration check in all these steps involves comparing the token's expiration time against the current time.

Code Implementation

class AuthenticationManager:

    def __init__(self, time_to_live: int):
        self.time_to_live = time_to_live
        self.token_expiration = {}

    def generate(self, token_id: str, current_time: int) -> None:
        # Store the token's expiration time.
        self.token_expiration[token_id] = current_time + self.time_to_live

    def renew(self, token_id: str, current_time: int) -> None:
        if token_id in self.token_expiration:
            if self.token_expiration[token_id] > current_time:
                # Update the expiration time.
                self.token_expiration[token_id] = current_time + self.time_to_live

    def countUnexpiredTokens(self, current_time: int) -> int:
        unexpired_token_count = 0

        # Iterate through all tokens to check if they're still valid.
        for token_id, expiration_time in self.token_expiration.items():
            # Increment counter if not expired.
            if expiration_time > current_time:
                unexpired_token_count += 1

        return unexpired_token_count

Big(O) Analysis

Time Complexity

O(n) – The AuthenticationManager stores tokens in a single data structure such as a list. Creating a token takes constant time, O(1). Renewing a token requires iterating through all n tokens in the worst case to find the matching tokenId and update its time, thus taking O(n) time. Counting unexpired tokens also requires iterating through all n tokens once to check each token's expiration, resulting in O(n) complexity. Therefore, the renew and countUnexpiredTokens methods drive the overall complexity. The most expensive operation is iterating through the tokens list, so the overall runtime complexity is O(n).

Space Complexity

O(N) – The brute force method involves storing all authentication tokens along with their expiration times. The number of tokens stored grows linearly with the number of authentication requests. Therefore, the auxiliary space required to store these tokens is proportional to N, where N is the total number of authentication tokens issued.

Optimal Solution

Approach

We need to manage authentication tokens efficiently, keeping track of when they expire. The best way to do this is to use a system that automatically cleans up old, expired tokens so we don't waste memory or processing power checking tokens that are no longer valid.

Here's how the algorithm would work step-by-step:

When a new authentication token is created, store it along with its expiration time.
When someone tries to use a token to access something, first check if the token exists.
If the token exists, check if it has expired by comparing its expiration time to the current time.
If the token has not expired, it's valid, so allow access and maybe update the token's expiration time if needed.
If the token doesn't exist or has expired, deny access.
Periodically, clean up the stored tokens by removing all the tokens that have already expired. This prevents old tokens from cluttering the system.

Code Implementation

import time

class AuthenticationManager:

    def __init__(self, time_to_live):
        self.time_to_live = time_to_live
        self.token_map = {}

    def generate(self, token_id, current_time):
        expiration_time = current_time + self.time_to_live
        self.token_map[token_id] = expiration_time

    def renew(self, token_id, current_time):
        # Check if the token exists and is not expired.
        if token_id in self.token_map:
            expiration_time = self.token_map[token_id]

            if expiration_time > current_time:
                self.token_map[token_id] = current_time + self.time_to_live

    def countUnexpiredTokens(self, current_time):
        unexpired_count = 0

        # Iterate through the tokens and count unexpired ones.
        for token_id, expiration_time in self.token_map.items():
            if expiration_time > current_time:
                unexpired_count += 1

        return unexpired_count

    def cleanupExpiredTokens(self, current_time):
        # Remove expired tokens from the token map.
        tokens_to_remove = []
        for token_id, expiration_time in self.token_map.items():
            if expiration_time <= current_time:
                tokens_to_remove.append(token_id)

        for token_id in tokens_to_remove:
            del self.token_map[token_id]

Big(O) Analysis

Time Complexity

O(n) – The creation of a token involves storing the token and its expiration time, taking O(1) time. Checking if a token exists involves a lookup in a hash map which takes O(1) time on average. Updating a token's expiration also involves a hash map update, taking O(1) time. The periodic cleanup iterates through all stored tokens, which can be 'n' in the worst case, where 'n' is the number of stored tokens. Therefore, the cleanup operation dominates with a time complexity of O(n). Overall, since the check operation is called frequently and clean up less so, it averages out to O(1) in practical usage but the cleanup itself is O(n). The worst case runtime for the clean up drives overall Big O complexity when accounting for long periods of usage.

Space Complexity

O(N) – The primary space complexity comes from storing the authentication tokens along with their expiration times. We can assume the number of tokens stored at any given time can grow linearly with the number of requests or users, which we can define as N. Therefore, the auxiliary space used to store these tokens and their corresponding expiration times is proportional to N. This leads to a space complexity of O(N).

Edge Cases

Case	How to Handle
timeToLive is zero or negative	Treating timeToLive as zero means tokens expire immediately; negative TTL is invalid and should be handled via exception or defaulting to a positive value.
currentTime is negative	Negative currentTime values may indicate an issue with the system's time and should be handled with a boundary check by either throwing an error or defaulting to a non-negative value.
tokenId is an empty string	An empty tokenId should either be considered an invalid input (throw exception) or be treated as a valid, distinct tokenId which could lead to unexpected behavior if not properly considered.
Concurrent create/renew/count calls from multiple threads	Use appropriate synchronization mechanisms (e.g., locks) to ensure thread safety and prevent race conditions in the internal data structure managing the tokens.
Large number of tokens causing memory issues	Choose a data structure that scales efficiently and consider implementing a mechanism to prune or expire tokens based on some eviction policy (LRU, LFU) if the number of tokens grows unboundedly.
Renewing a non-existent tokenId	Renewing a non-existent tokenId should either be a no-op (do nothing) or throw an exception indicating the token does not exist.
Count unexpired tokens called at a time very far in the future	Ensure the implementation can handle large currentTime values without integer overflows and efficiently iterates through the valid tokens.
Integer overflow when calculating expiration time	Prevent integer overflows by using appropriate data types (e.g., long) or checking for potential overflows before performing calculations related to token expiration times.

timeToLive is zero or negative

How to Handle:

Treating timeToLive as zero means tokens expire immediately; negative TTL is invalid and should be handled via exception or defaulting to a positive value.

currentTime is negative

How to Handle:

Negative currentTime values may indicate an issue with the system's time and should be handled with a boundary check by either throwing an error or defaulting to a non-negative value.

tokenId is an empty string

How to Handle:

An empty tokenId should either be considered an invalid input (throw exception) or be treated as a valid, distinct tokenId which could lead to unexpected behavior if not properly considered.

Concurrent create/renew/count calls from multiple threads

How to Handle:

Use appropriate synchronization mechanisms (e.g., locks) to ensure thread safety and prevent race conditions in the internal data structure managing the tokens.

Large number of tokens causing memory issues

How to Handle:

Choose a data structure that scales efficiently and consider implementing a mechanism to prune or expire tokens based on some eviction policy (LRU, LFU) if the number of tokens grows unboundedly.

Renewing a non-existent tokenId

How to Handle:

Renewing a non-existent tokenId should either be a no-op (do nothing) or throw an exception indicating the token does not exist.

Count unexpired tokens called at a time very far in the future

How to Handle:

Ensure the implementation can handle large currentTime values without integer overflows and efficiently iterates through the valid tokens.

Integer overflow when calculating expiration time

How to Handle:

Prevent integer overflows by using appropriate data types (e.g., long) or checking for potential overflows before performing calculations related to token expiration times.