We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design Authentication Manager

Difficulty: Medium

Problem Description

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.

Key Insights

  • Tokens are managed with unique identifiers and have a lifespan defined by timeToLive.
  • Renewing a token updates its expiry time based on the current time.
  • Expired tokens should not be counted or renewed.
  • The operations have to be efficient due to potentially high limits in calls and time values.

Space and Time Complexity

Time Complexity: O(1) for generate and countUnexpiredTokens, O(n) for renew (where n is the number of tokens if we need to check for expired tokens). Space Complexity: O(n) where n is the number of tokens stored in the system.

Solution

To solve this problem, we will use a hash table (dictionary) to store the tokens along with their expiry times. Each token's ID will map to its expiry time calculated as currentTime + timeToLive.

  1. Data Structure: A dictionary to hold token IDs as keys and their expiry times as values.
  2. Generate Method: Add a new token to the dictionary with its expiry time.
  3. Renew Method: Check if the token exists and is unexpired. If so, extend its expiry time. If it is expired, ignore the request.
  4. Count Method: Iterate through the tokens and count how many have not expired at the given currentTime.

Code Solutions

class AuthenticationManager:
    def __init__(self, timeToLive: int):
        self.timeToLive = timeToLive
        self.tokens = {}  # Dictionary to store tokenId and expiry time

    def generate(self, tokenId: str, currentTime: int) -> None:
        # Generate a new token with expiry time
        self.tokens[tokenId] = currentTime + self.timeToLive

    def renew(self, tokenId: str, currentTime: int) -> None:
        # Renew the token if it exists and is unexpired
        if tokenId in self.tokens and self.tokens[tokenId] > currentTime:
            self.tokens[tokenId] = currentTime + self.timeToLive

    def countUnexpiredTokens(self, currentTime: int) -> int:
        # Count unexpired tokens
        count = 0
        for expiry in list(self.tokens.values()):
            if expiry > currentTime:
                count += 1
            else:
                # Remove expired tokens
                self.tokens = {k: v for k, v in self.tokens.items() if v > currentTime}
        return count
← Back to All Questions