Previous
AI-assisted engineering/Rolling out agents

Pick the widest canary cohort under a user cap

Agent buildHard40 min

Your task

Before a new version of your agent reaches everyone, it runs on a canary cohort of tenants. Tenants form an account tree, and a sub-account can only get the new version if its parent account has it too, because they share agent settings. You want the cohort to cover as many tenants as possible, to see as many different setups as you can, while exposing at most cap users.

Write widest_cohort(tenants, cap) that returns the size of the largest cohort you can pick.

  • tenants: a list of [name, parent, users], in any order. parent is "" for a top-level account, and otherwise the name of another tenant in the list. Names are unique and parents never form a loop. users is a whole number, 0 or more.
  • cap: a whole number, 0 or more.
  • Return the number of tenants in the largest cohort.

Rules:

  1. A cohort is a set of tenants in which every tenant's parent, if it has one, is also in the set.
  2. The users of the tenants in the cohort add up to at most cap.
  3. There are at most 300 tenants.

Examples

widest_cohort(tenants: list[list], cap: int) -> int
Example 1
Inputwidest_cohort([["a", "", 3], ["b", "", 1], ["c", "", 2]], 3)
Output2
Example 2
Inputwidest_cohort([["org", "", 5], ["team", "org", 0], ["solo", "", 4]], 5)
Output2
Example 3
Inputwidest_cohort([["a", "", 0], ["b", "a", 0], ["c", "a", 2]], 0)
Output2