How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at eBay.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at eBay during technical interviews.

Assign Ads to Browser Positions | eBay Coding Question

Assign Ads to Browser Positions

Company: eBay

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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: ```ts 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: ```ts 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.

Quick Answer: This question evaluates algorithmic problem-solving around randomized selection, constraint-based resource allocation, and per-user state management, including enforcing eligibility rules and incrementing display counts.

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

Examples

Input: (['top', 'middle', 'bottom'], [{'adId': 'ad_a', 'perUserLimit': 2}, {'adId': 'ad_b', 'perUserLimit': 1}, {'adId': 'ad_c', 'perUserLimit': 3}], {'ad_a': 1, 'ad_b': 1}, 5)

Expected Output: ({'top': 'ad_a', 'middle': 'ad_c', 'bottom': 'ad_c'}, {'ad_a': 2, 'ad_b': 1, 'ad_c': 2})

Explanation: Initially only `ad_a` and `ad_c` are eligible, so duplicates are allowed. The seeded choices pick `ad_a`, then `ad_c`, then `ad_c` again.

Input: (['left', 'right'], [{'adId': 'a', 'perUserLimit': 1}, {'adId': 'b', 'perUserLimit': 1}, {'adId': 'c', 'perUserLimit': 1}], {}, 1)

Expected Output: ({'left': 'b', 'right': 'c'}, {'b': 1, 'c': 1})

Explanation: There are at least as many eligible ads as positions, so no ad may be repeated in this call. The seeded picks choose `b` first, then `c` from the remaining pool.

Input: (['p1', 'p2'], [{'adId': 'x', 'perUserLimit': 1}], {'x': 1}, 7)

Expected Output: ({'p1': None, 'p2': None}, {'x': 1})

Explanation: The only ad has already reached its per-user limit, so no position can be filled.

Input: ([], [{'adId': 'x', 'perUserLimit': 2}], {'x': 1}, 9)

Expected Output: ({}, {'x': 1})

Explanation: With no positions, nothing is assigned and the state does not change.

Input: (['a', 'b', 'c', 'd'], [{'adId': 'u', 'perUserLimit': 2}, {'adId': 'v', 'perUserLimit': 2}, {'adId': 'w', 'perUserLimit': 1}], {'u': 1}, 2)

Expected Output: ({'a': 'u', 'b': 'v', 'c': 'w', 'd': 'v'}, {'u': 2, 'v': 2, 'w': 1})

Explanation: Only three ads are initially eligible for four positions, so duplicates are allowed. The seeded process fills all four positions while respecting remaining limits.

Input: (['p1', 'p2', 'p3'], [{'adId': 'only', 'perUserLimit': 1}], {}, 4)

Expected Output: ({'p1': 'only', 'p2': None, 'p3': None}, {'only': 1})

Explanation: The single ad can be shown once, so the first position is filled and the rest remain unassigned.

Hints

First compute each ad's remaining capacity: `perUserLimit - currentCount`, but never let it go below 0.
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.

Quick Overview

This question evaluates algorithmic problem-solving around randomized selection, constraint-based resource allocation, and per-user state management, including enforcing eligibility rules and incrementing display counts.