Choose container set to minimize waste
Company: Imc
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
##### Question
A pharmaceutical company is packaging liquid medicine for shipment. Each customer order has a required volume. The company can choose **exactly one** "container set" and must then fulfill **all** orders using containers **only from that chosen set**.
Each container set defines the capacities of containers available in **unlimited quantity**. For each order you must:
1. Use exactly **one** container from the chosen set.
2. Fill that container **completely** up to the order amount.
3. If a container with capacity **exactly equal** to the order amount exists, use it (waste = 0). Otherwise, use the **smallest** container whose capacity is **greater than** the order amount.
4. The **waste** for an order is `capacity - order_amount`.
If, for some order, **no** container in a set is large enough (no capacity `>= requirement`), then that set is **invalid** and cannot be used at all.
Evaluate every container set and choose the one that:
- Can satisfy **all** orders, **and**
- Has the **minimum total waste**, where total waste is the sum of wasted units over all orders.
If multiple container sets tie on minimum total waste, return the **smallest index** among them. If **no** container set can satisfy all orders, return `-1`.
---
### Input format
The required input is provided to you in one of two equivalent forms (handle whichever your harness gives):
**Form A — flat 2D array grouped by set:**
- An integer `n`: the number of orders.
- An array `requirements[n]`: positive integers where `requirements[i]` is the required volume for the `i`-th order.
- An integer `numContainerSets`: the number of distinct container sets.
- A 2D array `containers[totalNumContainers][2]`, where `containers[k][0]` is the **set index** (`0` to `numContainerSets - 1`) and `containers[k][1]` is a **container capacity** (positive integer) belonging to that set.
- Rows are grouped by set index in increasing order of index.
- Within each set, capacities are listed in **non-decreasing** order.
**Form B — list of capacity arrays:**
- `requirements[]` (length `m`): the volume required for each order.
- `containerSets`: a list where `containerSets[i]` is an array of the container capacities available in set `i`. Capacities may appear in any order and duplicates may exist.
### Constraints
- `1 <= n <= 10^5`
- `1 <= numContainerSets <= 10^5`
- `1 <= totalNumContainers <= 2 * 10^5`
- `1 <= requirements[i] <= 10^9`
- `1 <= capacity <= 10^9`
Your algorithm must be efficient enough to handle inputs at the upper bounds. A naive solution that is `O(n * totalNumContainers)` or worse will time out.
---
### Required function
```text
int chooseContainers(int requirements[n],
int numContainerSets,
int containers[totalNumContainers][2])
```
**Return value:**
- The **0-based index** of the container set with the minimum total waste that satisfies all requirements (smallest index on ties), or
- `-1` if no container set can satisfy all requirements.
---
### Example
```text
n = 4
requirements = [4, 6, 6, 7]
numContainerSets = 3
containers = [
[0, 3], [0, 5], [0, 7], // set 0: capacities {3, 5, 7}
[1, 6], [1, 8], [1, 9], // set 1: capacities {6, 8, 9}
[2, 3], [2, 5], [2, 6] // set 2: capacities {3, 5, 6}
]
```
- **Set 0** `{3, 5, 7}`: 4->5 (waste 1), 6->7 (1), 6->7 (1), 7->7 (0) => total **3**.
- **Set 1** `{6, 8, 9}`: 4->6 (waste 2), 6->6 (0), 6->6 (0), 7->8 (1) => total **3**.
- **Set 2** `{3, 5, 6}`: cannot satisfy requirement 7 (max capacity 6 < 7) => **invalid**.
Set 0 and Set 1 both achieve the minimum total waste of 3, so return the smaller index:
```text
chooseContainers(...) = 0
```
Quick Answer: An IMC software engineer take-home asking you to pick the single container set that fulfills all medicine orders with minimum total waste. It tests ceiling-style binary search, per-set validity checks, smallest-index tie-breaking, and efficient handling of inputs up to 10^5 to avoid an O(n*T) timeout.
A pharmaceutical company fulfills every customer order using containers from exactly ONE chosen container set (containers are available in unlimited quantity). For each order of required volume `r`, you must pick the smallest container capacity `c` in the set with `c >= r`; the waste for that order is `c - r` (0 when an exact match exists). If any order has no capacity `>= r` in a set, that set is invalid and cannot be used.
Given `requirements` (the list of order volumes) and `containerSets` (where `containerSets[i]` is the list of capacities in set `i`, possibly unsorted with duplicates), return the 0-based index of the valid set with the minimum total waste (sum of per-order waste). Break ties by the smallest index. Return `-1` if no set can satisfy all orders.
Example: requirements = [4, 6, 6, 7], containerSets = [[3,5,7], [6,8,9], [3,5,6]]. Set 0 waste = 1+1+1+0 = 3; set 1 waste = 2+0+0+1 = 3; set 2 is invalid (no capacity >= 7). Sets 0 and 1 tie at 3, so return the smaller index 0.
Implement `chooseContainers(requirements, containerSets)`.
Constraints
- 1 <= number of orders (n) <= 10^5
- 1 <= number of container sets <= 10^5
- 1 <= total number of containers <= 2 * 10^5
- 1 <= requirements[i] <= 10^9
- 1 <= capacity <= 10^9
- Total waste can reach ~10^14, so use a 64-bit accumulator (Java long / C++ long long).
Examples
Input: requirements = [4, 6, 6, 7], containerSets = [[3, 5, 7], [6, 8, 9], [3, 5, 6]]
Expected Output: 0
Explanation: Set 0 waste = 1+1+1+0 = 3, set 1 waste = 2+0+0+1 = 3, set 2 invalid (no cap >= 7). Sets 0 and 1 tie at 3, smallest index 0 wins.
Input: requirements = [7], containerSets = [[3, 5, 6], [3, 4, 5]]
Expected Output: -1
Explanation: Neither set has a capacity >= 7, so no set is valid and the answer is -1.
Input: requirements = [5, 5, 5], containerSets = [[5], [6], [10]]
Expected Output: 0
Explanation: Set 0 fits 5 exactly (waste 0 each = total 0), the global minimum, so index 0.
Input: requirements = [10], containerSets = [[20, 12, 11], [11, 50]]
Expected Output: 0
Explanation: Both sets' ceiling for 10 is 11 (waste 1), a tie; the smaller index 0 is returned. Also checks unsorted input.
Input: requirements = [1, 2, 3], containerSets = [[3, 3, 2, 1], [4, 5, 6], []]
Expected Output: 0
Explanation: Set 0 (with a duplicate capacity) fits all exactly for total waste 0; set 2 is empty and skipped.
Input: requirements = [100], containerSets = [[99], [100], [101], [100]]
Expected Output: 1
Explanation: Set 0 invalid (99 < 100); set 1 matches exactly (waste 0); set 2 wastes 1; set 3 also waste 0 but later index, so index 1 wins.
Input: requirements = [2, 8], containerSets = [[10, 3], [9, 9, 9]]
Expected Output: 0
Explanation: Set 0: 2->3 (1), 8->10 (2) = 3; set 1: 2->9 (7), 8->9 (1) = 8. Set 0 has lower waste.
Input: requirements = [1000000000], containerSets = [[1000000000], [999999999]]
Expected Output: 0
Explanation: Boundary value: set 0 matches 1e9 exactly (waste 0); set 1's max 999999999 < 1e9 is invalid, so index 0.
Hints
- For one fixed set, the container for an order of size r is the smallest capacity c with c >= r — a 'ceiling' lookup. Binary search (lower_bound / bisect_left) finds it in O(log K) once the set is sorted.
- Sort and dedupe each set's capacities once, then check r against the set's maximum capacity first: if r exceeds it, the whole set is invalid and you can stop early.
- Use a 64-bit running total (n up to 1e5 times waste up to ~1e9 overflows 32-bit). Iterate sets in index order and update the best only on a STRICT improvement so the smallest index wins ties.