How should I practice Maximum Ad Revenue With a Rolling-Window Cap?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Maximum Ad Revenue With a Rolling-Window Cap associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Maximum Ad Revenue With a Rolling-Window Cap

Google● HardFULLTIMEONSITE INTERVIEW

Learn

Problem statement

You are given n video-ad offerings. Offering i occurs at the fixed point timestamp times[i], measured in elapsed minutes, and each selected copy contributes revenues[i]. The timestamps are strictly increasing; their original gaps remain unchanged when offerings are skipped.

Choose copies according to allowRepeats:

If allowRepeats is false, select zero or one copy of each offering.
If allowRepeats is true, select any nonnegative whole number of copies of each offering.
Every copy of offering i contributes its full revenue at the original timestamp times[i]. Copies cannot be moved to other timestamps or extend the timeline. The selected offerings remain in chronological order.

For every real window start s, the sum of selected revenue at timestamps inside the half-open interval [s, s + windowLength) must be at most cap. The left endpoint is included and the right endpoint is excluded. Therefore two timestamps separated by exactly windowLength cannot occur in the same window.

Return the maximum total selected revenue across the entire input. Return only the integer total, not the selected copies. The empty selection is allowed and contributes 0; empty input or no affordable offering therefore returns 0.

Function

maximumAdRevenue(times: int[], revenues: int[], windowLength: int, cap: int, allowRepeats: boolean) → int

Examples

Example 1

times = [1,2,4]revenues = [8,10,3]windowLength = 3cap = 10allowRepeats = falsereturn = 11

Select the 8-revenue offering at minute 1 and the 3-revenue offering at minute 4, for 11 total. Their gap is exactly 3, so no half-open three-minute window contains both. The 10-revenue offering at minute 2 cannot be combined with either other offering, so it gives only 10.

Example 2

times = [1,2,4]revenues = [8,10,3]windowLength = 3cap = 10allowRepeats = truereturn = 17

Select one copy at minute 1 and three copies at minute 4, contributing 8 + 3 * 3 = 17. No three-minute window contains both timestamps. The cap permits at most three copies of the 3-revenue offering. Selecting the 10-revenue offering at minute 2 leaves no capacity for either neighboring timestamp, so that choice cannot improve 17.

Example 3

times = [0,1,10,11]revenues = [2,3,4,3]windowLength = 5cap = 6allowRepeats = truereturn = 12

Select three copies of the 2-revenue offering at minute 0 and two copies of the 3-revenue offering at minute 11. Each group contributes 6; no five-minute window contains both groups. The two windows [0,5) and [10,15) partition all offerings and allow at most 6 each, proving that 12 is optimal.

Constraints

0 <= n == times.length == revenues.length <= 8.
0 <= times[i] <= 10^9, and times[i] < times[i+1] whenever both indices exist.
1 <= revenues[i] <= 100.
1 <= windowLength <= 10^9.
1 <= cap <= 10.
allowRepeats is a boolean. Invalid or unsorted inputs are outside the accepted domain.
All revenues are integers. Even in repeated-selection mode, an offering contributes at most cap, so the answer is at most n * cap <= 80.