Skip to content

1797. Design Authentication Manager 👍

  • Time: Constructor: $O(1)$, generate(tokenId: str, currentTime: int): $O(\log n)$, renew(tokenId: str, currentTime: int): $O(\log n)$, countUnexpiredTokens(currentTime: int): $O(|\texttt{generate(tokenId: str, currentTime: int)} + \texttt{renew(tokenId: str, currentTime: int)}|)$
  • Space: $O(|\texttt{generate(tokenId: str, currentTime: int)} + \texttt{renew(tokenId: str, currentTime: int)}|)$
 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
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) {
    const auto it = tokenIdToExpiryTime.find(tokenId);
    if (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);
    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
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;
    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
class AuthenticationManager:
  def __init__(self, timeToLive: int):
    self.timeToLive = timeToLive
    self.tokenIdToExpiryTime = {}
    self.times = collections.defaultdict(int)

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

  def renew(self, tokenId: str, currentTime: int) -> None:
    expiryTime = self.tokenIdToExpiryTime.get(tokenId)
    if expiryTime is None or currentTime >= expiryTime + self.timeToLive:
      return
    del self.times[expiryTime]
    self.tokenIdToExpiryTime[tokenId] = currentTime
    self.times[currentTime] += 1

  def countUnexpiredTokens(self, currentTime: int) -> int:
    expiryTimeThreshold = currentTime - self.timeToLive + 1
    for expiryTime in list(self.times.keys()):
      if expiryTime < expiryTimeThreshold:
        del self.times[expiryTime]
    return sum(self.times.values())