Code Implementation

class AuthenticationManager:

    def __init__(self, timeToLive: int):
        self.timeToLive = timeToLive
        self.tokens = {}

    def generate(self, tokenId: str, currentTime: int) -> None:
        self.tokens[tokenId] = currentTime + self.timeToLive

    def renew(self, tokenId: str, currentTime: int) -> None:
        if tokenId in self.tokens and self.tokens[tokenId] > currentTime:
            self.tokens[tokenId] = currentTime + self.timeToLive

    def countUnexpiredTokens(self, currentTime: int) -> int:
        return sum(expiry > currentTime for expiry in self.tokens.values())
      

class AuthenticationManager {
    int timeToLive;
    unordered_map<string, int> tokens;
public:
    AuthenticationManager(int timeToLive) {
        this->timeToLive = timeToLive;
    }
    
    void generate(string tokenId, int currentTime) {
        tokens[tokenId] = currentTime + timeToLive;
    }
    
    void renew(string tokenId, int currentTime) {
        if (tokens.count(tokenId) && tokens[tokenId] > currentTime) {
            tokens[tokenId] = currentTime + timeToLive;
        }
    }
    
    int countUnexpiredTokens(int currentTime) {
        int count = 0;
        for (auto& [_, expiry] : tokens) {
            if (expiry > currentTime) count++;
        }
        return count;
    }
};
      

class AuthenticationManager {
    private int timeToLive;
    private Map<String, Integer> tokens;

    public AuthenticationManager(int timeToLive) {
        this.timeToLive = timeToLive;
        this.tokens = new HashMap<>();
    }

    public void generate(String tokenId, int currentTime) {
        tokens.put(tokenId, currentTime + timeToLive);
    }

    public void renew(String tokenId, int currentTime) {
        if (tokens.containsKey(tokenId) && tokens.get(tokenId) > currentTime) {
            tokens.put(tokenId, currentTime + timeToLive);
        }
    }

    public int countUnexpiredTokens(int currentTime) {
        int count = 0;
        for (int expiry : tokens.values()) {
            if (expiry > currentTime) count++;
        }
        return count;
    }
}
      

class AuthenticationManager {
    constructor(timeToLive) {
        this.timeToLive = timeToLive;
        this.tokens = new Map();
    }

    generate(tokenId, currentTime) {
        this.tokens.set(tokenId, currentTime + this.timeToLive);
    }

    renew(tokenId, currentTime) {
        if (this.tokens.has(tokenId) && this.tokens.get(tokenId) > currentTime) {
            this.tokens.set(tokenId, currentTime + this.timeToLive);
        }
    }

    countUnexpiredTokens(currentTime) {
        let count = 0;
        for (let expiry of this.tokens.values()) {
            if (expiry > currentTime) count++;
        }
        return count;
    }
}
      

Problem Description

The "Design Authentication Manager" problem requires you to implement a system that manages authentication tokens with an expiration policy. Each token is identified by a unique tokenId and has a limited lifespan defined by timeToLive seconds. The class must support three operations:

• generate(tokenId, currentTime): Registers a new token with the given tokenId at currentTime. The token will expire after timeToLive seconds from currentTime.
• renew(tokenId, currentTime): If the token exists and has not expired, resets its expiry time to currentTime + timeToLive. If the token has expired or does not exist, do nothing.
• countUnexpiredTokens(currentTime): Returns the number of tokens that are still valid (i.e., not expired) at currentTime.

Key constraints include:

• Each tokenId is unique.
• Expired tokens should not be renewed or counted.
• All operations should be efficient, as they may be called frequently.

Thought Process

The core challenge is to efficiently track tokens and their expiration times, allowing for fast generation, renewal, and counting of unexpired tokens. The naive approach would be to store all tokens and their expiration times, and whenever we need to count unexpired tokens, iterate through the entire collection and check each expiry. However, this could be slow if there are many tokens.

To optimize, we need a data structure that allows:

• Quick updates to expiry times (for renewals)
• Efficient lookup to check if a token exists and is valid
• Fast counting of unexpired tokens

Solution Approach

The solution uses a hash map to store each tokenId and its corresponding expiry time. Here are the steps for each operation:

1. Generate: On calling generate(tokenId, currentTime), insert or update the tokenId in the map with value currentTime + timeToLive.
2. Renew: On calling renew(tokenId, currentTime), check if the token exists and its expiry time is greater than currentTime. If so, update its expiry to currentTime + timeToLive. If not, do nothing.
3. Count Unexpired Tokens: On calling countUnexpiredTokens(currentTime), iterate through the map and count tokens whose expiry time is greater than currentTime.

We use a hash map because it provides O(1) average time complexity for insert, lookup, and update operations, making all three methods efficient.

For even more optimization (not required for this problem), we could periodically clean up expired tokens to save memory. However, for correctness and efficiency in the context of this problem, the hash map approach is sufficient.

Example Walkthrough

Let's walk through an example with timeToLive = 5:

1. generate("abc", 1): Adds "abc" with expiry at 6 (1 + 5).
2. generate("def", 2): Adds "def" with expiry at 7 (2 + 5).
3. renew("abc", 4): "abc" has expiry 6, which is > 4, so update expiry to 9 (4 + 5).
4. countUnexpiredTokens(5): "abc" (expiry 9) and "def" (expiry 7) are both > 5, so return 2.
5. countUnexpiredTokens(7): "abc" (expiry 9) is > 7, "def" (expiry 7) is not (> 7 is false), so return 1.
6. renew("def", 8): "def" has expiry 7, which is not > 8, so do nothing.
7. countUnexpiredTokens(10): "abc" (expiry 9) is not > 10, so return 0.

At each step, we see how the expiry times are updated and how expired tokens are ignored for renewals and counting.

Time and Space Complexity

Brute-force approach: If we used a list to store all tokens, counting unexpired tokens would be O(n) where n is the number of tokens. Renew and generate would also be O(n) if searching through a list.

Optimized approach (hash map):

• generate: O(1) average, as inserting/updating in a hash map is constant time.
• renew: O(1) average, as lookup and update are constant time.
• countUnexpiredTokens: O(n), where n is the number of tokens, because we must check all expiry times.

Summary

The Authentication Manager problem is elegantly solved using a hash map to track token expirations. This approach ensures fast generation and renewal of tokens, and although counting unexpired tokens is O(n), it is simple and effective for the problem's constraints. The key insight is to use efficient data structures for quick lookups and updates, while handling expiry logic carefully to avoid renewing or counting expired tokens.