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 | + |
| |
2 | + |
| |
1 | 3 |
| |
2 | 4 | ||
3 | 5 |
| |
4 | - |
| |
6 | + |
| |
5 | - |
| |
7 | + |
| |
8 | + |
| |
9 | + |
| |
10 | + | ||
11 | + |
| |
12 | + |
| |
13 | + |
| |
14 | + |
| |
15 | + |
| |
16 | + |
| |
17 | + |
| |
18 | + |
| |
19 | + |
| |
20 | + | ||
21 | + |
| |
22 | + | ||
6 | 23 |
| |
7 | 24 |
| |
8 | 25 |
| |
9 | 26 |
| |
10 | 27 |
|
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)
.