How should I practice Choose Containers?

Start by reading the full statement, solve the visible examples, then compare the pattern against related IMC online assessment problems in FastPrep.

Is Choose Containers associated with IMC?

FastPrep tags this as a IMC coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Array

Choose Containers

Learn this problem

● MediumIMCOA

Problem statement

You work for a pharmaceutical company that produces liquid medicine. Patients requiring these medications often require different amounts. To package the medication for delivery, you can choose between different sets of containers. Each container set specifies the sizes of containers it allows. For example, set 1 might offer containers with size 300 ml and 200 ml, while set 2 might offer containers with sizes 400 ml, 250 ml, and 100 ml.

When fulfilling a customer order for a given amount, a single container must be used and filled completely. If a container does not exist that matches the required amount, the next largest container is used. The extra medication included in that larger container, i.e. size of the container - required amount, is considered waste.

Your job is to evaluate different sets of containers and identify the set of containers that will minimize the total waste for a given collection of orders.

Return the zero-based index of the set of containers which minimizes the overall waste. If multiple sets provide the same minimum waste, return the lower index. If no set satisfies the required amounts, return -1.

Container data

The requirements array contains the requested sizes, and numContainerSets is the number of container sets. Each row of containers stores a container-set index followed by one container size.

The containers rows are given in set order: the sizes for set 0 are followed by the sizes for set 1, and so on. Within each set, the sizes are sorted in ascending order.

Function

chooseContainers(requirements: int[], numContainerSets: int, containers: int[][]) → int

Examples

Example 1

requirements = [4, 6, 6, 7]numContainerSets = 3containers = [[0, 3], [0, 5], [0, 7], [1, 6], [1, 8], [1, 9], [2, 3], [2, 5], [2, 6]]return = 0

The containers array is a 2D array where the first element is the container set id and the second is the size. In this case, the first set, id 0, has three containers with sizes 3, 5, and 7. The second set has containers with sizes 6, 8, and 9, and the third set has sizes 3, 5, and 6.

Using the first set, the losses are:

5 - 4 = 1
7 - 6 = 1
7 - 6 = 1
7 - 7 = 0

The total waste is 1 + 1 + 1 + 0 = 3 units.

Using the second set type, the losses are:

6 - 4 = 2
6 - 6 = 0
6 - 6 = 0
8 - 7 = 1

The total waste is 2 + 0 + 0 + 1 = 3 units.

The third set cannot be used because its maximum capacity is 6 and there is a requirement for 7.

Two sets of containers can be used that each result in 3 wasted units. The lower index set is at index 0.

Constraints

1 <= n <= 10^5
1 <= numContainerSets <= 10^9
1 <= totalNumContainers <= 10^5