Problem Description

You need to build an authentication system that manages tokens with expiration times. Each token has a unique ID and expires after a certain time period.

The system should support the following operations:

1. Initialize the system with a timeToLive parameter that determines how long tokens remain valid (in seconds).

2. Generate a new token with a given tokenId at a specific currentTime. The token will expire at currentTime + timeToLive.

3. Renew an existing token with a given tokenId at a specific currentTime. This operation:

   • Only works if the token exists and hasn't expired yet (token is unexpired if its expiration time is strictly greater than currentTime)
   • If valid, extends the token's expiration time to currentTime + timeToLive
   • If the token doesn't exist or has already expired, the operation is ignored

4. Count unexpired tokens at a given currentTime. Returns the number of tokens that haven't expired yet.

Important timing rule: If a token expires exactly at time t, and another action (renew or count) happens at the same time t, the expiration happens first. This means a token expiring at time t is considered expired when any operation occurs at time t.

For example:

• If a token expires at time 10, and you try to renew it at time 10, the renewal will fail because the token is already expired
• If a token expires at time 10, it won't be counted as unexpired when checking at time 10

The solution uses a hash table to store each tokenId with its expiration time, making generate and renew operations efficient O(1), while counting unexpired tokens requires checking all tokens O(n).

Intuition

The key insight is that we need to track tokens and their expiration times efficiently. Since each token has a unique ID and an associated expiration time, a hash table (dictionary) is the natural choice for storage.

Why a hash table? Let's think through what we need:

• When generating a token, we need to store its ID and when it expires
• When renewing a token, we need to quickly check if it exists and whether it's expired
• When counting unexpired tokens, we need to examine all tokens

A hash table gives us O(1) access to any token by its ID, which is perfect for generate and renew operations.

For storing expiration information, we have two choices:

1. Store the creation time and calculate expiration each time we need it
2. Store the expiration time directly

The second approach is simpler - we store currentTime + timeToLive as the value. This way, checking if a token is expired is just comparing the stored expiration time with the current time: if expirationTime > currentTime, the token is still valid.

The renew operation becomes straightforward: first check if the token exists and hasn't expired (d[tokenId] > currentTime), then update its expiration time to the new value (currentTime + timeToLive).

For counting unexpired tokens, while we could optimize this with more complex data structures (like a sorted list or heap to remove expired tokens), the simple approach of iterating through all tokens and counting those with expirationTime > currentTime is sufficient and keeps the code clean.

The beauty of this solution is its simplicity - we're essentially maintaining a mapping of tokenId -> expirationTime, and all operations become natural manipulations of this mapping.

Learn more about Linked List patterns.

Solution Approach

Let's implement the authentication system using a hash table to store token information.

Data Structure Choice: We use a hash table (Python's defaultdict(int)) where:

• Key: tokenId (string)
• Value: expiration time (integer)

The defaultdict(int) ensures that accessing a non-existent key returns 0, which simplifies our logic for checking expired tokens.

Implementation Details:

1. Constructor (__init__):

   • Store timeToLive as an instance variable self.t
   • Initialize an empty hash table self.d to store tokens

2. Generate Token (generate):

   • Simply add the token to our hash table
   • Set the expiration time as currentTime + timeToLive
   • Formula: self.d[tokenId] = currentTime + self.t
   • This overwrites any existing token with the same ID

3. Renew Token (renew):

   • First check if the token is valid (unexpired)
   • A token is expired if self.d[tokenId] <= currentTime
   • If expired or doesn't exist (defaultdict returns 0), ignore the operation
   • If valid, update the expiration time to currentTime + self.t

4. Count Unexpired Tokens (countUnexpiredTokens):

   • Iterate through all values (expiration times) in the hash table
   • Count tokens where expiration time > currentTime
   • Use Python's generator expression: sum(exp > currentTime for exp in self.d.values())
   • This efficiently counts True values (1 for True, 0 for False)

Time Complexity Analysis:

• generate: O(1) - single hash table insertion
• renew: O(1) - hash table lookup and update
• countUnexpiredTokens: O(n) - must check all n tokens in the hash table

Space Complexity: O(n) where n is the number of unique tokens stored

The solution elegantly handles the timing rule where expiration happens before other actions at the same time. By using <= in the renewal check and > in the counting check, we ensure that a token expiring at time t is considered expired for any operation at time t.

Example Walkthrough

Let's walk through a concrete example with timeToLive = 5 seconds:

Step 1: Initialize the system

• Create an AuthenticationManager with timeToLive = 5
• Hash table d = {} (empty)

Step 2: Generate token "abc" at time 2

• Call generate("abc", 2)
• Calculate expiration: 2 + 5 = 7
• Update hash table: d = {"abc": 7}
• Token "abc" will expire at time 7

Step 3: Generate token "xyz" at time 4

• Call generate("xyz", 4)
• Calculate expiration: 4 + 5 = 9
• Update hash table: d = {"abc": 7, "xyz": 9}

Step 4: Count unexpired tokens at time 6

• Call countUnexpiredTokens(6)
• Check each token:
  • "abc": expiration 7 > 6? ✓ (unexpired)
  • "xyz": expiration 9 > 6? ✓ (unexpired)
• Return: 2 tokens

Step 5: Renew token "abc" at time 6

• Call renew("abc", 6)
• Check if valid: d["abc"] = 7 > 6? ✓ (can renew)
• Update expiration: 6 + 5 = 11
• Hash table: d = {"abc": 11, "xyz": 9}

Step 6: Try to renew token "abc" at time 11 (exact expiration time)

• Call renew("abc", 11)
• Check if valid: d["abc"] = 11 > 11? ✗ (11 is not > 11)
• Token has expired, renewal ignored
• Hash table unchanged: d = {"abc": 11, "xyz": 9}

Step 7: Count unexpired tokens at time 11

• Call countUnexpiredTokens(11)
• Check each token:
  • "abc": expiration 11 > 11? ✗ (expired)
  • "xyz": expiration 9 > 11? ✗ (expired)
• Return: 0 tokens

This example demonstrates:

• How tokens are stored with their expiration times
• The renewal process extending expiration time
• The critical timing rule: a token expiring at time t is considered expired for operations at time t

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__(timeToLive): O(1) - Simply initializes the time-to-live value and creates an empty defaultdict.
• generate(tokenId, currentTime): O(1) - Performs a single dictionary insertion/update operation.
• renew(tokenId, currentTime): O(1) - Performs one dictionary lookup and potentially one update operation.
• countUnexpiredTokens(currentTime): O(n) - Iterates through all values in the dictionary to count unexpired tokens, where n is the number of tokens stored in the dictionary.

Space Complexity: O(n), where n is the number of key-value pairs (tokens) stored in the hash table d. The defaultdict stores one entry for each unique tokenId that has been generated, with each entry containing the token's expiration time. The space grows linearly with the number of tokens managed by the system.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Expiration Time Comparison

One of the most common mistakes is using the wrong comparison operator when checking if a token has expired. The problem states that if a token expires at time t, it's considered expired for any operation at time t.

Incorrect Implementation:

def renew(self, tokenId: str, currentTime: int) -> None:
    # WRONG: Using < instead of <=
    if self.tokens[tokenId] < currentTime:
        return
    self.tokens[tokenId] = currentTime + self.time_to_live

Why it's wrong: This would allow renewing a token at the exact moment it expires, violating the timing rule.

Correct Implementation:

def renew(self, tokenId: str, currentTime: int) -> None:
    # CORRECT: Token expired if expiration_time <= currentTime
    if self.tokens[tokenId] <= currentTime:
        return
    self.tokens[tokenId] = currentTime + self.time_to_live

2. Not Handling Non-Existent Tokens Properly

Without using defaultdict, forgetting to check if a token exists before accessing it can cause KeyError.

Incorrect Implementation:

def __init__(self, timeToLive: int):
    self.time_to_live = timeToLive
    self.tokens = {}  # Regular dict instead of defaultdict

def renew(self, tokenId: str, currentTime: int) -> None:
    # WRONG: Will raise KeyError if tokenId doesn't exist
    if self.tokens[tokenId] <= currentTime:
        return
    self.tokens[tokenId] = currentTime + self.time_to_live

Correct Implementation (without defaultdict):

def renew(self, tokenId: str, currentTime: int) -> None:
    # Check if token exists first
    if tokenId not in self.tokens or self.tokens[tokenId] <= currentTime:
        return
    self.tokens[tokenId] = currentTime + self.time_to_live

3. Memory Leak from Not Cleaning Up Expired Tokens

The current implementation never removes expired tokens from the dictionary, which can lead to memory issues in long-running systems.

Problem: If tokens are continuously generated but never cleaned up, the dictionary grows indefinitely.

Solution with Periodic Cleanup:

def countUnexpiredTokens(self, currentTime: int) -> int:
    # Optional: Clean up expired tokens while counting
    expired_tokens = [token_id for token_id, exp_time in self.tokens.items() 
                     if exp_time <= currentTime]
    for token_id in expired_tokens:
        del self.tokens[token_id]
  
    return len(self.tokens)

Alternative Solution with Lazy Cleanup:

def generate(self, tokenId: str, currentTime: int) -> None:
    self.tokens[tokenId] = currentTime + self.time_to_live
    # Periodically clean up (e.g., every 100 generates)
    if len(self.tokens) % 100 == 0:
        self._cleanup_expired(currentTime)

def _cleanup_expired(self, currentTime: int) -> None:
    expired = [tid for tid, exp in self.tokens.items() if exp <= currentTime]
    for tid in expired:
        del self.tokens[tid]

4. Inconsistent Time Comparison Logic

Using different comparison logic between renew and countUnexpiredTokens methods.

Incorrect Implementation:

def renew(self, tokenId: str, currentTime: int) -> None:
    if self.tokens[tokenId] <= currentTime:  # Using <=
        return
    self.tokens[tokenId] = currentTime + self.time_to_live

def countUnexpiredTokens(self, currentTime: int) -> int:
    # WRONG: Using >= instead of >
    return sum(exp >= currentTime for exp in self.tokens.values())

Why it's wrong: This counts tokens that expire at currentTime as unexpired, contradicting the timing rule.

Correct Implementation: Both methods should treat tokens expiring at currentTime as expired:

• renew: Check expiration_time <= currentTime (token is expired)
• count: Check expiration_time > currentTime (token is unexpired)