## Salesforce Interview Question

Software Engineer / DevelopersDynamic Programming may be one solution. I googled and found it. If you do not understand the below solution, please google it.

S[i,j] be an array of coins and that is coins from 0..........i-1 and j+1 ........n have already been picked up. We have coins i through j remaining coins to pick. And it now our chance to pick.

Representation of S: S[ .......,i,......j,......]

If it is our move, we have cleverly pick such that the neighbor sum is minimized.

Case A: when we have picked 'i' from the available coins i through j. Then Neighbor has a chance to pick coin at (i+1)th or jth location. His resultant value would be either S[i+2, j] or S[i+1, j-1]. We have to minimize this result.

A = Min {S[i+2, j], S[i+1, j-1]} + coin value. This would be minimizing opponent's sum.

Case B: Similar, when we have picked 'j' . After that there would be coins i through j-1 are left. He can pick either coin @ i or j-1 location

B = Min {S[i+1, j-1], S[i, j-2]} + value of coin.

This would be minimizing opponent's sum.

Finally, we have Maximize all the moves starting from 0...n

Maximize{ A, B }

Complexity O(n^2).

I cannot find the explanation after googling, can you post some link or what exactly you googled for, I kind of lost from here : His resultant value would be either S[i+2, j] or S[i+1, j-1]

#include<stdio.h>

#include<conio.h>

int main()

{

int a[5]={12,24,10,25,8};

int s=0;

int e=4;

int max=a[s]+a[e];

while(s < e)

{

if((a[s]+a[e])> max)

{

max=a[s]+a[e];

}

if(a[s]>a[e])

{

--e;

}

else

++s;

}

printf("%d",max);

getchar();

getchar();

return 0;

}

My java implementation:

```
private static Pair<Integer, Integer> getMaxPossibleWithSmartOpponent(int[] nos, boolean isMainPlayer, int p1, int p2) {
if(nos.length == 1) {
if(isMainPlayer) return Pair.of(p1 + nos[0], p2);
else return Pair.of(p1, p2 + nos[0]);
}
// call for opponent assuming left is picked
Pair<Integer, Integer> leftAns = null;
if(isMainPlayer) {
leftAns = getMaxPossibleWithSmartOpponent(Arrays.copyOfRange(nos, 1, nos.length),
!isMainPlayer, p1 + nos[0], p2);
} else {
leftAns = getMaxPossibleWithSmartOpponent(Arrays.copyOfRange(nos, 1, nos.length),
!isMainPlayer, p1, p2 + nos[0]);
}
// call for opponent assuming right is picked
Pair<Integer, Integer> rightAns = null;
if(isMainPlayer) {
rightAns = getMaxPossibleWithSmartOpponent(Arrays.copyOfRange(nos, 0, nos.length-1),
!isMainPlayer, p1 + nos[nos.length-1], p2);
} else {
rightAns = getMaxPossibleWithSmartOpponent(Arrays.copyOfRange(nos, 0, nos.length-1),
!isMainPlayer, p1, p2 + nos[nos.length-1]);
}
if(isMainPlayer) {
return leftAns.getLeft() > rightAns.getLeft() ? leftAns : rightAns;
} else {
return leftAns.getRight() > rightAns.getRight() ? leftAns : rightAns;
}
}
```

this is the case for 2 players:

- rkris April 22, 2011Take 5 first ..

.. then list is ( 12, 24, 10)

they take 12 or 10 either list look like (24, 10) or (12, 24)

Now pick 24 ..,

you sum is 29 and oppenent sum is 22.

..but i didnt understand ..what this to do with software engineer question.. i really wonder.,