FastPrep
Problem · Queue

Ad Rotation Scheduler With Cooldown

Learn this problem
● MediumGoogleNEW GRADONSITE INTERVIEW
See Google hiring insights

Problem statement

You are building an ad rotation scheduler. There are n ads, numbered from 1 to n. Ad i must be shown exactly counts[i - 1] times.

Implement the scheduler by returning the sequence of values that repeated calls to next() would produce.

On each call, the scheduler should choose the next currently available ad in round-robin order. Initially, available ads are ordered by increasing ad ID. After an ad is shown, if it still has remaining displays, it becomes unavailable for its cooldown period and then returns to the back of the available queue.

Cooldown is measured in calls to next(). If ad i is shown on call t, it can be shown again no earlier than call t + cooldowns[i - 1] + 1. If no ad is available on a call but some displays remain, that call returns -1 and time still advances by one call.

Return the full output sequence until all display counts have been consumed. Do not include trailing -1 values after every ad has been shown the required number of times.

Original Interview Report

Onsite 2 was an ad rotation / scheduling problem. Multiple ads each have a display count. Design next(); each call returns the next ad, rotating through ads as evenly as possible, such as 1,2,3,1,2,3, unless only one ad remains.

The follow-up adds cooldown: after an ad is displayed, it must wait for its corresponding cooldown period before it can be displayed again.

Function

scheduleAdsWithCooldown(counts: int[], cooldowns: int[]) → int[]

Examples

Example 1

counts = [2,2,2]cooldowns = [0,0,0]return = [1,2,3,1,2,3]

All ads have no cooldown, so the scheduler cycles through them in round-robin order.

Example 2

counts = [3,1]cooldowns = [0,0]return = [1,2,1,1]

After ad 2 has been used once, only ad 1 remains, so it is returned on the remaining calls.

Example 3

counts = [3]cooldowns = [2]return = [1,-1,-1,1,-1,-1,1]

The only ad must wait two calls after each display. During those waiting calls, no ad is available, so -1 is returned.

Constraints

  • 1 <= counts.length == cooldowns.length <= 2000
  • 0 <= counts[i] <= 2000 for at least one ad
  • 0 <= cooldowns[i] <= 2000
  • The returned sequence length will not exceed 200,000.

More Google problems

drafts saved locally
public int[] scheduleAdsWithCooldown(int[] counts, int[] cooldowns) {
  // write your code here
}
counts[2,2,2]
cooldowns[0,0,0]
expected[1,2,3,1,2,3]
checking account