Amazon SDE-1/2/SDE-Intern OA Questions | Amazon OA Questions | Kumar K | August 2026 |Set 241

Question

AWS provides scalable systems. A set of n servers are used for horizontally scaling an application. The goal is to have the computational power of the servers in non decreasing order. To do so, you can increase the computational power of each server in any contiguous segment by x. Choose the values of x such that after the computational powers are in non decreasing order, the sum of the x values is minimum.

 

Example

There are n = 5 servers and their computational power = [3,4,1,6,2]

Add 3 units to then subarray [2,4] and 4 units to the subarray [4,4]. The final arrangement of the servers is: [3,4,4,9,9]. The answer is 3+4 = 7

3 4 1 6 2

          +3 +3 +3

 

3 4 4 9 5

                    +4

 

3 4 4 9 9

 

Function description:

Complete the function findMinimumSum, its has parameter(s)

int power[n]: the computational power of n servers.

Returns:

 int: the minimum possible sum of integers required to make the array non- decreasing

 

Constraint:

1<=n<=10^5

1<=power[i] <=10^9

 

Sample Case 0

Power = [3,2,1], Output : 2

Explanation: Add 1 unit to the subarray [1,2] and 1 unit to subarray [2,2]. The final arrangement of servers is [3,3,3].

 

Sample Case 1

Power = [3,5,2,3], Output: 3

Add 3 units to the subarray [2,3]. The final arrangement o

f servers is [3,5,5,6].

Comments

Key to solve is: sum of all positive adjacent drops.

Answer 1

class Solution {
    public static long findMinimumSum(int[] power) {
        long ans = 0;

        for (int i = 0; i < power.length - 1; i++) {
            if (power[i] > power[i + 1]) {
                ans += (long) power[i] - power[i + 1];
            }
        }

        return ans;
    }
}