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 valuesint 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.
Candidate's Approach
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; }
Interviewer's Feedback
No feedback provided.