FastPrep
Problem · Dynamic Programming

Efficient Deployments

Learn this problem
● HardSnowflakeINTERNOA
See Snowflake hiring insights

Problem statement

A supercomputer has n processors arranged in a row. Processors are deployed one at a time in any order.

For processor i, its efficiency is:

  • no_adjacent[i] when neither adjacent processor was deployed earlier,
  • one_adjacent[i] when exactly one adjacent processor was deployed earlier,
  • both_adjacent[i] when both adjacent processors were deployed earlier.

The first and last processors have only one adjacent processor. Return the maximum total efficiency over all deployment orders.

Function

getMaximumSum(no_adjacent: int[], one_adjacent: int[], both_adjacent: int[]) → long

Examples

Example 1

no_adjacent = [1, 2, 3, 4]one_adjacent = [4, 4, 2, 1]both_adjacent = [0, 1, 1, 0]return = 14

Deploy processors in the order 4 -> 3 -> 2 -> 1. Their efficiencies are 4, 2, 4, and 4, for a total of 14.

The older source rendering lists 13, but its displayed addition substitutes 3 for one_adjacent[3] = 2. Applying the stated rules and arrays gives 14.

Constraints

  • 2 <= n <= 10^5
  • no_adjacent.length == one_adjacent.length == both_adjacent.length == n
  • 1 <= no_adjacent[i], one_adjacent[i], both_adjacent[i] <= 10^9

More Snowflake problems

drafts saved locally
public long getMaximumSum(int[] no_adjacent, int[] one_adjacent, int[] both_adjacent) {
  // write your code here
}
no_adjacent[1, 2, 3, 4]
one_adjacent[4, 4, 2, 1]
both_adjacent[0, 1, 1, 0]
expected14
checking account