Design Authentication Manager: Hash Map Design Pattern

Design Authentication Manager asks you to build a token-based authentication system. You are given a timeToLive value. The class supports three operations: generate(tokenId, currentTime) creates a new token that expires at currentTime + timeToLive, renew(tokenId, currentTime) extends an unexpired token's lifetime, and countUnexpiredTokens(currentTime) returns how many tokens have not yet expired. A token is considered expired if its expiry time is less than or equal to the current time.

This is LeetCode 1797: Design Authentication Manager.

Why this problem matters

Design problems like this test your ability to pick the right data structure for a set of operations. There is no tricky algorithm here. The challenge is recognizing that a single hash map can support all three operations cleanly, and understanding the tradeoffs involved in how you handle expired tokens.

This pattern shows up constantly in real systems. Session managers, API rate limiters, and cache invalidation layers all store key-value pairs with expiration times. The decisions you make here (lazy vs. eager cleanup, O(1) writes vs. O(n) reads) are the same decisions backend engineers make when designing production authentication systems. Getting fluent with this pattern gives you vocabulary for both interviews and system design discussions.

Token management is also a great context for understanding the difference between correctness and optimization. The simplest correct solution stores every token and scans on count. You could optimize with a sorted structure for faster counting, but the simple approach is clean, correct, and sufficient for the problem's constraints.

The key insight

Store token expiration times in a hash map where the key is the token ID and the value is the expiration timestamp. For generate, insert tokenId -> currentTime + timeToLive. For renew, check whether the token exists in the map and its expiration is strictly greater than currentTime. If so, update the expiration to currentTime + timeToLive. If not, do nothing. For countUnexpiredTokens, iterate over all values in the map and count those strictly greater than currentTime.

The critical detail is the expiration check: a token is unexpired only when expiry > currentTime, not expiry >= currentTime. If the expiry equals the current time, the token has already expired.

The solution

class AuthenticationManager:
    def __init__(self, time_to_live: int):
        self.ttl = time_to_live
        self.tokens = {}

    def generate(self, token_id: str, current_time: int) -> None:
        self.tokens[token_id] = current_time + self.ttl

    def renew(self, token_id: str, current_time: int) -> None:
        if token_id in self.tokens and self.tokens[token_id] > current_time:
            self.tokens[token_id] = current_time + self.ttl

    def count_unexpired_tokens(self, current_time: int) -> int:
        return sum(1 for exp in self.tokens.values() if exp > current_time)

The generate method is a single dictionary write. It overwrites any existing token with the same ID, which matches the problem's guarantee that generate is only called with new token IDs.

The renew method performs two checks in one if statement: the token must exist, and its stored expiry must be strictly greater than the current time. If either condition fails, the method does nothing. When both pass, it resets the expiry to currentTime + timeToLive, effectively extending the token's life.

The count_unexpired_tokens method uses a generator expression to scan all stored expiry values and count those that are still in the future. This is a linear scan over the map, but it is the simplest correct approach.

Visual walkthrough

Let's trace through a full sequence of operations with timeToLive = 5. Watch how the token map changes at each step, and pay attention to the expiry comparisons during renew and count.

Notice how token "bbb" stays in the map even after it expires. The renew call at time 8 checks the expiry (7) against the current time (8) and correctly skips the update. The countUnexpiredTokens call at time 11 scans every entry but only counts "ccc" because it is the only token with expiry greater than 11.

Complexity analysis

Time: generate and renew are O(1) since they perform a constant number of dictionary operations. countUnexpiredTokens is O(n) where n is the number of tokens in the map, because it scans all values.

Space: O(n) for storing all tokens. With lazy deletion, n includes expired tokens that have not been cleaned up. In the worst case, every generated token remains in the map.

The building blocks

1. Token expiry map

The core data structure is a dictionary mapping token IDs to their expiration timestamps. This gives O(1) lookups for both generate (write) and renew (read + conditional write). The value is an absolute timestamp, not a relative TTL, which makes comparisons against the current time simple and avoids recomputing expiry on every access.

2. Lazy expiration checking

Rather than removing tokens the moment they expire, you leave them in the map and skip over them during operations. The renew method ignores expired tokens by checking expiry > currentTime before updating. The count method filters them out with a generator expression. This approach is simpler to implement and avoids the overhead of maintaining a separate expiration queue or sorted structure.

Edge cases

• Renewing an expired token. If the token exists but its expiry is at or before the current time, the renew call does nothing. The condition self.tokens[token_id] > current_time handles this.
• Renewing a nonexistent token. If the token ID is not in the map at all, the token_id in self.tokens check fails and the method returns immediately.
• Count at exact expiry time. A token with expiry equal to currentTime is considered expired. The comparison is strictly greater than, not greater than or equal to.
• Multiple generates with different IDs. Each generate call adds a new entry. The map grows over time since expired entries are not cleaned up.
• Renew then count. Renewing a token changes its expiry, so a subsequent countUnexpiredTokens call will reflect the updated value. Since both read from the same map, consistency is automatic.

From understanding to recall

This problem is deceptively simple. You will read the solution, understand every line, and feel confident. But when you sit down to write it from memory, the small details will trip you up. Is the expiry check >= or >? Does renew return anything? What happens when you try to renew a token that was never generated?

The way to lock this in is repetition. Write the class from scratch a few times, focusing on the exact boundary condition in the renew method. Pay attention to whether the expiry comparison uses strict inequality. These details are what separate a correct solution from a subtle bug, and the only way to make them automatic is practice.

Related posts

• LRU Cache - Hash map plus doubly linked list design for cache management with eviction policy
• Design Add and Search Words Data Structure - Trie-based design pattern where the data structure choice drives the solution
• Implement Trie - Fundamental data structure design problem that builds intuition for class-based solutions

The design pattern here is universal: pick a data structure, define your operations, and handle edge cases at the boundaries. If you want to build fluency with these patterns so they become second nature under interview pressure, the key is spaced repetition.