List Unallocated Experiment Buckets
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## List Unallocated Experiment Buckets
### Problem
An experiment system divides traffic into numbered buckets. Implement `findUnallocatedBuckets(bucketCount, groups) -> buckets`.
The bucket universe is every integer from `0` through `bucketCount - 1`. `groups[0]` is the control group, and every later element is an enabled group. A bucket may belong to at most one group.
Return every bucket that is not allocated to any group.
### Function Contract
- `bucketCount` is an integer.
- `groups` is a JSON-compatible array of integer arrays.
- Return a JSON-compatible integer array sorted in strictly increasing order.
- Do not mutate `groups` or any nested array.
- The original fixed-size case uses `bucketCount = 1000`, representing buckets `0` through `999`.
### Constraints
- `1 <= bucketCount <= 1000`.
- `1 <= groups.length <= 101`.
- Every listed bucket is in `[0, bucketCount - 1]`.
- No bucket is repeated within a group or across different groups.
- Groups may be empty.
### Examples
```text
bucketCount = 6
groups = [[0, 2], [1, 4]]
buckets = [3, 5]
```
```text
bucketCount = 5
groups = [[], [0, 1, 2, 3, 4]]
buckets = []
```
```hint Ignore group identity for this pass
For the unallocated result, it matters whether a bucket appears anywhere, not which control or enabled group contains it.
```
### Requirements
- Produce each unallocated bucket exactly once in ascending order.
- Aim for `O(bucketCount + A)` time, where `A` is the total number of allocated bucket entries.
- Use `O(bucketCount)` auxiliary space or explain an equivalent fixed-universe representation.
### Discussion Prompts
1. How would validation change if the same bucket could accidentally appear in two groups?
2. What representation is convenient because the universe has at most 1000 buckets?
3. Why should the output ordering be specified even though allocation membership is set-like?
Quick Answer: Identify every unallocated bucket in a fixed experiment-traffic range after considering control and enabled-group assignments. This problem examines efficient membership tracking, duplicate-safe output, ascending order, boundary cases, and clear complexity reasoning.
An experiment system divides traffic into numbered buckets. The bucket universe
is every integer from `0` through `bucketCount - 1`.
`groups[0]` is the control group and every later element is an enabled group.
Each inner array lists the bucket ids that group has been allocated. A bucket
belongs to at most one group, and a group may be empty.
Implement `findUnallocatedBuckets(bucketCount, groups)` returning every bucket
that is not allocated to any group.
## Output semantics
- Return an integer array sorted in **strictly increasing** order.
- Each unallocated bucket appears **exactly once**; if every bucket is
allocated, return an empty array.
- Group identity is irrelevant to the answer: a bucket counts as allocated when
it appears anywhere in `groups`, whether that is the control group or an
enabled group.
- Do not mutate `groups` or any nested array.
- Bucket ids inside a group may appear in any order; the returned array must be
ascending regardless.
Every bucket id is at most `999`, so 32-bit signed integers are sufficient in
every language and no wide-integer handling is needed.
## Examples
```text
bucketCount = 6
groups = [[0, 2], [1, 4]]
result = [3, 5]
```
Buckets 0, 1, 2 and 4 are allocated, so 3 and 5 remain.
```text
bucketCount = 5
groups = [[], [0, 1, 2, 3, 4]]
result = []
```
The control group is empty and the enabled group covers the whole universe, so
no bucket is unallocated.
Constraints
- 1 <= bucketCount <= 1000
- 1 <= groups.length <= 101
- Every listed bucket is in [0, bucketCount - 1]
- No bucket is repeated within a group or across different groups
- Groups may be empty
- Implied by the uniqueness rule: the total number of allocated bucket entries is at most bucketCount, and every bucket id fits in a 32-bit signed integer (maximum id 999)
Examples
Input: (6, [[0, 2], [1, 4]])
Expected Output: [3, 5]
Input: (5, [[], [0, 1, 2, 3, 4]])
Expected Output: []
Hints
- Group identity never changes the answer: a bucket is allocated if it appears anywhere in groups, and unallocated otherwise.
- The universe is small and fixed at at most 1000 ids, so you can afford one slot per bucket instead of searching the groups again for each id.
- If you scan the universe in increasing id order at the very end, the required ascending output falls out with no sort step.