Pick the canary window that exposes the fewest users

Agent buildMedium25 min

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:

  • tasks and users: two lists of the same length, 1 to 100,000 slots. Slot i is 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 and users[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 users over its slots, and its tasks the sum of tasks. 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) -> int
Example 1
Inputquiet_window([5, 1, 8, 2], [4, 1, 9, 2], 9)
Output10
Example 2
Inputquiet_window([6, 0, 0, 7], [5, 0, 0, 6], 10)
Output11
Example 3
Inputquiet_window([3, 3], [1, 1], 7)
Output-1