Design Authentication Manager

Medium
2070.

Design Authentication Manager

MediumHash TableLinked ListDesign

Design Authentication Manager is a medium coding problem on hash table.

An authentication system issues tokens that live for timeToLive seconds: a token generated or renewed at time t expires at time t + timeToLive. A renewal pushes the expiry back to timeToLive seconds after the renewal.

Write the class AuthenticationManager:

  • AuthenticationManager(int timeToLive) sets the lifetime of every token.
  • void generate(String tokenId, int currentTime) issues a new token tokenId at currentTime.
  • void renew(String tokenId, int currentTime) renews the token tokenId if it exists and has not expired at currentTime. Renewing a token that does not exist or has already expired does nothing.
  • int countUnexpiredTokens(int currentTime) returns how many tokens are unexpired at currentTime.

Expiry takes effect before anything else: a token that expires exactly at time t is already expired for a renew or a count made at time t.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

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
Renewing aaa at time 1 does nothing — it does not exist yet. aaa is generated at 2 and expires at 7, so it counts at 6, but at 8 it has expired and cannot be renewed. bbb, generated at 7, is renewed at 10 to expire at 15, so at 15 no token is left.

Example 2

Input
["AuthenticationManager","generate","renew","countUnexpiredTokens","countUnexpiredTokens"] [[3],["x",1],["x",3],[5],[6]]
Output
[null,null,null,1,0]
Explanation
x is generated at 1 with expiry 4 and renewed at 3 to expiry 6. At 5 it is alive; at 6 it has just expired.

Constraints

  • 1 <= timeToLive <= 10^8
  • 1 <= currentTime <= 10^8
  • 1 <= tokenId.length <= 5
  • tokenId consists of lowercase English letters
  • Every generate call uses a tokenId never generated before
  • The currentTime values of all calls are strictly increasing
  • At most 2000 calls are made to the three methods in total
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} timeToLive
 */
var AuthenticationManager = function(timeToLive) {
    
};

/**
 * @param {string} tokenId
 * @param {number} currentTime
 * @return {void}
 */
AuthenticationManager.prototype.generate = function(tokenId, currentTime) {
    
};

/**
 * @param {string} tokenId
 * @param {number} currentTime
 * @return {void}
 */
AuthenticationManager.prototype.renew = function(tokenId, currentTime) {
    
};

/**
 * @param {number} currentTime
 * @return {number}
 */
AuthenticationManager.prototype.countUnexpiredTokens = function(currentTime) {
    
};

Sign in to run your own test cases

Sign in

Design Authentication Manager — Problem & Solution

Design Authentication Manager solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Design Authentication Manager is a medium coding problem on hash table.

  • Difficulty: Medium
  • Topics: Hash Table
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

An authentication system issues tokens that live for timeToLive seconds: a token generated or renewed at time t expires at time t + timeToLive. A renewal pushes the expiry back to timeToLive seconds after the renewal.

Write the class AuthenticationManager:

  • AuthenticationManager(int timeToLive) sets the lifetime of every token.
  • void generate(String tokenId, int currentTime) issues a new token tokenId at currentTime.
  • void renew(String tokenId, int currentTime) renews the token tokenId if it exists and has not expired at currentTime. Renewing a token that does not exist or has already expired does nothing.
  • int countUnexpiredTokens(int currentTime) returns how many tokens are unexpired at currentTime.

Expiry takes effect before anything else: a token that expires exactly at time t is already expired for a renew or a count made at time t.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

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: Renewing aaa at time 1 does nothing — it does not exist yet. aaa is generated at 2 and expires at 7, so it counts at 6, but at 8 it has expired and cannot be renewed. bbb, generated at 7, is renewed at 10 to expire at 15, so at 15 no token is left.

Example 2

Input: ["AuthenticationManager","generate","renew","countUnexpiredTokens","countUnexpiredTokens"]
[[3],["x",1],["x",3],[5],[6]]
Output: [null,null,null,1,0]
Explanation: x is generated at 1 with expiry 4 and renewed at 3 to expiry 6. At 5 it is alive; at 6 it has just expired.

Constraints

  • 1 <= timeToLive <= 10^8
  • 1 <= currentTime <= 10^8
  • 1 <= tokenId.length <= 5
  • tokenId consists of lowercase English letters
  • Every generate call uses a tokenId never generated before
  • The currentTime values of all calls are strictly increasing
  • At most 2000 calls are made to the three methods in total

Hints for Design Authentication Manager

  1. Hint 1

    All a token needs is its expiry time. Keep a map from token id to expiry.

  2. Hint 2

    A token is alive at time t exactly when its expiry is strictly greater than t — that one comparison handles the "expires before anything else" rule.

  3. Hint 3

    renew checks that comparison before moving the expiry; countUnexpiredTokens counts the expiries greater than t (expired entries may be deleted as you go, since times only increase).

How to solve Design Authentication Manager

Store each token's expiry time in a hash map. Every rule in the statement is then one comparison: a token is alive at t iff expiry > t.

Approach

  1. generate(id, t): expiry[id] = t + timeToLive.
  2. renew(id, t): if id is in the map and expiry[id] > t, set expiry[id] = t + timeToLive.
  3. countUnexpiredTokens(t): count the entries with expiry > t. Because times strictly increase, an expired entry can never come back; deleting it while counting keeps the map small.

Why it works

A token issued or renewed at s is alive during [s, s + timeToLive). Since expiry happens before other actions at the same instant, at time t it is alive iff t < s + timeToLive, i.e. expiry > t — for renewals and counts alike.

Complexity

  • Time — O(1) per generate and renew, O(k) per count for k stored tokens
  • Space — O(k)

Pitfalls

  • Using >= keeps a token alive at the very moment it expires; the statement says it is already gone.
  • Renewing an expired token must not bring it back.
  • For counts in O(1) amortised, keep tokens in a list ordered by expiry (renewing moves one to the end) and drop expired ones from the front — the linked-list variant of the same idea.

Reference solution

Python

class AuthenticationManager:

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

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

    def renew(self, tokenId: str, currentTime: int) -> None:
        if self.expiry.get(tokenId, 0) > currentTime:  # alive iff expiry > now
            self.expiry[tokenId] = currentTime + self.ttl

    def countUnexpiredTokens(self, currentTime: int) -> int:
        for k in [k for k, e in self.expiry.items() if e <= currentTime]:
            del self.expiry[k]  # times only increase: expired tokens never return
        return len(self.expiry)

Java

class AuthenticationManager {
    private int ttl;
    private HashMap<String, Integer> expiry = new HashMap<>();

    public AuthenticationManager(int timeToLive) {
        ttl = timeToLive;
    }

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

    public void renew(String tokenId, int currentTime) {
        Integer e = expiry.get(tokenId);
        if (e != null && e > currentTime) expiry.put(tokenId, currentTime + ttl); // alive iff expiry > now
    }

    public int countUnexpiredTokens(int currentTime) {
        expiry.values().removeIf(e -> e <= currentTime); // times only increase: expired tokens never return
        return expiry.size();
    }
}

C++

class AuthenticationManager {
    int ttl;
    unordered_map<string, int> expiry;
public:
    AuthenticationManager(int timeToLive) : ttl(timeToLive) {}

    void generate(string tokenId, int currentTime) {
        expiry[tokenId] = currentTime + ttl;
    }

    void renew(string tokenId, int currentTime) {
        auto it = expiry.find(tokenId);
        if (it != expiry.end() && it->second > currentTime) it->second = currentTime + ttl; // alive iff expiry > now
    }

    int countUnexpiredTokens(int currentTime) {
        for (auto it = expiry.begin(); it != expiry.end();) {
            if (it->second <= currentTime) it = expiry.erase(it); // expired tokens never return
            else ++it;
        }
        return expiry.size();
    }
};

JavaScript

var AuthenticationManager = function(timeToLive) {
    this.ttl = timeToLive;
    this.expiry = new Map();
};

AuthenticationManager.prototype.generate = function(tokenId, currentTime) {
    this.expiry.set(tokenId, currentTime + this.ttl);
};

AuthenticationManager.prototype.renew = function(tokenId, currentTime) {
    var e = this.expiry.get(tokenId);
    if (e !== undefined && e > currentTime) this.expiry.set(tokenId, currentTime + this.ttl); // alive iff expiry > now
};

AuthenticationManager.prototype.countUnexpiredTokens = function(currentTime) {
    var self = this, dead = [];
    this.expiry.forEach(function(e, k) { if (e <= currentTime) dead.push(k); });
    dead.forEach(function(k) { self.expiry.delete(k); }); // times only increase: expired tokens never return
    return this.expiry.size;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 439 hash table problems · the whole catalogue

Learn the technique: Hashing: Hash Maps and Hash Sets