This question is asked during an online interview:
There is a service with n servers and the i’th server has a processing power of server[i] units.
A user can assign k different tasks to any contiguous segment of servers from index i to (i+k-1) for any valid index i.
To ensure consistent behavior, we want the sums of processing powers of any of these subarrays to be equal.
To achieve this, we can replace any server with a new server of any processing power.
Given the array server and an integer, k, find the minimum number of servers that must be replaced such that every contiguous subarray of k servers has an equal sum of processing powers.
- Example
Suppose n = 4, server = [1, 2, 3, 2], and k = 2.
contiguous sum are [(1,2), (2,3), (3,2)] = [3,5,5]
It is optimal to replace only the first server, => [3,2,3,2] , the contiguous sum are now [(3,2), (2,3), (3,2)] = [5,5,5]
so the answer is 1.
2. Example suppose n = 5, server = [1,2,1,1,2], k = 3
contiguous sum = [(1,2,1), (2,1,1), (1,1,2)] = [4,4,4], so answer is 0
The is the code :
public static void main(String[] args) {
System.out.println(solve(2, Arrays.asList(1,2,3,2))); // correct is 1
System.out.println(solve(2, Arrays.asList(1,2,3))); // correct is 2
System.out.println(solve(3, Arrays.asList(1,2,1,1,2))); // correct is 0
}
private static int solve(int k, List<Integer> server) {
// here is my code, which fails for 2nd test case.
long sum = 0;
for(int i=0; i<k; i++) sum += server.get(i); // get sum of k items
long current = sum; // assign that to current
int result = 0;
int n = server.size();
for(int i=1; i<=n-k; i++) {
current += server.get(i+k-1) - server.get(i-1); // get group sum that starts with i
if(current != sum) result++; // found difference
if(current > sum) sum = current; // update sum if it is less than current
}
return result;
}
In my code, I have made an assumption that for a group starting with i, the replacement will be done at server[i] only, but this assumption is not correct for this task. What is the correct approach to solve this problem.