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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Design Authentication Manager

Number: 1905

Difficulty: Medium

Paid? No

Companies: Oracle, Confluent, Docusign, LinkedIn, X

Problem Description

Implement an AuthenticationManager that supports generating tokens with an expiration time, renewing tokens if they are still unexpired, and counting unexpired tokens at any given time. Each token is set to expire after a fixed timeToLive period, and renewed tokens receive an updated expiration time. Actions on the same timestamp as a token’s expiry will see the token as already expired.

Key Insights

  • Use a hash table (dictionary) to store token IDs with their corresponding expiration times.
  • Since currentTime values are strictly increasing, we can safely check and remove expired tokens during the count operation without worrying about out-of-order timestamps.
  • Renewal only occurs if the token hasn’t already expired.
  • Even though a more efficient strategy using a priority queue (or sorted list) could be used for larger input sizes, given the maximum of 2000 calls the simpler approach is acceptable in terms of performance.

Space and Time Complexity

Time Complexity:

  • generate: O(1)
  • renew: O(1)
  • countUnexpiredTokens: O(n) in worst-case where n is the number of tokens (since it may iterate over all tokens)

Space Complexity:

  • O(n), where n is the number of tokens stored at any time.

Solution

We choose a dictionary (hash table) to map token Ids to their expiration times.

  • For generate, insert a new entry with tokenId and expiration = currentTime + timeToLive.
  • For renew, check if tokenId exists and its expiration time is greater than currentTime. If yes, update expiration; otherwise, do nothing.
  • For countUnexpiredTokens, iterate over the dictionary and count tokens where the stored expiration time is greater than currentTime. Optionally, remove expired tokens to keep the dictionary clean.

This approach leverages the strictly increasing nature of currentTime to ensure expired tokens can be safely pruned when queried.

Code Solutions

# Python solution for AuthenticationManager

class AuthenticationManager:
    def __init__(self, timeToLive: int):
        # Initialize the manager with a given timeToLive
        self.timeToLive = timeToLive
        # Dictionary to store token and its expiration time
        self.tokenExpirations = {}

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

    def renew(self, tokenId: str, currentTime: int) -> None:
        # Renew token only if it exists and has not expired
        if tokenId in self.tokenExpirations and self.tokenExpirations[tokenId] > currentTime:
            self.tokenExpirations[tokenId] = currentTime + self.timeToLive

    def countUnexpiredTokens(self, currentTime: int) -> int:
        # Count tokens that are still unexpired at currentTime
        count = 0
        # Optional: Clean up expired tokens
        expired_tokens = []
        for tokenId, expiry in self.tokenExpirations.items():
            if expiry > currentTime:
                count += 1
            else:
                expired_tokens.append(tokenId)
        # Remove expired tokens from the dictionary
        for token in expired_tokens:
            del self.tokenExpirations[token]
        return count

# Example usage:
# mgr = AuthenticationManager(5)
# mgr.generate("aaa", 2)
# print(mgr.countUnexpiredTokens(6))
← Back to All Questions