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.,