Design Authentication Manager - Practice Coding Problems

Design Authentication Manager - 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: 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.

Input & Output

Example 1 — Basic Authentication Operations

$ Input: operations = ["AuthenticationManager","renew","generate","countUnexpiredTokens","generate","renew","renew","countUnexpiredTokens"], params = [[5],["aaa",1],["aaa",2],[6],["bbb",7],["aaa",8],["bbb",10],[15]]

› Output: [null,null,null,1,null,null,null,0]

💡 Note: AuthenticationManager(5): timeToLive = 5. renew("aaa", 1): no token "aaa" exists, ignored. generate("aaa", 2): token "aaa" expires at time 7. countUnexpiredTokens(6): "aaa" expires at 7 > 6, so 1 token. generate("bbb", 7): token "bbb" expires at time 12. renew("aaa", 8): "aaa" expired at 7 < 8, ignored. renew("bbb", 10): "bbb" expires at 12 > 10, renewed to expire at 15. countUnexpiredTokens(15): both tokens expired, so 0 tokens.

Example 2 — Token Renewal

$ Input: operations = ["AuthenticationManager","generate","renew","countUnexpiredTokens"], params = [[3],["test",1],["test",3],[4]]

› Output: [null,null,null,1]

💡 Note: AuthenticationManager(3): timeToLive = 3. generate("test", 1): token expires at time 4. renew("test", 3): token still valid (4 > 3), renewed to expire at 6. countUnexpiredTokens(4): token expires at 6 > 4, so 1 token.

Example 3 — Expiration Edge Case

$ Input: operations = ["AuthenticationManager","generate","countUnexpiredTokens","countUnexpiredTokens"], params = [[2],["token",5],[7],[8]]

› Output: [null,null,1,0]

💡 Note: AuthenticationManager(2): timeToLive = 2. generate("token", 5): token expires at time 7. countUnexpiredTokens(7): token expires exactly at 7, but expiration happens before the count, so 1 token. countUnexpiredTokens(8): token expired, so 0 tokens.

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
At most 2000 calls will be made to generate, renew, and countUnexpiredTokens

Visualization

Tap to expand

Understanding the Visualization

Input Operations

Sequence of AuthenticationManager operations

Token Management

Generate, renew, and count tokens based on expiry

Output Results

Return results for count operations

Key Takeaway

🎯 Key Insight: Use hash map to track token expiry times for efficient operations

Asked in

M Microsoft 15 a Amazon 12

The key insight is to use a hash map to store token IDs mapped to their expiry times. This enables O(1) generate and renew operations, while countUnexpiredTokens requires O(n) time to scan all tokens. Best approach is the hash map solution with Time: O(1) for generate/renew, O(n) for count, Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Approach	O(n)	O(n)	Use hash map to store tokens with their expiry times for O(1) access
Brute Force with Linear Search	O(n)	O(n)	Store all tokens and check each one's expiry time for every operation

Hash Map Approach — Algorithm Steps

Step 1: Use hash map to store tokenId -> expiry time mapping
Step 2: Generate and renew operations are O(1)
Step 3: Count operation scans all values in hash map

Visualization

Tap to expand

Step-by-Step Walkthrough

Hash Map Storage

Store tokenId -> expiry mapping

O(1) Operations

Generate and renew in constant time

Scan Values

Count unexpired by checking all values

Code -

solution.c — C

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

#define MAX_TOKENS 1000

typedef struct {
    char tokenId[100];
    int expiry;
    int valid;
} Token;

typedef struct {
    int timeToLive;
    Token tokens[MAX_TOKENS];
    int tokenCount;
} AuthenticationManager;

AuthenticationManager* authenticationManagerCreate(int timeToLive) {
    AuthenticationManager* obj = malloc(sizeof(AuthenticationManager));
    obj->timeToLive = timeToLive;
    obj->tokenCount = 0;
    for (int i = 0; i < MAX_TOKENS; i++) {
        obj->tokens[i].valid = 0;
    }
    return obj;
}

void authenticationManagerGenerate(AuthenticationManager* obj, char* tokenId, int currentTime) {
    int found = -1;
    for (int i = 0; i < obj->tokenCount; i++) {
        if (strcmp(obj->tokens[i].tokenId, tokenId) == 0) {
            found = i;
            break;
        }
    }
    
    if (found >= 0) {
        obj->tokens[found].expiry = currentTime + obj->timeToLive;
        obj->tokens[found].valid = 1;
    } else {
        strcpy(obj->tokens[obj->tokenCount].tokenId, tokenId);
        obj->tokens[obj->tokenCount].expiry = currentTime + obj->timeToLive;
        obj->tokens[obj->tokenCount].valid = 1;
        obj->tokenCount++;
    }
}

void authenticationManagerRenew(AuthenticationManager* obj, char* tokenId, int currentTime) {
    for (int i = 0; i < obj->tokenCount; i++) {
        if (obj->tokens[i].valid && strcmp(obj->tokens[i].tokenId, tokenId) == 0 && obj->tokens[i].expiry > currentTime) {
            obj->tokens[i].expiry = currentTime + obj->timeToLive;
            break;
        }
    }
}

int authenticationManagerCountUnexpiredTokens(AuthenticationManager* obj, int currentTime) {
    int count = 0;
    for (int i = 0; i < obj->tokenCount; i++) {
        if (obj->tokens[i].valid && obj->tokens[i].expiry > currentTime) {
            count++;
        }
    }
    return count;
}

int main() {
    printf("[null,null,null,1,null,2]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Generate/renew are O(1), but countUnexpiredTokens is O(n)

✓ Linear Growth

Space Complexity

O(n)

Hash map stores up to n tokens

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

380 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler