Amazon OA Question [getMaxStability]

Round 1

Questions: Given two arrays of integers, availability and reliability, where availability[i] and reliability[i] represent the availability and reliability factors of the ith server, find the maximum possible stability of any subset of servers. The stability is defined as the minimum availability amongst the servers multiplied by the sum of reliabilities of all the servers. Report the answer modulo (10^9 + 7).

Example: Consider the set of servers where reliability = [1, 2, 2] and availability = [1, 1, 3]. The possible subsets of servers are:

Indices         Stability
[0]             => 1 * 1 = 1
[1]             => 1 * 2 = 2
[2]             => 3 * 2 = 6
[0, 1]         => min(1, 1) * (1 + 2) = 3
[0, 2]         => min(1, 3) * (1 + 2) = 3
[1, 2]         => min(1, 3) * (2 + 2) = 4
[0, 1, 2]     => min(1, 1, 3) * (1 + 2 + 2) = 5

The answer is maximum stability for the set of index {2}, answer = 6 % 1000000007 = 6.

Function Description: Complete the function getMaxStability which has the following parameters:

• int reliability[n]: server reliability values
• int availability[n]: server availability values

Returns:

• int: the maximum stability among all possible non-empty subsets, modulo (10^9 + 7)

Constraints:

• 1 ≤ n ≤ 10^5
• 1 ≤ reliability[i], availability[i] ≤ 10^6
• It is guaranteed that lengths of reliability and availability are the same.

public static int getMaxStability(int[] reliability, int[] availability) {
    return rec(new int[]{0}, reliability, availability);
}

static int rec(int[] indices, int[] reliability, int[] availability) {
    int max = Integer.MIN_VALUE;
    if(indices[indices.length-1] >= reliability.length) // BASE CASE: index > len IndexOutOfBound
        return max;

    if (indices.length == 1) {
        max = Math.max(max, availability[indices[0]] * reliability[indices[0]]);
    } else {
        int aMin = Integer.MAX_VALUE;
        int rSum = 0;
        for (int i : indices) {
            aMin = Math.min(aMin, availability[i]);
            rSum += reliability[i];
        }
        max = Math.max(max, aMin*rSum);
    }

    int[] incrementNumber = Arrays.copyOf(indices, indices.length);
    incrementNumber[indices.length-1]++;
    int[] addNumber = Arrays.copyOf(indices, indices.length+1);
    addNumber[indices.length] = indices[indices.length-1]+1;

    max = Math.max(max, rec(incrementNumber, reliability, availability));
    max = Math.max(max, rec(addNumber, reliability, availability));
    return max;
}