Assign Ads to Browser Positions

Implement a function that assigns ads to browser positions for a single user.

You are given:

• positions: a list of browser position identifiers, such as "top", "sidebar", or "bottom".
• candidateAds: a list of ads that may be shown. Each ad has:
  • adId: a unique string identifier.
  • perUserLimit: the maximum number of times this ad may be shown to the same user.
• userAdState: a dictionary keyed by adId, where each value is the number of times that ad has already been displayed to this user.

Write a function that returns an assignment of ads to browser positions and updates the user's ad state.

Requirements:

1. Assign ads randomly among eligible candidates.
2. An ad is eligible only if its current display count for this user is less than its perUserLimit.
3. If there are enough eligible ads to fill all positions, do not assign the same ad to more than one position in the same call.
4. If there are fewer eligible ads than positions, assign as many positions as possible. You may reuse an ad only if doing so still respects its remaining per-user limit.
5. Every time an ad is assigned, increment its count in userAdState.
6. Return both the position-to-ad assignment and the updated state.

Example input:

positions = ["top", "middle", "bottom"]

candidateAds = [
  { adId: "ad_a", perUserLimit: 2 },
  { adId: "ad_b", perUserLimit: 1 },
  { adId: "ad_c", perUserLimit: 3 }
]

userAdState = {
  "ad_a": 1,
  "ad_b": 1
}

One valid randomized output could be:

assignments = {
  "top": "ad_c",
  "middle": "ad_a",
  "bottom": null
}

updatedUserAdState = {
  "ad_a": 2,
  "ad_b": 1,
  "ad_c": 1
}

The exact assignment may vary because the selection is random.

Assign Ads to Browser Positions

Implement a function that assigns ads to browser positions for a single user.

You are given:

• positions: a list of distinct browser position identifiers.
• candidateAds: a list of dictionaries. Each dictionary has:
  • adId: a unique string
  • perUserLimit: the maximum number of times this ad may be shown to this user
• userAdState: a dictionary mapping adId to how many times that ad has already been shown to this user
• seed: an integer used to make the random choices deterministic for testing

An ad is eligible if its current count in userAdState is strictly less than its perUserLimit.

Rules:

1. Assign ads using the deterministic pseudo-random rule below.
2. If the number of eligible ads at the start is at least the number of positions, do not use the same ad more than once in this call.
3. If there are fewer eligible ads than positions, assign as many positions as possible. In this case, an ad may be reused only while it still has remaining capacity.
4. Each time an ad is assigned, increment its count in the returned state.
5. If no ad can be assigned to a position, store None for that position.
6. Return both the assignment dictionary and the updated user state.

Deterministic pseudo-random rule:

• Keep a local variable x, initially equal to seed.
• Whenever you need to choose from a pool of size k > 0, update: x = (x * 17 + 11) % 1000003
• Then choose the element at index x % k from the current pool.

Pool construction:

• Always keep ads in the same relative order as they appear in candidateAds.
• If duplicates are forbidden for this call, remove a chosen ad from the pool after assigning it.
• If duplicates are allowed, rebuild the pool before each position using all ads that still have remaining capacity.

Constraints

• 0 <= len(positions) <= 200
• 0 <= len(candidateAds) <= 200
• All values in positions are distinct strings
• All adId values in candidateAds are unique
• 0 <= perUserLimit <= 10^9
• 0 <= userAdState[adId] <= 10^9 for any key present
• If an adId is missing from userAdState, treat its current count as 0

Hints

1. First compute each ad's remaining capacity: perUserLimit - currentCount, but never let it go below 0.
2. Decide once at the beginning whether duplicates are forbidden. If enough unique eligible ads exist, sample without replacement; otherwise, rebuild the eligible pool before each position.