How should I practice Minimum S3 Storage Cost?

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

Is Minimum S3 Storage Cost associated with Amazon?

FastPrep tags this as a Amazon online assessment coding practice problem when the problem catalog has that company and stage context.

Problem

Minimum S3 Storage Cost

Learn this problem

AmazonFULLTIMEOA

See Amazon hiring insights

Problem statement

A batch contains files numbered from 1 to 2^n. Some files are sensitive and require encryption; their indices are given in sensitiveFiles.

For any contiguous batch of M files:

If it contains X > 0 sensitive files, storing the whole batch costs M * X * encCost.
If it contains no sensitive files, storing the whole batch costs flatCost.

If the batch size is even, you may either store the whole batch or split it into two equal contiguous batches and pay the sum of their optimal costs. Return the minimum possible storage cost modulo 1_000_000_007.

Function

minStorageCost(n: int, encCost: int, flatCost: int, sensitiveFiles: int[]) → int

Examples

Example 1

n = 2encCost = 2flatCost = 1sensitiveFiles = [1,3]return = 6

Splitting all the way to single files costs 2 + 1 + 2 + 1 = 6, which is better than keeping the full batch or only splitting once.

Example 2

n = 3encCost = 2flatCost = 1sensitiveFiles = [1,2,3,4,5,6,7,8]return = 16

Every file is sensitive. Splitting into single files gives eight batches, each costing 2.

Example 3

n = 3encCost = 2flatCost = 1sensitiveFiles = [7,1]return = 8

One optimal split is [1], [2], [3,4], [5,6], [7], and [8], for total cost 8.

Constraints

1 <= n <= 3 * 10^5
1 <= encCost, flatCost <= 10^5
1 <= sensitiveFiles.length <= 2^n
Each sensitive file index is between 1 and 2^n.