Amazon Online Assessment (OA) - Minimum Total Container Size

You want to move N items in k days (N >= k). You have to move at least one item per day. The items are listed in array P, where P[i] is size of item i. You can move item i only if all items from 0 to [i - 1] are already moved. Every day you need a container to pack the item and move it. The container size needed for day i is the maximum item size moved on that day.

Given k days and array P as the item sizes, find out the minimum total container size required to move all the items.

Examples

Example 1:

Input: P = [10, 2, 20, 5, 15, 10, 1], d = 3
Output: 31
Explanation:
  • day 1 - [10, 2, 20, 5, 15]. ContainerSize = 20
  • day 2 - [10]. ContainerSize = 10
  • day 3 - [1]. ContainerSize = 1

Total = 20 + 10 + 1 = 31

Example 2:

Input: P = [10, 2, 20, 5, 15, 10, 1], d = 5
Output: 43
Explanation:
  • day 1 - move [10]. ContainerSize = 10
  • day 2 - move [2]. ContainerSize = 2
  • day 3 - move [20, 5, 15]. ContainerSize = 20
  • day 4 - move [10]. ContainerSize = 10
  • day 5 - move [1]. ContainerSize = 1

Total = 10 + 2 + 20 + 10 + 1 = 43

Example 3:

Input: P = [5, 4, 2, 4, 3, 4, 5, 4], d = 4
Output: 16
Explanation:
  • day 1 - [5, 4], containerSize = 5
  • day 2 - [2], containerSize = 2
  • day 3 - [4, 3], containerSize = 4
  • day 4 - [4, 5, 4], containerSize = 5
  • day 5 - move [1]. ContainerSize = 1

Total = 5 + 2 + 4 + 5 = 16

Example 4:

Input: P = [22, 12, 1, 14, 17], d = 2
Output: 39
Explanation:
  • day 1 - [22, 12], containerSize = 22
  • day 2 - [1, 14, 17], containerSize = 17

Total = 22 + 17 = 39

Try it yourself

Solution

Assume 0-based indexing and left-inclusive, right-exclusive ranges.

Imagine we have moved i items in total after d days, and the total container size we have used is s(d, i). Notice that for fixed i and d, having a lower s is always better than a higher s (since the available choices for later days are the same).

For d > 0, we must have moved some number of items during the last day, let's say k items. Then s(d, i) is the sum of s(d - 1, i - k) (the total container size when we moved i - k items after d - 1 days) and the max of container sizes from item i - k to item i (container size we used during the last day). So the minimum possible s(d, i) is the minimum of all s(d - 1, i - k) + max(sizes[i - k..i]) for all k in 1..i + 1 (at least 1 every day, and at most all items).

For d = 0, we haven't moved anything yet, so s(d=0, i=0) = 0 (total container size 0), and s(d=0, i) is impossible for i != 0 (moved non-0 items in 0 days) which we will represent with infinity / int max (since we want minimum).

So we have an recurrence relation:

  • s(d=0, i=0) = 0
  • s(d=0, i!=0) = inf
  • s(d!=0, i) = min(s(d - 1, i - k) + max(sizes[i - k..i]) for k = 1..i + 1)

We can write this out as a (memoized) recursive function (top-down dynamic programming):

1
+
from functools import lru_cache
2
+
from math import inf
1
3
from typing import List
2
4
3
5
def min_container_size(item_sizes: List[int], days: int) -> int:
4
-
    # WRITE YOUR BRILLIANT CODE HERE
6
+
    @lru_cache
5
-
    return 0
7
+
    def dfs(day: int, item: int) -> int:
8
+
        if day == 0:
9
+
            return 0 if item == 0 else inf
10
+
11
+
        # min total container size
12
+
        res = inf
13
+
        # number of items moved during the last day
14
+
        for last in range(1, item + 1):
15
+
            # max size of items moved during the last day
16
+
            mx = max(item_sizes[item - last:item])
17
+
            # inf + mx = inf, so no need to check
18
+
            res = min(res, dfs(day - 1, item - last) + mx)
19
+
        return res
20
+
21
+
    return dfs(days, len(item_sizes))
22
+
6
23
if __name__ == '__main__':
7
24
    item_sizes = [int(x) for x in input().split()]
8
25
    days = int(input())
9
26
    res = min_container_size(item_sizes, days)
10
27
    print(res)
The above solution will indeed give the correct answer,
but we can do better.
Notice that the value of s on day d
only depends on the values of s on day d - 1.
This means that if we calculate all the s of a day before moving onto the next day
(bottom-up dynamic programming),
we can discard the data from 2 or more days ago and save space.
This reduces the auxiliary space from O(d * |P|) to O(|P|),
where d is the value of input d and |P| is the size of input P
(see pseudo-polynomial).
Another thing to notice is that for each k,
the naive approach of calculating max(sizes[i - k..i]) involves a loop —
but we are already looping through k one by one!
So rather than repeatedly searching for the max of size[i - k..i] for each k,
we keep the current max outsize of the loop,
so when we increment k,
the new max size[i - k..i] is the max of old max and size[i - k].
This reduces the runtime from O(d * |P|^3) to O(d * |P|^2).
Implementation