FastPrep
Problem · Array

Experiment Bucket Allocation and Rebalancing

Learn this problem
● MediumPinterest logoPinterestFULLTIMEPHONE SCREEN

Problem statement

An experiment owns bucketCount buckets labeled from 0 through bucketCount - 1. The current allocation is given by groups, where groups[0] is the control group and every later row is an enabled group. A bucket appears in at most one group. Any bucket absent from all rows is currently unallocated.

Rebalance every group to its target percentage from targetPercentages. Each target is guaranteed to produce a whole number of buckets: bucketCount * targetPercentages[i] / 100.

  1. If a group has too many buckets, keep its smallest target-sized prefix after sorting and release the rest.
  2. Process groups in index order. Fill deficits using buckets that were unallocated before the rebalance, in ascending order.
  3. Only after those initially unallocated buckets are exhausted, use released buckets in ascending order.

Return a two-dimensional array whose first row contains every bucket left unallocated after the rebalance. Row i + 1 contains the final sorted allocation for groups[i]. Every returned row must be sorted in ascending order.

Function

rebalanceBuckets(bucketCount: int, groups: int[][], targetPercentages: int[]) → int[][]

Examples

Example 1

bucketCount = 20groups = [[0, 1], [2, 3]]targetPercentages = [25, 25]return = [[10, 11, 12, 13, 14, 15, 16, 17, 18, 19], [0, 1, 4, 5, 6], [2, 3, 7, 8, 9]]

Each group needs five buckets. The initially unallocated buckets are consumed in ascending order and in group-index order, leaving buckets 10 through 19 unallocated.

Example 2

bucketCount = 20groups = [[0, 1, 2, 3, 4, 5, 6, 7], [8]]targetPercentages = [25, 25]return = [[5, 6, 7, 13, 14, 15, 16, 17, 18, 19], [0, 1, 2, 3, 4], [8, 9, 10, 11, 12]]

The control group releases 5, 6, and 7. The enabled group still takes initially unallocated buckets 9 through 12 first, so the released buckets remain unallocated.

Example 3

bucketCount = 20groups = [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], [12, 13, 14, 15, 16, 17]]targetPercentages = [25, 50]return = [[7, 8, 9, 10, 11], [0, 1, 2, 3, 4], [5, 6, 12, 13, 14, 15, 16, 17, 18, 19]]

The enabled group first takes initially unallocated buckets 18 and 19, then takes released buckets 5 and 6. The other released buckets remain unallocated.

Constraints

  • 1 <= bucketCount <= 1000
  • 1 <= groups.length == targetPercentages.length <= 20
  • 0 <= groups[i].length <= bucketCount
  • Every bucket ID is in [0, bucketCount - 1] and appears in at most one input row.
  • 0 <= targetPercentages[i] <= 100, their sum is at most 100, and every product bucketCount * targetPercentages[i] is divisible by 100.

More Pinterest problems

drafts saved locally
public int[][] rebalanceBuckets(int bucketCount, int[][] groups, int[] targetPercentages) {
  // write your code here
}
bucketCount20
groups[[0, 1], [2, 3]]
targetPercentages[25, 25]
expected[[10, 11, 12, 13, 14, 15, 16, 17, 18, 19], [0, 1, 4, 5, 6], [2, 3, 7, 8, 9]]
checking account