Amazon Online Assessment (OA) - Fill The Truck

A Warehouse manager needs to create a shipment to fill a truck. All the products in the warehouse are in boxes of the same size. Each product is packed in some number of units per box.

Given the number of boxes, the truck can hold, write an algorithm to determine the maximum number of units of any mix of products that can be shipped.

Input

The input consists of five arguments:

num: an integer representing the number of products

boxes: a list of integers representing the number of available boxes for products

unitSize: an integer representing size of unitsPerBox

unitsPerBox: a list of integers representing the number of units packed in each box

truckSize: an integer representing the number of boxes the truck can carry.

Output

Return an integer representing the maximum units that can be carried by truck.

Constraints

1 <= |boxes| <= 10^5

|boxes| == |unitsPerBox|

1 <= boxes[i] <= 10^7

1 <= i <= |boxes|

1 <= unitsParBox[i] <= 10^5

1 <= j <= |unitsPerBox|

1 <= truckSize <= 10 ^ 8

Examples

Example 1:

Input:

num = 3

boxes = [1, 2, 3]

unitSize = 3

unitsPerBox = [3, 2, 1]

truckSize = 3

Output: 7
Explanation:

Product 0: because boxes[0] = 1, we know there is 1 box in product 0. And because unitsPerBox[0] = 3, we know there is 1 box with 3 units in product 0.

Product 1: 2 boxes with 2 units each

Product 2: 3 boxes with 1 unit each

Finally, we have packed products like a list: [3, 2, 2, 1, 1, 1]

The truckSize is 3, so we pick the top 3 from the above list, which is [3, 2, 2], and return the sum 7.

The maximum number of units that can be shipped = 3 + 2 + 2 = 7 units

Try it yourself

Solution

The problem is fairly straightforward. We want to use as many boxes with large units as possible. We can simply sort the boxes by how many units it can contain and start fill the truck until it's full.

1
1
from typing import List
2
2
3
3
def fill_the_truck(num: int, boxes: List[int], unit_size: int, units_per_box: List[int], truck_size: int) -> int:
4
-
    # WRITE YOUR BRILLIANT CODE HERE
4
+
    ans = 0
5
-
    return 0
5
+
    boxes_left = truck_size
6
+
    for units, box in sorted(zip(units_per_box, boxes), reverse=True):
7
+
        box = min(boxes_left, box)
8
+
        ans += box * units
9
+
        boxes_left -= box
10
+
        if boxes_left == 0:
11
+
            break
12
+
    return ans
13
+
6
14
if __name__ == '__main__':
7
15
    num = int(input())
8
16
    boxes = [int(x) for x in input().split()]
9
17
    unit_size = int(input())
10
18
    units_per_box = [int(x) for x in input().split()]
Expand 3 lines ...