Twitter Online Assessment (OA) 2021 | Authentication Tokens
Most websites that requires user login now utilize a "token" system. Every time a user logs into the website, they are issued a token so that when they go to the website again, they are authenticated with the token so they don't have to log in again. Usually a token has an expiration time so that after certain amount of inactivity, the token is voided.
In this particular system, there are two commands:
0 <token_id> <time>: Generates a token
timeminutes. The token is valid for
expiry_timeminutes unless it is reset. This operation can only be done on a token that does not already exist. If a token with this ID already exist, regardless of whether it is active or expired, nothing happens.
1 <token_id> <time>: Resets the token whose ID is
timeminutes. This operation resets the expiry timer so that this token will be valid for
timeunless it is reset again. The token must exist and be active when this operation is performed. If the token does not already exist, or is already expired, this operation does nothing. A token can be reset multiple times, as long as each time the token is still valid.
Given a list of operations sorted chronologically, determine how many tokens are still active after the final operation.
expiry_time: How long since the token was generated or reset before it expires.
operations: An integer matrix with
nrows. Each row has
time, representing an operation.
- The number of tokens still valid after the final operation.
expiry_time = 4
operations = [[0, 1, 1], [0, 2, 2], [1, 1, 5], [1, 2, 7]]
1 is initialized at
T = 1 and token
2 is initialized at
T = 2.
1 is reset at
T = 5, it is still in the active period, so the token's lifespan
is increased to
T = 5 + 4 = 9. When token
2 is reset at
T = 7, it already expired so
nothing happens. After this operation, only token
1 is still valid.
1 <= expiry_time <= 10^8
1 <= n <= 10^5
1 <= token_id <= 10^8
1 <= T <= 10^8