There were 3 questions (easy - medium) asked in the OA with a time limit of 1.5 hours.
Question 3 was a the same as Design Authentication Manager, but the the total number of queries was 10^5.
The brute force approach of maintaining a {token-time} map and traversing the entire map for counting unexpired tokens was giving TLE.
I tried using binary search by maintaining a multiset for all expiry times and using the upper bound to find the number of tokens with expire greater than the given time but it gives wrong answer on some test cases, can someone suggest why this is wrong?
public:
unordered_map<string,int> m;
multiset<int> mm;
int tl = 0;
AuthenticationManager(int timeToLive) {
this->tl = timeToLive;
mm.clear();
m.clear();
}
void generate(string tokenId, int currentTime) {
m[tokenId] = currentTime+tl;
mm.insert(m[tokenId]);
}
void renew(string tokenId, int currentTime) {
if (m.find(tokenId)== m.end()){
return;
}
int old = m[tokenId];
m[tokenId] = tl+ currentTime;
mm.erase(mm.find(old));
mm.insert(tl+currentTime);
}
int countUnexpiredTokens(int currentTime) {
auto it = mm.upper_bound(currentTime);
if (it == mm.end()){
return 0;
}
return distance(it, mm.end());
}
};
Comments (2)