## Capgemini Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
2
of 2 vote

Sounds like 3-dimensional dynamic programming. The dp function is as follows:
dp[i][j][k] = ((dp[i + 1][j][!k] + num[i]) + (dp[i][j - 1][!k] + num[j] )) / 2;

``````Here I will explain the function I wrote.  It is 3 dimensional dynamic programming.
Let's say we have an array called num[N] which contains the importance levels.

Then [i - j] is the sub region of array num , e.g 0 - 4, 2-3 and so on. k can only be 0 or 1 representing player 1 or player 2. And dp array stores the average importance.
dp[i][j][k] = ((dp[i + 1][j][!k] + num[i] ) + (dp[i][j - 1][!k] + num[j])) / 2;
This function means that when player k moves and the sub region is from i to j, we can get the answer from its sub problems which are dp[i + 1][j][!k] and dp[i][j - 1][!k].
Let's see an example, dp  can be constructed from d and dp since we can only shoot from the edge.``````

This idea can be easily implemented using 3 loops which I believe any of you can do:)

Here I just provide my implementation

``````public class Test{

public static float getSum(float[] tempSum, int start, int end){
if(start == 0){
return tempSum[end];
}else{
return tempSum[end] - tempSum[start - 1];
}
}

public static void main(String[] args){
float[] num = new float[]{10, 20};
float[][][] dp = new float[num.length][num.length];
float[] tempNum = new float[num.length];
System.arraycopy(num, 0, tempNum, 0, num.length);
for(int i = 1; i < num.length; ++i){
tempNum[i] += tempNum[i - 1];
}
for(int i = 1; i <= num.length; ++i){
for(int j = 0; j <= num.length - i; ++j){
for(int k = 0; k <= 1; ++k){
if(i == 1){
dp[j][j][k] = num[j];
}else{
float total1 = getSum(tempNum, j, j + i - 2);
float total2 = getSum(tempNum, j + 1, j + i - 1);
dp[j][j + i - 1][k] = ((total1 - dp[j][j + i - 2][1 - k] + num[j + i - 1]) + (total2 - dp[j + 1][j + i - 1][1 - k] + num[j])) / 2;
}
}
}
}
System.out.println(dp[num.length - 1]);
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.