You have an array of error rates 10, 2, 3, 5, 1, 7, 4, 8 and position of the element pos = 5.
Find such subarray (could be the whole array) that contains element with specified position, where product of min(subarray) * length(subarray) is maximum. Return -1 in case of error.
I didn't ask the interviewer whether elements are unique, but I guess this is valid to the level of complexity so far.
For the given array the answer is 12 (subarray 7, 4, 8).
Finally I suggested to use two pointers approach, but failed to finalise the idea & code in time.
I had very little chance to come up with something substantial, given that I had 15 minutes till the end of call :/
Below is my O(nlogn) solution which I concluded afterwards...
You can provide your own solution if you want
public static void main(String[] args) {
assert maxUnhealthyServerTime(new int[]{10, 2, 3, 5, 1, 7, 4, 8}, 5) == 12;
assert maxUnhealthyServerTime(new int[]{10, 2, 3, 5, 1, 7, 4, 8}, 4) == 8;
assert maxUnhealthyServerTime(new int[]{5, 4, 2, 10}, 2) == 8;
assert maxUnhealthyServerTime(new int[]{1, 2, 3}, 2) == 4;
assert maxUnhealthyServerTime(new int[]{1, 2, 3, 4, 5, 6}, 3) == 12;
}
public static int maxUnhealthyServerTime(int[] errorRates, int pos) {
if (pos < 0 || errorRates.length == 0 || pos >= errorRates.length) {
return -1;
}
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < errorRates.length; i++) {
map.put(errorRates[i], i);
}
Iterator<Map.Entry<Integer, Integer>> iter = map.entrySet().iterator();
Map.Entry<Integer, Integer> firstEntry = iter.next();
int max = firstEntry.getKey() * errorRates.length;
while (iter.hasNext()) {
Map.Entry<Integer, Integer> next = iter.next();
int curPos = next.getValue();
int curKey = next.getKey();
int left = curPos, right = curPos;
while (left > 0 && errorRates[left] >= curKey) left--;
while (right < errorRates.length && errorRates[right] >= curKey) right++;
left++;
right--;
if (pos <= right && left <= pos) {
max = Math.max(max, curKey * (right - left + 1));
}
}
return max;
}