Pick the canary window that exposes the fewest users
Your task
A canary tries a new version on a small slice of traffic. Yours will take all of one region's live traffic for one unbroken stretch of time, then hand back to the current version. You want it to see enough tasks to judge the version, and to reach as few users as possible while it does. That region's traffic follows the same weekly pattern every week, so you plan from last week's numbers.
Write quiet_window(tasks, users, need) that returns the fewest users a canary window can reach.
Input and output:
tasksandusers: two lists of the same length, 1 to 100,000 slots. Slotiis one stretch of last week, in order, and the week repeats after the last slot.tasks[i]is the number of tasks in that slot andusers[i]the number of users who sent them. Each value is a whole number from 0 to 1,000,000.need: the fewest tasks the canary must see, a whole number from 1 to 100,000,000,000.- Return a whole number.
Rules:
- A window is one or more slots in a row. It may run past the last slot of the week into the first slots, but it never covers a slot twice.
- A window's users are the sum of
usersover its slots, and its tasks the sum oftasks. Count a user again in every slot they appear in. - Return the smallest users sum over windows whose tasks sum is at least
need. Return -1 when no window has enough tasks.
Examples
quiet_window(tasks: list[int], users: list[int], need: int) -> intExample 1
Input
quiet_window([5, 1, 8, 2], [4, 1, 9, 2], 9)Output
10Example 2
Input
quiet_window([6, 0, 0, 7], [5, 0, 0, 6], 10)Output
11Example 3
Input
quiet_window([3, 3], [1, 1], 7)Output
-1