Issue and Reuse 16-Bit Tokens
Meta● MediumFULLTIMEONSITE INTERVIEWProblem statement
Implement a token issuer with capacity capacity. Its possible token IDs are the unsigned 16-bit integers 0 through capacity - 1. A token is active after it is issued and before it is returned.
Process operations from left to right. An operation -1 requests a token. If any previously issued token has been returned and is still available, issue the smallest returned token. Otherwise, issue the smallest token that has never been issued, starting from 0. If no token is available, output -1 for that request.
A nonnegative operation t returns token t. Only a currently active token can be returned; a duplicate return, a never-issued token, or a token outside the configured capacity has no effect. Return an array containing one result for each request operation, in request order. Return operations add no result.
Function
issueTokens(capacity: int, operations: int[]) → int[]Examples
Example 1
capacity = 4operations = [-1,-1,-1,1,0,-1,-1,-1]return = [0,1,2,0,1,3]The first three requests issue 0, 1, and 2. After 1 and 0 are returned, the issuer reuses 0 then 1 before issuing fresh token 3.
Example 2
capacity = 2operations = [1,-1,0,0,-1,-1,-1,1,-1]return = [0,0,1,-1,1]The first return of 1 is ignored because 1 was never issued. The repeated return of 0 is ignored. After both tokens are active, the next request is exhausted; returning 1 makes it available again.
Example 3
capacity = 0operations = [-1,-1]return = [-1,-1]Capacity zero has no token to issue.
Constraints
0 <= capacity <= 65536.1 <= operations.length <= 100000.- Each operation is either
-1or an integer from0through65535. - Returning a token that is not active is allowed and has no effect.