FastPrep
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.

More Amazon problems

drafts saved locally
public int minStorageCost(int n, int encCost, int flatCost, int[] sensitiveFiles) {
  // write your code here
}
n2
encCost2
flatCost1
sensitiveFiles[1,3]
expected6
checking account