Design Authentication Manager

medium hash table design simulation

Problem

Design an AuthenticationManager with a fixed timeToLive. generate(tokenId, t) creates a token that expires at t + timeToLive. renew(tokenId, t) extends an unexpired token's expiry to t + timeToLive (ignored otherwise). countUnexpiredTokens(t) returns how many tokens have not yet expired. A token expiring exactly at time t is already gone for any action at t.

Inputttl = 5; renew("aaa",1); generate("aaa",2); count(6); generate("bbb",7); renew("aaa",8); renew("bbb",10); count(15)

Output[null, null, null, 1, null, null, null, 0]

"aaa" expires at 7; counted at 6 → 1. At 8 it is already gone, so renew is ignored. "bbb" is renewed at 10 to expire at 15; at 15 it is already gone → 0.

timeToLive

operations (op:token:time, comma-separated; count:_:time)

class AuthenticationManager:
    def __init__(self, timeToLive: int):
        self.ttl = timeToLive
        self.expiry = {}                       # tokenId -> expiry time

    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:
            self.expiry[tokenId] = currentTime + self.ttl

    def countUnexpiredTokens(self, currentTime: int) -> int:
        return sum(1 for e in self.expiry.values() if e > currentTime)

class AuthenticationManager {
  constructor(timeToLive) {
    this.ttl = timeToLive;
    this.expiry = new Map();               // tokenId -> expiry time
  }
  generate(tokenId, currentTime) {
    this.expiry.set(tokenId, currentTime + this.ttl);
  }
  renew(tokenId, currentTime) {
    if ((this.expiry.get(tokenId) || 0) > currentTime) {
      this.expiry.set(tokenId, currentTime + this.ttl);
    }
  }
  countUnexpiredTokens(currentTime) {
    let count = 0;
    for (const e of this.expiry.values()) if (e > currentTime) count++;
    return count;
  }
}

class AuthenticationManager {
    private int ttl;
    private Map<String, Integer> expiry = new HashMap<>();
    public AuthenticationManager(int timeToLive) {
        this.ttl = timeToLive;
    }
    public void generate(String tokenId, int currentTime) {
        expiry.put(tokenId, currentTime + ttl);
    }
    public void renew(String tokenId, int currentTime) {
        if (expiry.getOrDefault(tokenId, 0) > currentTime) {
            expiry.put(tokenId, currentTime + ttl);
        }
    }
    public int countUnexpiredTokens(int currentTime) {
        int count = 0;
        for (int e : expiry.values()) if (e > currentTime) count++;
        return count;
    }
}

class AuthenticationManager {
    int ttl;
    unordered_map<string, int> expiry;       // tokenId -> expiry time
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;
    }
    int countUnexpiredTokens(int currentTime) {
        int count = 0;
        for (auto& kv : expiry) if (kv.second > currentTime) count++;
        return count;
    }
};

Explanation

The whole system is just a hash map from tokenId to the absolute time at which that token expires. Storing the expiry instead of the creation time means every query is a simple comparison against currentTime — no recomputation needed.

generate is unconditional: a brand-new token is born and we record expiry[tokenId] = currentTime + ttl. Because all generate calls use unique ids, this never clobbers a live token by accident.

renew must first check that the token is still alive. A token is unexpired only if its stored expiry is strictly greater than currentTime (the rule "expiry at time t happens before other actions at t" makes the comparison strict). If alive, we push its expiry out to currentTime + ttl; otherwise the call is silently ignored.

countUnexpiredTokens scans the map and counts entries whose expiry is strictly greater than currentTime. Expired entries can simply be left in the map — they never count and may be overwritten later by a fresh generate.

Each generate and renew is O(1); a count is O(n) over the stored tokens. The strict > comparison is the single subtle detail that makes the example return 0 at time 15 rather than 1.

Time: O(1) generate/renew, O(n) count Space: O(n)