Ad Score Scheduler With Delay
Learn this problem
GoogleFULLTIMEONSITE INTERVIEWProblem statement
Process the operations in operations against an advertisement scheduler. Each operation is one of:
INSERT id score delay: insert a new advertisement with a unique identifier, its current integer score, and a nonnegative delay.GET: return the eligible advertisement with the highest current score. If several eligible ads have the same score, return the lexicographically smallest identifier. After an ad is returned, decrease its score by1.
An advertisement returned by a GET cannot be returned on the next max(1, delay) GET calls. This guarantees that the same advertisement is never returned consecutively, even when its declared delay is 0. Calls that return no ad still count toward every waiting period.
If no advertisement is eligible, return NONE. Inserted advertisements remain registered for the rest of the simulation. Return the result of every GET operation in order.
Function
runAdScheduler(operations: String[]) → String[]Examples
Example 1
operations = ["INSERT alpha 5 0","INSERT beta 4 0","GET","GET","GET"]return = ["alpha","beta","alpha"]alpha wins the first call and its score becomes 4. It cannot repeat immediately, so beta is returned next. On the third call, alpha is eligible again and has the larger score.
Example 2
operations = ["INSERT a 10 2","INSERT b 5 0","GET","GET","GET","GET"]return = ["a","b","NONE","a"]After the first result, a must sit out two calls. After the second result, b must sit out one call, so the third call has no eligible ad. Both are eligible by the fourth call, and a has the larger score.
Constraints
1 <= operations.length <= 100000- Every operation is exactly
GETor has the formINSERT id score delay. - Each identifier contains
1through20lowercase English letters and is inserted exactly once. -1000000000 <= score <= 10000000000 <= delay <= operations.length