Skip to content

1797. Design Authentication Manager

  • Time: Constructor: $O(1)$, generate(): $O(\log |\texttt{generate()} + \texttt{renew()}|)$, renew(): $O(\log |\texttt{generate()} + \texttt{renew()}|)$, countUnexpiredTokens(): $O(|\texttt{generate()} + \texttt{renew()}|)$
  • Space: $O(|\texttt{generate()} + \texttt{renew()}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class AuthenticationManager {
 public:
  AuthenticationManager(int timeToLive) : timeToLive(timeToLive) {}

  void generate(string tokenId, int currentTime) {
    tokenIdToExpiryTime[tokenId] = currentTime;
    times.emplace(currentTime);
  }

  void renew(string tokenId, int currentTime) {
    if (const auto it = tokenIdToExpiryTime.find(tokenId);
        it == tokenIdToExpiryTime.cend() ||
        currentTime >= it->second + timeToLive)
      return;
    times.erase(tokenIdToExpiryTime[tokenId]);
    tokenIdToExpiryTime[tokenId] = currentTime;
    times.emplace(currentTime);
  }

  int countUnexpiredTokens(int currentTime) {
    const auto it = times.lower_bound(currentTime - timeToLive + 1);
    // Remove expired tokens.
    times.erase(times.begin(), it);
    return times.size();
  }

 private:
  const int timeToLive;
  unordered_map<string, int> tokenIdToExpiryTime;
  set<int> times;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class AuthenticationManager {
  public AuthenticationManager(int timeToLive) {
    this.timeToLive = timeToLive;
  }

  public void generate(String tokenId, int currentTime) {
    tokenIdToExpiryTime.put(tokenId, currentTime);
    times.add(currentTime);
  }

  public void renew(String tokenId, int currentTime) {
    Integer expiryTime = tokenIdToExpiryTime.get(tokenId);
    if (expiryTime == null || currentTime >= expiryTime + timeToLive)
      return;
    times.remove(expiryTime);
    tokenIdToExpiryTime.put(tokenId, currentTime);
    times.add(currentTime);
  }

  public int countUnexpiredTokens(int currentTime) {
    final int expiryTimeThreshold = currentTime - timeToLive + 1;
    // Remove expired tokens.
    times.headSet(expiryTimeThreshold).clear();
    return times.size();
  }

  private final int timeToLive;
  private final Map<String, Integer> tokenIdToExpiryTime = new HashMap<>();
  private final TreeSet<Integer> times = new TreeSet<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from sortedcontainers import SortedSet


class AuthenticationManager:
  def __init__(self, timeToLive: int):
    self.timeToLive = timeToLive
    self.tokenIdToExpiryTime = {}
    self.times = SortedSet()

  def generate(self, tokenId: str, currentTime: int) -> None:
    self.tokenIdToExpiryTime[tokenId] = currentTime
    self.times.add(currentTime)

  def renew(self, tokenId: str, currentTime: int) -> None:
    if tokenId not in self.tokenIdToExpiryTime or \
            currentTime >= self.tokenIdToExpiryTime[tokenId] + self.timeToLive:
      return
    self.times.remove(self.tokenIdToExpiryTime[tokenId])
    self.tokenIdToExpiryTime[tokenId] = currentTime
    self.times.add(currentTime)

  def countUnexpiredTokens(self, currentTime: int) -> int:
    i = self.times.bisect_left(currentTime - self.timeToLive + 1)
    # Remove expired tokens.
    for _ in range(i):
      self.times.remove(self.times[0])
    return len(self.times)