Skip to content

Commit d3dd701

Browse files
haoelhaoel
committed
New Problem Solution -"Design Authentication Manager"
1 parent 500937a commit d3dd701

File tree

2 files changed

+110
-0
lines changed

2 files changed

+110
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,7 @@ LeetCode
1313
|1802|[Maximum Value at a Given Index in a Bounded Array](https://leetcode.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/) | [C++](./algorithms/cpp/maximumValueAtAGivenIndexInABoundedArray/MaximumValueAtAGivenIndexInABoundedArray.cpp)|Medium|
1414
|1801|[Number of Orders in the Backlog](https://leetcode.com/problems/number-of-orders-in-the-backlog/) | [C++](./algorithms/cpp/numberOfOrdersInTheBacklog/NumberOfOrdersInTheBacklog.cpp)|Medium|
1515
|1800|[Maximum Ascending Subarray Sum](https://leetcode.com/problems/maximum-ascending-subarray-sum/) | [C++](./algorithms/cpp/maximumAscendingSubarraySum/MaximumAscendingSubarraySum.cpp)|Easy|
16+
|"1797"|["Design Authentication Manager"](https://leetcode.com/problems/design-authentication-manager/) | [C++](./algorithms/cpp/designAuthenticationManager/DesignAuthenticationManager.cpp)|"Medium"|
1617
|1796|[Second Largest Digit in a String](https://leetcode.com/problems/second-largest-digit-in-a-string/) | [C++](./algorithms/cpp/secondLargestDigitInAString/SecondLargestDigitInAString.cpp)|Easy|
1718
|1793|[Maximum Score of a Good Subarray](https://leetcode.com/problems/maximum-score-of-a-good-subarray/) | [C++](./algorithms/cpp/maximumScoreOfAGoodSubarray/MaximumScoreOfAGoodSubarray.cpp)|Hard|
1819
|1792|[Maximum Average Pass Ratio](https://leetcode.com/problems/maximum-average-pass-ratio/) | [C++](./algorithms/cpp/maximumAveragePassRatio/MaximumAveragePassRatio.cpp)|Medium|

‎algorithms/cpp/designAuthenticationManager/DesignAuthenticationManager.cpp

Lines changed: 109 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
1+
// Source : https://leetcode.com/problems/design-authentication-manager/
2+
// Author : Hao Chen
3+
// Date : 2021-03-22
4+
5+
/*****************************************************************************************************
6+
*
7+
* There is an authentication system that works with authentication tokens. For each session, the user
8+
* will receive a new authentication token that will expire timeToLive seconds after the currentTime.
9+
* If the token is renewed, the expiry time will be extended to expire timeToLive seconds after the
10+
* (potentially different) currentTime.
11+
*
12+
* Implement the AuthenticationManager class:
13+
*
14+
* AuthenticationManager(int timeToLive) constructs the AuthenticationManager and sets the
15+
* timeToLive.
16+
* generate(string tokenId, int currentTime) generates a new token with the given tokenId at
17+
* the given currentTime in seconds.
18+
* renew(string tokenId, int currentTime) renews the unexpired token with the given tokenId at
19+
* the given currentTime in seconds. If there are no unexpired tokens with the given tokenId, the
20+
* request is ignored, and nothing happens.
21+
* countUnexpiredTokens(int currentTime) returns the number of unexpired tokens at the given
22+
* currentTime.
23+
*
24+
* Note that if a token expires at time t, and another action happens on time t (renew or
25+
* countUnexpiredTokens), the expiration takes place before the other actions.
26+
*
27+
* Example 1:
28+
*
29+
* Input
30+
* ["AuthenticationManager", "renew", "generate", "countUnexpiredTokens", "generate", "renew",
31+
* "renew", "countUnexpiredTokens"]
32+
* [[5], ["aaa", 1], ["aaa", 2], [6], ["bbb", 7], ["aaa", 8], ["bbb", 10], [15]]
33+
* Output
34+
* [null, null, null, 1, null, null, null, 0]
35+
*
36+
* Explanation
37+
* AuthenticationManager authenticationManager = new AuthenticationManager(5); // Constructs the
38+
* AuthenticationManager with timeToLive = 5 seconds.
39+
* authenticationManager.renew("aaa", 1); // No token exists with tokenId "aaa" at time 1, so nothing
40+
* happens.
41+
* authenticationManager.generate("aaa", 2); // Generates a new token with tokenId "aaa" at time 2.
42+
* authenticationManager.countUnexpiredTokens(6); // The token with tokenId "aaa" is the only
43+
* unexpired one at time 6, so return 1.
44+
* authenticationManager.generate("bbb", 7); // Generates a new token with tokenId "bbb" at time 7.
45+
* authenticationManager.renew("aaa", 8); // The token with tokenId "aaa" expired at time 7, and 8 >=
46+
* 7, so at time 8 the renew request is ignored, and nothing happens.
47+
* authenticationManager.renew("bbb", 10); // The token with tokenId "bbb" is unexpired at time 10, so
48+
* the renew request is fulfilled and now the token will expire at time 15.
49+
* authenticationManager.countUnexpiredTokens(15); // The token with tokenId "bbb" expires at time 15,
50+
* and the token with tokenId "aaa" expired at time 7, so currently no token is unexpired, so return 0.
51+
*
52+
* Constraints:
53+
*
54+
* 1 <= timeToLive <= 10^8
55+
* 1 <= currentTime <= 10^8
56+
* 1 <= tokenId.length <= 5
57+
* tokenId consists only of lowercase letters.
58+
* All calls to generate will contain unique values of tokenId.
59+
* The values of currentTime across all the function calls will be strictly increasing.
60+
* At most 2000 calls will be made to all functions combined.
61+
******************************************************************************************************/
62+
63+
class AuthenticationManager {
64+
private:
65+
int ttl;
66+
set<pair<int, string>> time_set;
67+
unordered_map<string, int> token_map;
68+
public:
69+
AuthenticationManager(int timeToLive):ttl(timeToLive) { }
70+
71+
void generate(string tokenId, int currentTime) {
72+
token_map[tokenId] = currentTime;
73+
time_set.insert({currentTime, tokenId});
74+
}
75+
76+
void renew(string tokenId, int currentTime) {
77+
//if the token is not found, or the token is expired
78+
if (token_map.find(tokenId) == token_map.end() ||
79+
token_map[tokenId] + ttl <= currentTime ) {
80+
return;
81+
}
82+
time_set.erase({token_map[tokenId], tokenId});
83+
time_set.insert({currentTime, tokenId});
84+
token_map[tokenId] = currentTime;
85+
}
86+
87+
int countUnexpiredTokens(int currentTime) {
88+
return clean(currentTime - ttl);
89+
}
90+
91+
int clean(int expired) {
92+
93+
auto it = time_set.begin();
94+
while(!time_set.empty() && it->first <= expired) {
95+
token_map.erase(it->second);
96+
time_set.erase(it);
97+
it = time_set.begin();
98+
}
99+
return time_set.size();
100+
}
101+
};
102+
103+
/**
104+
* Your AuthenticationManager object will be instantiated and called as such:
105+
* AuthenticationManager* obj = new AuthenticationManager(timeToLive);
106+
* obj->generate(tokenId,currentTime);
107+
* obj->renew(tokenId,currentTime);
108+
* int param_3 = obj->countUnexpiredTokens(currentTime);
109+
*/

0 commit comments

Comments
 (0)