Choose container set with minimum total waste

Q: Choose container set with minimum total waste

This question evaluates algorithmic problem-solving and efficiency in array processing, particularly matching requirements to capacities using sorting and search-related techniques.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Imc.

Q: What role is this question designed for?

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

Question

Waste Reduction (Minimum Total Waste Container Set)

A pharmaceutical company prepares liquid medication for multiple patients. Each patient order has a required volume. The company can choose one “container set” to fulfill all orders. A container set contains multiple available container capacities.

Rules for fulfilling an order

For an order with requirement r using a chosen container set:

You must pick exactly one container from the set.
The container must be filled completely .
If a container with capacity exactly r exists, use it (waste = 0).
Otherwise, use the smallest container capacity c such that c >= r .
Waste for this order is c - r .
If a set has no container capacity >= r for any order, that container set is invalid and cannot be chosen.

Task

Given:

requirements[] : volumes required for each order (patients)
containerSets : a list where containerSets[i] is an array of container capacities available in set i

Compute the total waste for each valid set (sum of wastes across all orders). Return:

The 0-based index of the container set with the minimum total waste
If there is a tie, return the smallest index among those tied
If no set can fulfill all orders, return -1

Input/Output

Input: requirements (length m ), and containerSets (length s , each set has one or more capacities)
Output: integer index of the best set, or -1

Notes / Assumptions

Container capacities and requirements are positive integers.
A container set may contain capacities in any order; duplicates may exist.
Constraints can be large (e.g., up to 2e5 total capacities across all sets), so an efficient approach is expected.