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 tokentokenIdatcurrentTime.void renew(String tokenId, int currentTime)renews the tokentokenIdif it exists and has not expired atcurrentTime. Renewing a token that does not exist or has already expired does nothing.int countUnexpiredTokens(int currentTime)returns how many tokens are unexpired atcurrentTime.
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^81 <= currentTime <= 10^81 <= tokenId.length <= 5tokenId consists of lowercase English lettersEvery generate call uses a tokenId never generated beforeThe currentTime values of all calls are strictly increasingAt most 2000 calls are made to the three methods in total
Hints for Design Authentication Manager
Hint 1
All a token needs is its expiry time. Keep a map from token id to expiry.
Hint 2
A token is alive at time
texactly when its expiry is strictly greater thant— that one comparison handles the "expires before anything else" rule.Hint 3
renewchecks that comparison before moving the expiry;countUnexpiredTokenscounts the expiries greater thant(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
generate(id, t):expiry[id] = t + timeToLive.renew(id, t): ifidis in the map andexpiry[id] > t, setexpiry[id] = t + timeToLive.countUnexpiredTokens(t): count the entries withexpiry > 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