Salesforce | MTS | OA

Round 1

Questions: A software development firm is hiring engineers and used the following challenge in its online test.

Given an array arr that contains n integers, the following operation can be performed on it any number of times (possibly zero):

• Choose any index i (0 ≤ i < n - 1) and swap arr[i] and arr[i + 1].
• Each element of the array can be swapped at most once during the whole process.

The strength of an index i is defined as (arr[i] × (i + 1)), using 0-based indexing. Find the maximum possible sum of the strength of all indices after optimal swaps. Mathematically, maximize the following:

Example
Consider n = 4, arr = [2, 1, 4, 3].
It is optimal to swap (arr [2], arr[3]) and (arr[0], arr[1]). The final array is [1, 2, 3, 4]. The sum of strengths = (1×1 + 2×2 + 3×3 + 4×4) = 30, which is maximum possible. Thus, the answer is 30.

Function Description
Complete the function getMaximumSumOfStrengths in the editor below.

getMaximumSumOfStrengths has the following parameter:

• int arr[n]: the initial array

Returns
long_int: the maximum possible sum of strengths of all indices after the operations are applied optimally

Constraints

• 1 ≤ n ≤ 10^5
• 1 ≤ arr[i] ≤ 10^5

Sample Case 0
Sample Input for Custom Testing

STDIN         FUNCTION
-----         --------
5        →    arr[] size, n = 5
1        →    arr = [1, 9, 7, 3, 2]
9
7
3
2

Sample Output

66

Explanation
It is optimal to swap (arr[2], arr[3]). The final array is arr[] = [1, 9, 3, 7, 2]. The sum of strengths = (1×1 + 2×9 + 3×7 + 4×3 + 5×2) = 66.

Sample Case 1
Sample Input for Custom Testing

STDIN         FUNCTION
-----         --------
3        →    arr[] size, n = 3
1        →    arr = [1, 2, 5]
2
5

Sample Output

20

Explanation
No swaps are needed in this case. The sum of strengths = (1×1 + 2×2 + 3×5) = 20.

Working Solution

public static long getMaximumSumOfStrengths(List<Integer> arr) {
    int n = arr.size();
    if (n == 0) return 0;

    // dp array to store the maximum strength sum up to index i
    long[] dp = new long[n];

    // Initialize the first index
    dp[0] = arr.get(0) * 1; // 0-based index, so (0 + 1)

    // Fill the dp array
    for (int i = 1; i < n; i++) {
        // Calculate the strength if no swap
        dp[i] = dp[i - 1] + arr.get(i) * (i + 1);

        // Calculate the strength if we swap arr[i] with arr[i-1]
        // Swap operation is only possible if i > 0
        if (i >= 1) {
            long swapStrength = (i >= 2 ? dp[i - 2] : 0) + arr.get(i - 1) * (i + 1) + arr.get(i) * i;
            dp[i] = Math.max(dp[i], swapStrength);
        }
    }

    // The result is the maximum strength sum for the full array
    return dp[n - 1];
}

Candidate's Approach

No approach provided.

Interviewer's Feedback

No feedback provided.

---