1797. Design Authentication Manager - Solution

The problem

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.

Example 1:

Input
["AuthenticationManager", "renew", "generate", "countUnexpiredTokens", "generate", "renew", "renew", "countUnexpiredTokens"]
[[5], ["aaa", 1], ["aaa", 2], [6], ["bbb", 7], ["aaa", 8], ["bbb", 10], [15]]
Output
[null, null, null, 1, null, null, null, 0]

Explanation
AuthenticationManager authenticationManager = new AuthenticationManager(5); // Constructs the AuthenticationManager with timeToLive = 5 seconds.
authenticationManager.renew("aaa", 1); // No token exists with tokenId "aaa" at time 1, so nothing happens.
authenticationManager.generate("aaa", 2); // Generates a new token with tokenId "aaa" at time 2.
authenticationManager.countUnexpiredTokens(6); // The token with tokenId "aaa" is the only unexpired one at time 6, so return 1.
authenticationManager.generate("bbb", 7); // Generates a new token with tokenId "bbb" at time 7.
authenticationManager.renew("aaa", 8); // The token with tokenId "aaa" expired at time 7, and 8 >= 7, so at time 8 the renew request is ignored, and nothing happens.
authenticationManager.renew("bbb", 10); // The token with tokenId "bbb" is unexpired at time 10, so the renew request is fulfilled and now the token will expire at time 15.
authenticationManager.countUnexpiredTokens(15); // The token with tokenId "bbb" expires at time 15, and the token with tokenId "aaa" expired at time 7, so currently no token is unexpired, so return 0.

Constraints:

1 <= timeToLive <= 10⁸
1 <= currentTime <= 10⁸
1 <= tokenId.length <= 5
tokenId consists only of lowercase letters.
All calls to generate will contain unique values of tokenId.
The values of currentTime across all the function calls will be strictly increasing.
At most 2000 calls will be made to all functions combined.

Approach overview

Problem Overview: Design an authentication system that issues tokens with a fixed timeToLive. Each token can be generated, renewed before expiration, and counted if still valid at a given time. The system must support efficient lookup and expiration handling across multiple operations.

Approach 1: Using HashMap for Token Management (O(1) average time)

Store each tokenId in a hash map with its expiration timestamp. When generate is called, insert tokenId → currentTime + timeToLive. For renew, first check if the token exists and whether its expiration is greater than the current time; if valid, update the expiration timestamp. For countUnexpiredTokens, iterate through the map and count entries whose expiration time is still greater than currentTime. Hash lookup and updates run in O(1) average time using a hash table, though counting requires scanning all stored tokens. Space complexity is O(n) where n is the number of active tokens ever created.

Approach 2: Ordered Dictionary to Maintain Token Expiration Order (O(n) cleanup, O(1) amortized ops)

Maintain tokens in insertion or expiration order using an ordered dictionary or a structure backed by a doubly-linked list. Each node stores tokenId and expiration time, while a hash map points to nodes for constant-time access. When a token expires, remove it from the front of the structure since expirations occur in chronological order. Renewing a token removes its node and reinserts it with an updated expiration timestamp. This approach reduces repeated scanning during countUnexpiredTokens because expired tokens are cleaned up incrementally. Time complexity for updates remains O(1) amortized, and space complexity is O(n).

Recommended for interviews: Start with the HashMap approach since it directly models the problem and shows you understand token validation with constant-time lookups. Interviewers often accept this design because operations like generate and renew remain efficient. The ordered structure variant demonstrates stronger system design thinking by handling expiration cleanup proactively and combining a hash map with a linked structure, a common pattern in design problems such as LRU caches.

Approach 1: Using HashMap for Token Management

In this approach, we utilize a hash map (or dictionary) to store each token's expiration time. This allows for efficient lookups, renewals, and expirations.

generate: Simply add the token's expiration time to the map.
renew: Only renew if the token is unexpired by checking the current time against the stored expiration time.
countUnexpiredTokens: Iterate through the values of the map, counting tokens that have not yet expired. Clean up any expired tokens in the process.

Python

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

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

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

    def count_unexpired_tokens(self, current_time: int) -> int:
        count = 0
        for token in list(self.token_map):
            if self.token_map[token] > current_time:
                count += 1
            else:
                del self.token_map[token]
        return count

Java

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

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

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

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

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

    public int countUnexpiredTokens(int currentTime) {
        int count = 0;
        Iterator<Map.Entry<String, Integer>> it = tokenMap.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<String, Integer> entry = it.next();
            if (entry.getValue() > currentTime) {
                count++;
            } else {
                it.remove();
            }
        }
        return count;
    }
}

C++

#include <unordered_map>

class AuthenticationManager {
public:
    AuthenticationManager(int timeToLive) : timeToLive(timeToLive) {}

    void generate(const std::string& tokenId, int currentTime) {
        tokenMap[tokenId] = currentTime + timeToLive;
    }

    void renew(const std::string& tokenId, int currentTime) {
        if (tokenMap.find(tokenId) != tokenMap.end() && tokenMap[tokenId] > currentTime) {
            tokenMap[tokenId] = currentTime + timeToLive;
        }
    }

    int countUnexpiredTokens(int currentTime) {
        int count = 0;
        for (auto it = tokenMap.begin(); it != tokenMap.end();) {
            if (it->second > currentTime) {
                count++;
                ++it;
            } else {
                it = tokenMap.erase(it);
            }
        }
        return count;
    }

private:
    int timeToLive;
    std::unordered_map<std::string, int> tokenMap;
};

JavaScript

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

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

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

    countUnexpiredTokens(currentTime) {
        let count = 0;
        for (const [key, expireTime] of this.tokenMap.entries()) {
            if (expireTime > currentTime) {
                count++;
            } else {
                this.tokenMap.delete(key);
            }
        }
        return count;
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define HASH_MAP_SIZE 256

typedef struct Token {
    char tokenId[6];
    int expireTime;
    struct Token* next;
} Token;

typedef struct {
    int timeToLive;
    Token* map[HASH_MAP_SIZE];
} AuthenticationManager;

unsigned int hash(const char* tokenId) {
    unsigned int hashValue = 0;
    while (*tokenId) {
        hashValue = (hashValue << 5) + *tokenId++;
    }
    return hashValue % HASH_MAP_SIZE;
}

AuthenticationManager* authenticationManagerCreate(int timeToLive) {
    AuthenticationManager* obj = malloc(sizeof(AuthenticationManager));
    memset(obj->map, 0, sizeof(obj->map));
    obj->timeToLive = timeToLive;
    return obj;
}

void generate(AuthenticationManager* obj, char* tokenId, int currentTime) {
    unsigned int index = hash(tokenId);
    Token* token = malloc(sizeof(Token));
    strcpy(token->tokenId, tokenId);
    token->expireTime = currentTime + obj->timeToLive;
    token->next = obj->map[index];
    obj->map[index] = token;
}

void renew(AuthenticationManager* obj, char* tokenId, int currentTime) {
    unsigned int index = hash(tokenId);
    Token* curr = obj->map[index];
    while (curr != NULL) {
        if (!strcmp(curr->tokenId, tokenId) && curr->expireTime > currentTime) {
            curr->expireTime = currentTime + obj->timeToLive;
            return;
        }
        curr = curr->next;
    }
}

int countUnexpiredTokens(AuthenticationManager* obj, int currentTime) {
    int count = 0;
    for (int i = 0; i < HASH_MAP_SIZE; ++i) {
        Token* curr = obj->map[i];
        Token** prev = &obj->map[i];
        while (curr != NULL) {
            if (curr->expireTime > currentTime) {
                count++;
                prev = &(curr->next);
            } else {
                *prev = curr->next;
                free(curr);
            }
            curr = *prev;
        }
    }
    return count;
}

void authenticationManagerFree(AuthenticationManager* obj) {
    for (int i = 0; i < HASH_MAP_SIZE; ++i) {
        Token* curr = obj->map[i];
        while (curr != NULL) {
            Token* next = curr->next;
            free(curr);
            curr = next;
        }
    }
    free(obj);
}

using System;
using System.Collections.Generic;

public class AuthenticationManager {
    private int timeToLive;
    private Dictionary<string, int> tokenMap;

    public AuthenticationManager(int timeToLive) {
        this.timeToLive = timeToLive;
        this.tokenMap = new Dictionary<string, int>();
    }

    public void Generate(string tokenId, int currentTime) {
        tokenMap[tokenId] = currentTime + timeToLive;
    }

    public void Renew(string tokenId, int currentTime) {
        if (tokenMap.ContainsKey(tokenId) && tokenMap[tokenId] > currentTime) {
            tokenMap[tokenId] = currentTime + timeToLive;
        }
    }

    public int CountUnexpiredTokens(int currentTime) {
        int count = 0;
        var keysToRemove = new List<string>();

        foreach (var kvp in tokenMap) {
            if (kvp.Value > currentTime) {
                count++;
            } else {
                keysToRemove.Add(kvp.Key);
            }
        }

        foreach (var key in keysToRemove) {
            tokenMap.Remove(key);
        }

        return count;
    }
}

The Python solution uses a dictionary to store the token's expiration times. We directly manipulate this dictionary during operations. The use of dictionary methods ensures average constant time operations for adding and checking tokens.

Complexity

In Python, operations generate and renew have O(1) average time complexity. The count_unexpired_tokens operation has time complexity O(n) in the worst case. Space complexity is O(n) due to dictionary storage.

Try this approach in the editor

Approach 2: Using Ordered Dictionary to Maintain Token Expiration Order

In this second approach, we introduce an ordered dictionary to help maintain the order of token expirations, which can make count operations more efficient by stopping early when no more unexpired tokens are found.

generate: Insert token in the ordered dictionary with expiration time as the value.
renew: Remove the token if expired, otherwise update its expiration time.
countUnexpiredTokens: Traverse through tokens in order; stop counting when an expired token is encountered.

Python

from collections import OrderedDict

class AuthenticationManager:
    def __init__(self, time_to_live: int):
        self.time_to_live = time_to_live
        self.token_map = OrderedDict()

    def generate(self, token_id: str, current_time: int) -> None:
        self.token_map[token_id] = current_time + self.time_to_live
        self.token_map.move_to_end(token_id)

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

    def count_unexpired_tokens(self, current_time: int) -> int:
        while self.token_map:
            token, expire_time = next(iter(self.token_map.items()))
            if expire_time <= current_time:
                self.token_map.popitem(last=False)
            else:
                break
        return len(self.token_map)

Python's OrderedDict maintains the order of insertion, providing ordered iteration that helps manage token expiration. When counting unexpired tokens, we can efficiently remove expired tokens by iterating in order of expiration.

Complexity

The time complexities for generate and renew remain O(1) on average with ordered dictionary. The count_unexpired_tokens generally performs better than unordered approaches, as early stopping can reduce average time complexity.

Try this approach in the editor

Approach 3: Hash Table

We can simply maintain a hash table d, where the key is tokenId and the value is the expiration time.

During the generate operation, we store tokenId as the key and currentTime + timeToLive as the value in the hash table d.
During the renew operation, if tokenId is not in the hash table d, or currentTime >= d[tokenId], we ignore this operation; otherwise, we update d[tokenId] to currentTime + timeToLive.
During the countUnexpiredTokens operation, we traverse the hash table d and count the number of unexpired tokenId.

In terms of time complexity, both generate and renew operations have a time complexity of O(1), and the countUnexpiredTokens operation has a time complexity of O(n), where n is the number of key-value pairs in the hash table d.

The space complexity is O(n), where n is the number of key-value pairs in the hash table d.

TypeScript

class AuthenticationManager {
    private timeToLive: number;
    private map: Map<string, number>;

    constructor(timeToLive: number) {
        this.timeToLive = timeToLive;
        this.map = new Map<string, number>();
    }

    generate(tokenId: string, currentTime: number): void {
        this.map.set(tokenId, currentTime + this.timeToLive);
    }

    renew(tokenId: string, currentTime: number): void {
        if ((this.map.get(tokenId) ?? 0) <= currentTime) {
            return;
        }
        this.map.set(tokenId, currentTime + this.timeToLive);
    }

    countUnexpiredTokens(currentTime: number): number {
        let res = 0;
        for (const time of this.map.values()) {
            if (time > currentTime) {
                res++;
            }
        }
        return res;
    }
}

/**
 * Your AuthenticationManager object will be instantiated and called as such:
 * var obj = new AuthenticationManager(timeToLive)
 * obj.generate(tokenId,currentTime)
 * obj.renew(tokenId,currentTime)
 * var param_3 = obj.countUnexpiredTokens(currentTime)
 */

type AuthenticationManager struct {
	t int
	d map[string]int
}

func Constructor(timeToLive int) AuthenticationManager {
	return AuthenticationManager{timeToLive, map[string]int{}}
}

func (this *AuthenticationManager) Generate(tokenId string, currentTime int) {
	this.d[tokenId] = currentTime + this.t
}

func (this *AuthenticationManager) Renew(tokenId string, currentTime int) {
	if v, ok := this.d[tokenId]; !ok || v <= currentTime {
		return
	}
	this.Generate(tokenId, currentTime)
}

func (this *AuthenticationManager) CountUnexpiredTokens(currentTime int) int {
	ans := 0
	for _, exp := range this.d {
		if exp > currentTime {
			ans++
		}
	}
	return ans
}

/**
 * Your AuthenticationManager object will be instantiated and called as such:
 * obj := Constructor(timeToLive);
 * obj.Generate(tokenId,currentTime);
 * obj.Renew(tokenId,currentTime);
 * param_3 := obj.CountUnexpiredTokens(currentTime);
 */

Rust

use std::collections::HashMap;
struct AuthenticationManager {
    time_to_live: i32,
    map: HashMap<String, i32>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl AuthenticationManager {
    fn new(timeToLive: i32) -> Self {
        Self {
            time_to_live: timeToLive,
            map: HashMap::new(),
        }
    }

    fn generate(&mut self, token_id: String, current_time: i32) {
        self.map.insert(token_id, current_time + self.time_to_live);
    }

    fn renew(&mut self, token_id: String, current_time: i32) {
        if self.map.get(&token_id).unwrap_or(&0) <= &current_time {
            return;
        }
        self.map.insert(token_id, current_time + self.time_to_live);
    }

    fn count_unexpired_tokens(&self, current_time: i32) -> i32 {
        self.map
            .values()
            .filter(|&time| *time > current_time)
            .count() as i32
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using HashMap for Token Management	In Python, operations `generate` and `renew` have O(1) average time complexity. The `count_unexpired_tokens` operation has time complexity O(n) in the worst case. Space complexity is O(n) due to dictionary storage.
Using Ordered Dictionary to Maintain Token Expiration Order	The time complexities for `generate` and `renew` remain O(1) on average with ordered dictionary. The `count_unexpired_tokens` generally performs better than unordered approaches, as early stopping can reduce average time complexity.
Hash Table	–

Complexity analysis

Approach	Time	Space	When to Use
HashMap for Token Management	O(1) generate/renew, O(n) count	O(n)	General implementation when token count is moderate and simplicity is preferred
Ordered Dictionary with Expiration Order	O(1) amortized operations	O(n)	When frequent expiration cleanup is required and you want to avoid scanning all tokens

Frequently asked questions

Is Design Authentication Manager easy or hard?

Design Authentication Manager is considered a Medium difficulty problem. The logic is straightforward with a hash map, but handling renewals, expirations, and efficient counting requires careful reasoning about timestamps and data structure design.

Design Authentication Manager Python/Java solution

In Python, the solution typically uses a dictionary mapping tokenId to expiration timestamps. In Java, a HashMap<String, Integer> is commonly used. Both implementations perform constant-time insert, lookup, and update operations for generate and renew.

How to solve Design Authentication Manager in O(n)?

Store token IDs in a hash map with their expiration times. When generating a token, record currentTime + timeToLive. For renew, update the expiration only if the token has not expired. Counting valid tokens iterates through the map and counts entries with expiration greater than the current time, resulting in O(n) time.

What is the best approach for Design Authentication Manager?

The common solution uses a HashMap that maps tokenId to its expiration timestamp. Token generation and renewal are constant-time operations using hash lookups, while counting valid tokens scans the map. A more advanced design combines a hash map with an ordered structure such as a doubly linked list to remove expired tokens incrementally.

Is Design Authentication Manager asked at Google/Amazon/Meta?

Design-style problems involving token systems, caching, and expiration logic are common in interviews at companies like Amazon, Google, and Meta. This problem tests hash table usage and object-oriented design patterns similar to LRU cache implementations.

What data structure is used in Design Authentication Manager?

The primary data structure is a hash table mapping tokenId to expiration time. Some optimized solutions also use a doubly linked list or ordered dictionary to maintain tokens by expiration order for faster cleanup.

What is the time complexity of Design Authentication Manager?

With a HashMap implementation, generate and renew operations run in O(1) average time, while countUnexpiredTokens requires O(n) time to check all tokens. Space complexity is O(n) to store token IDs and expiration timestamps.

Design Authentication Manager solution and explanation

The problem

Approach overview

Approach 1: Using HashMap for Token Management

Approach 2: Using Ordered Dictionary to Maintain Token Expiration Order

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Design Authentication Manager solution and explanation

The problem

Approach overview

Approach 1: Using HashMap for Token Management

Approach 2: Using Ordered Dictionary to Maintain Token Expiration Order

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems