Rebalance Experiment Buckets with Minimal Reassignment
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Rebalance Experiment Buckets with Minimal Reassignment
### Problem
Implement `rebalanceBuckets(bucketCount, groups, targetPercentages) -> rebalancedGroups`.
The bucket universe is every integer from `0` through `bucketCount - 1`. `groups[0]` is the control group, and later elements are enabled groups. Current allocations are globally unique. Resize every group to its target percentage while preserving existing assignments when possible and using buckets that were originally unallocated before reusing buckets released from an oversized group.
### Function Contract
- `groups` and `targetPercentages` have the same length.
- Group `g` must contain exactly `bucketCount * targetPercentages[g] / 100` buckets after rebalancing.
- Return one sorted integer array per group, in the original group order.
- Buckets not present in the returned groups remain unallocated.
- Do not mutate either input.
Several valid membership sets may have the requested sizes, so use this canonical rule:
1. For each group, keep its lowest existing buckets up to that group's target count. Release any higher excess buckets.
2. Form a fill pool containing all originally unallocated buckets in ascending order, followed by released buckets in ascending order.
3. Visit groups from index `0` upward. Fill each deficit from the front of that pool.
4. Sort every returned group in ascending order.
### Constraints
- `1 <= bucketCount <= 1000`.
- `1 <= groups.length = targetPercentages.length <= 101`.
- Every current bucket is in `[0, bucketCount - 1]` and appears at most once globally.
- Each target percentage is an integer in `[0, 100]`.
- `bucketCount * targetPercentages[g]` is divisible by `100` for every group.
- The target percentages sum to at most `100`.
### Examples
```text
bucketCount = 10
groups = [[0], [1]]
targetPercentages = [20, 20]
rebalancedGroups = [[0, 2], [1, 3]]
```
```text
bucketCount = 10
groups = [[0, 1, 8, 9], [2, 3]]
targetPercentages = [20, 30]
rebalancedGroups = [[0, 1], [2, 3, 4]]
```
For the original 1000-bucket case, control buckets `0` through `99` and enabled-group buckets `100` through `199`, rebalanced to `[20, 20]`, become control buckets `0` through `99` plus `200` through `299`, and enabled buckets `100` through `199` plus `300` through `399`.
```hint Separate two kinds of free bucket
Keep track of buckets that were free before rebalancing separately from buckets released only because a group exceeded its new target.
```
### Requirements
- Meet every target count exactly with no duplicate bucket across outputs.
- Preserve as many current group memberships as the target sizes permit.
- Apply the original-unallocated-first and group-order tie-breaks exactly.
- Aim for `O(bucketCount + A + G)` time and `O(bucketCount + G)` auxiliary space, where `A` is the number of current assignments and `G` is the number of groups.
### Discussion Prompts
1. Why is preserving `min(currentSize, targetSize)` buckets per group the maximum possible preservation?
2. How can a fixed-size owner array avoid sorting arbitrary input groups?
3. How would the contract change if targets were allowed to sum above 100 percent?
Quick Answer: Rebalance experiment buckets to exact target percentages while retaining as many existing assignments as the contract allows. The challenge focuses on canonical tie-breaking, nonmutation, global uniqueness, deterministic reuse of free buckets, and linear-scale bookkeeping.
An experimentation platform splits traffic across a fixed universe of buckets: every
integer from `0` through `bucketCount - 1`. `groups[0]` is the control group and every
later element is an enabled group. Current allocations are globally unique — no bucket
belongs to two groups, and any bucket in no group is currently unallocated.
Implement `rebalanceBuckets(bucketCount, groups, targetPercentages)`. Resize every group
to its target percentage while preserving as many existing assignments as the target
sizes permit, and consume buckets that were originally unallocated before reusing buckets
released from an oversized group.
### Output
Return one list per group, in the original group order. Group `g` must contain exactly
`bucketCount * targetPercentages[g] / 100` buckets (the constraints guarantee this
division is exact). Every returned list is sorted in ascending order. A group whose
target count is `0` returns an empty list but still occupies its slot in the result.
Buckets that appear in no returned group remain unallocated. Neither input may be
mutated.
### Canonical rule
Several different membership sets can have the requested sizes, so the answer is pinned
by this exact procedure:
1. For each group, keep its **lowest-valued** existing buckets, up to that group's target
count. Release any higher excess buckets. "Lowest" is by bucket value, not by position
in the input list — an input group may be given in any order.
2. Build a fill pool: **all originally unallocated buckets in ascending order, followed by
all released buckets in ascending order.** Originally unallocated means unallocated
before rebalancing began; a bucket released in step 1 is never treated as originally
unallocated.
3. Visit groups from index `0` upward. Fill each group's deficit by taking buckets from
the **front** of that pool.
4. Sort every returned group in ascending order.
### Example 1
```text
bucketCount = 10
groups = [[0], [1]]
targetPercentages = [20, 20]
Output: [[0, 2], [1, 3]]
```
Both targets are `10 * 20 / 100 = 2`. Each group keeps its one existing bucket and needs
one more. Nothing is released, so the pool is `[2, 3, 4, 5, 6, 7, 8, 9]`. Group `0` is
filled first and takes `2`; group `1` then takes `3`.
### Example 2
```text
bucketCount = 10
groups = [[0, 1, 8, 9], [2, 3]]
targetPercentages = [20, 30]
Output: [[0, 1], [2, 3, 4]]
```
Targets are `2` and `3`. Group `0` is oversized: it keeps its lowest two buckets `0` and
`1` and releases `8` and `9`. Group `1` keeps `2` and `3` and needs one more. The pool is
`[4, 5, 6, 7]` (originally unallocated) followed by `[8, 9]` (released), so group `1`
takes `4` — not `8`, and not `9`.
Constraints
- 1 <= bucketCount <= 1000
- The bucket universe is every integer from 0 through bucketCount - 1
- 1 <= groups.length == targetPercentages.length <= 101
- Every currently assigned bucket is an integer in [0, bucketCount - 1] and appears at most once across all groups (allocations are globally unique)
- A group may be empty, both before and after rebalancing
- Each targetPercentages[g] is an integer with 0 <= targetPercentages[g] <= 100
- bucketCount * targetPercentages[g] is divisible by 100 for every group g
- The target percentages sum to at most 100, so buckets may be left unallocated
Examples
Input: (10, [[0], [1]], [20, 20])
Expected Output: [[0, 2], [1, 3]]
Input: (10, [[0, 1, 8, 9], [2, 3]], [20, 30])
Expected Output: [[0, 1], [2, 3, 4]]
Hints
- A fixed-size array indexed by bucket, holding the owning group (or a sentinel for unallocated), lets you answer 'who owns this bucket?' in O(1) without sorting any input group.
- One ascending sweep over the whole universe visits each group's buckets in increasing order, which is exactly the order the keep-the-lowest rule needs.
- The two kinds of free bucket are not interchangeable. Collect them separately during that sweep and concatenate them in the required order rather than merging them into one sorted list.