Google Interview Question
InternsCountry: United States
Interview Type: Phone Interview
Is it Minimax algorithm? Try to maximize own profit on n elements by minimizing the opponent's profit on n-1 elements, and so on.
Yes, ninhnnsoc, minimax. However the amount of states to visit is small therefore does not have to have same time complexity as minimax.
Amr, see my comment below. If you do not use DP, your solution is exponential while can be simply n^2.
Just one comment: In my solution instead of mimicking recursive solution and enhancing it with meimozation, I just work through building the two matrices. It comes out smaller. I will type it in in the evening.
FOUND A BUG: array[start/end] counts towards current player but plus solveGame towards opposing player. kim addresses this, however I am not fun of his solution because he uses HashMap instead of matrix.
It's unclear if the game is competitive or cooperative. If it's competitive, it's unclear if player 2 plays perfectly. I will assume it is either cooperative or that player 2 plays poorly. Here is a solution that simply iterates over the possible outcomes and picks the one with the max value. Time complexity is O(2^n)). Some memozation could speed it up.
int maxGold(int a[]) {
return maxGold(a, 0, a.length - 1, true);
}
int maxGold(int a[], int left, int right, boolean firstPlayer) {
int max = _maxGold(a, left, right, firstPlayer);
System.out.println("(" + left + "," + right + "," + firstPlayer + ") = " + max);
return max;
}
int _maxGold(int a[], int left, int right, boolean firstPlayer) {
if (left == right) {
if (firstPlayer) {
return a[left];
}
else {
return 0;
}
}
int leftMax = maxGold(a, left+1, right, !firstPlayer);
int rightMax = maxGold(a, left, right-1, !firstPlayer);
if (firstPlayer) {
leftMax += a[left];
rightMax += a[right];
}
return Math.max(leftMax, rightMax);
}
And here is the memoized solution. Time complexity is O(n^2).
int maxGold(int a[]) {
int cache[][][] = new int[2][a.length][a.length];
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < a.length; ++j) {
for (int k = 0; k < a.length; ++k) {
cache[i][j][k] = -1;
}
}
}
return maxGold(a, 0, a.length - 1, true, cache);
}
int maxGold(int a[], int left, int right, boolean firstPlayer, int cache[][][]) {
int cachedMax = cache[firstPlayer ? 1 : 0][left][right];
if (cachedMax >= 0) {
return cachedMax;
}
int max = _maxGold(a, left, right, firstPlayer, cache);
cache[firstPlayer ? 1 : 0][left][right] = max;
System.out.println("(" + left + "," + right + "," + firstPlayer + ") = " + max);
return max;
}
int _maxGold(int a[], int left, int right, boolean firstPlayer, int cache[][][]) {
++iterations;
if (left == right) {
if (firstPlayer) {
return a[left];
}
else {
return 0;
}
}
int leftMax = maxGold(a, left+1, right, !firstPlayer, cache);
int rightMax = maxGold(a, left, right-1, !firstPlayer, cache);
if (firstPlayer) {
leftMax += a[left];
rightMax += a[right];
}
return Math.max(leftMax, rightMax);
}
Upon further reflection... It does not matter if the game is competitive or cooperative because we are simply looking for the best possible outcome for player 1 and that outcome occurs at the same time as the worst possible outcome for player 2. The strategy used by either player is irrelevant.
I thought each should use best for him/her strategy. Ok, I see, you interpreted the problem as how much Gold if first plays best and second plays worst. But still, you need strategy for best and strategy for worst.
No I think what the problem is asking is, "Regardless of the strategies chosen by the two players, what is best possible outcome for player 1?" Another problem might ask, "If both players use a strategy of choosing the number with the greatest possible outcome, what will player 1's score be?" Yet another problem might ask, "Is there a strategy that guarantees the best possible outcome?"
After playing with this problem more, I am starting to wonder if there is a O(n) solution. Experimentally I have seen that there is a high probability that that best outcome is the sum of the n/2 highest numbers (i.e. the set of numbers >= median).
Yes, I meant the the same. I don't think it can be that simple because n/2 highest can be all consecutive and this sequence would have to be broken by second after at most in the half of the game. However, perhaps there exist O(n) solution, or less than n^2 for this version of problem interpretation, I would myself be interested to research.
Yes, there are cases where player 1 cannot choose the n/2 highest numbers no matter what order either player chooses, however experimentally I have seen that those case are rare. In cases where the n/2 highest are consecutive, player 1 can always choose all of them. For example,
1,2,3,4 => player 1 chooses 4,3
2,1,3,4 => player 1 chooses 4,3
Cases where it is not possible are some cases where the n/2 highest alternate left and right. For example:
12,10,8,6,4,2,1,3,5,7,9,11
CAVEAT: I didn't check this particular one but it follows the pattern.
The recursive solution O(2^n):
public static int getMaxGold(int[] input) {
int N = input.length;
int[] sum = new int[N];
for (int i = 0; i < N; i++) {
if (i == 0)
sum[i] = input[i];
else
sum[i] = sum[i - 1] + input[i];
}
return getMaxGold(input, 0, N - 1, sum);
}
public static int getMaxGold(int[] input, int start, int end, int[] sum) {
if (start < 0 || end > input.length || start > end)
return 0;
else if (start == end)
return input[start];
int choose1 = input[start] + sum[end] - sum[start] - getMaxGold(input, start + 1, end, sum);
int choose2 = input[end] + sum[end - 1] - getMaxGold(input, start, end - 1, sum);
if (start > 0)
choose2 = choose2 - sum[start - 1];
return Math.max(choose1, choose2);
}
The dp solution O(n^2):
public static int getMaxGold2(int[] input) {
int N = input.length;
int[] sum = new int[N];
for (int i = 0; i < N; i++) {
if (i == 0)
sum[i] = input[i];
else
sum[i] = sum[i - 1] + input[i];
}
HashMap<String, Integer> map = new HashMap<>();
return getMaxGold2(input, 0, N - 1, sum, map);
}
public static int getMaxGold2(int[] input, int start, int end, int[] sum,
HashMap<String, Integer> map) {
if (start < 0 || end > input.length || start > end)
return 0;
else if (start == end)
return input[start];
else {
String key = start + "," + end;
if (map.containsKey(key))
return map.get(key);
int choose1 = input[start] + sum[end] - sum[start] - getMaxGold2(input, start + 1, end, sum, map);
int choose2 = input[end] + sum[end - 1] - getMaxGold2(input, start, end - 1, sum, map);
if (start > 0)
choose2 = choose2 - sum[start - 1];
int result = Math.max(choose1, choose2);
map.put(key, result);
return result;
}
}
The below dynamic programming solution is relatively simple (ignores the second player altogether) and works on a few test cases. The allocation for the 0 padded solution matrix is a little strange, but saves on if statements.
#include <stdio.h>
#include <climits>
#include <iostream>
#define START_BUFFER 2
#define END_BUFFER 4
using namespace std;
int get_max(int * array, int sz)
{
int max = INT_MIN;
for (int i = 0; i < sz; ++i)
{
if (max < array[i])
{
max = array[i];
}
}
return max;
}
void solve(int * pots, int npots, int ** allocators, int ** slns)
{
int options[4];
for (int start = npots-1; start >= 0; --start)
{
for (int end = start; end < npots; ++end)
{
options[0] = pots[start] + slns[start + 1][end - 1];
options[1] = pots[start] + slns[start + 2][end];
options[2] = pots[end] + slns[start + 1][end - 1];
options[3] = pots[end] + slns[start][end - 2];
slns[start][end] = get_max(options, 4);
}
}
}
int main(int argc, char* argv[])
{
int npots = 6;
// simple test
int pots[] = { 5, 1, 5, 1, 5, 1};
int ** allocators; int ** slns;
// allocate with zero padding
allocators = new int*[npots + START_BUFFER];
slns = new int*[npots + START_BUFFER];
for (int j = 0; j < npots + START_BUFFER; ++j)
{
allocators[j] = new int[npots + END_BUFFER];
slns[j] = allocators[j] + START_BUFFER;
memset(allocators[j], 0, sizeof(int)*(npots + END_BUFFER));
}
// solve
solve(pots, npots, allocators, slns);
for (int i = 0; i < npots; ++i)
{
for (int j = 0; j < npots; ++j)
{
printf(" %i ", slns[i][j]);
}
printf("\n");
}
// deallocate
for (int i = 0; i < npots + START_BUFFER; ++i)
{
delete allocators[i];
}
delete allocators;
delete slns;
system("pause");
return 0;
}
package careercup;
public class CC5707979286380544 {
public static int getMaxGold(int[] gold,int maxGold,int turn,int startIndex,int endIndex){
if(startIndex >endIndex||startIndex < 0||endIndex > gold.length){
return maxGold;
}
if(turn == 0){
if(gold[startIndex] > gold[endIndex]){
maxGold+= gold[startIndex];
return getMaxGold(gold, maxGold, 1, ++startIndex, endIndex);
}else{
maxGold+= gold[endIndex];
return getMaxGold(gold, maxGold, 1, startIndex, --endIndex);
}
}else{
if(gold[startIndex] > gold[endIndex]){
return getMaxGold(gold, maxGold, 0, startIndex, --endIndex);
}else{
return getMaxGold(gold, maxGold, 0, ++startIndex, endIndex);
}
}
}
public static void main(String[] args){
int[] gold = {5,3,1,2,4};
System.out.println(getMaxGold(gold, 0, 0, 0, gold.length-1));
}
}
#include<iostream>
void recur(int a[],int ii,int jj,int P,int MaxA,int MaxB)
{
cout<<"\n Nana ::"<<ii<<"\t"<<jj;
if(ii>jj){ cout<<"\n\t\t Maximum A, B-->("<<MaxA<<","<<MaxB<<")("<<ii<<","<<jj<<")";return ;}
if(P%2==0){
cout<<"\n\t One A::"<<ii<<"\t"<<jj<<"\t MaxA,MaxB"<<MaxA<<","<<MaxB;;
recur(a,ii+1,jj,(P+1)%2,a[ii]+MaxA,MaxB); cout<<"\n\t One A1::"<<ii<<"\t"<<jj<<"\t MaxA,MaxB"<<MaxA<<","<<MaxB;
recur(a,ii,jj-1,(P+1)%2,a[jj]+MaxA,MaxB); cout<<"\n\t One A2::"<<ii<<"\t"<<jj<<"\t MaxA,MaxB"<<MaxA<<","<<MaxB;
}else if(P%2!=0){
cout<<"\n\t One B::"<<ii<<"\t"<<jj<<"\t MaxA,MaxB"<<MaxA<<","<<MaxB;
recur(a,ii+1,jj,(P+1)%2,MaxA,a[ii]+MaxB);cout<<"\n\t One B1::"<<ii<<"\t"<<jj<<"\t MaxA,MaxB"<<MaxA<<","<<MaxB;
recur(a,ii,jj-1,(P+1)%2,MaxA,a[jj]+MaxB);cout<<"\n\t One B2::"<<ii<<"\t"<<jj<<"\t MaxA,MaxB"<<MaxA<<","<<MaxB;
}
}
int main()
{
int a[]={1,2,3,4,5,6};recur(a,0,sizeof(a)/sizeof(int)-1,0,0,0);
return 0;
}
Just wrote solution on paper, no time to type it.
NOTICE: There are n^2 states here (begin offset multiplied by end offset) and whatever strategy led to each state has to be the best for both therefore you can assume there is only one way to get to each state.
THEREFORE: IF you don't use dynamic programming, your solution is exponential as opposed to n^2.
DP with no recursion:
(If you wonder how comes it does not look like minimax but rather min-min: switch of turn is implied by even or odd number of taken jars or by moving one cell horizontally or vertically)
public static int maxGold( int[] input ) {
int[] sum = new int[input.length+1];
sum[0] = 0;
for ( int i = 0; i < input.length; i ++) sum[i+1] += sum[i] + input[i];
int[][] takenOnSides2Gold = new int[input.length+1][input.length+1];
for ( int taken = input.length - 1; taken >= 0; taken --) {
for ( int takenFront = 0; takenFront <= taken; takenFront ++) {
int takenEnd = taken - takenFront;
takenOnSides2Gold[takenFront][takenEnd] =
sum[input.length-takenEnd] - sum[takenFront] - //total gold left
Math.min( //next move minimizes how much is taken by opponent
takenOnSides2Gold[takenFront+1][takenEnd],
takenOnSides2Gold[takenFront][takenEnd+1]);
}
}
return takenOnSides2Gold[0][0];
}
An idea surfaced that the problem implies that max may mean that first plays to maximize gold but the second, perhaps due to inexperience in the game, inadvertently plays to minimize his/her gold, thus helping the first to achieve his absolute max gold possible by the game rules. If that was the correct interpretation, my solution can be easily modified for this:
public static int maxGold( int[] input ) {
int[] sum = new int[input.length+1];
sum[0] = 0;
for ( int i = 0; i < input.length; i ++) sum[i+1] += sum[i] + input[i];
int[][] takenOnSides2Gold = new int[input.length+1][input.length+1];
for ( int taken = input.length - 1; taken >= 0; taken --) {
for ( int takenFront = 0; takenFront <= taken; takenFront ++) {
int takenEnd = taken - takenFront;
takenOnSides2Gold[takenFront][takenEnd] =
sum[input.length-takenEnd] - sum[takenFront] - //total gold left
( (taken % 2 ==0) ?
Math.min(
takenOnSides2Gold[takenFront+1][takenEnd],
takenOnSides2Gold[takenFront][takenEnd+1]) :
Math.max(
takenOnSides2Gold[takenFront+1][takenEnd],
takenOnSides2Gold[takenFront][takenEnd+1] ) );
}
}
return takenOnSides2Gold[0][0];
}
In Python:
def each_cons(L, n):
for j in range(len(L) - n + 1):
yield L[j:j+n]
def coin_game(L, values={(): 0}, indices={}):
for length in range(len(L)):
for sliced_list in each_cons(tuple(L), length + 1):
take_left_value = sliced_list[0] - values[sliced_list[1:]]
take_right_value = sliced_list[-1] - values[sliced_list[:-1]]
if take_left_value > take_right_value:
values[sliced_list] = take_left_value
indices[sliced_list] = 0
else:
values[sliced_list] = take_right_value
indices[sliced_list] = -1
print "list", L, "has value", values[tuple(L)], "take", indices[tuple(L)]
It can be solved with dynamic programming in O(n^2) as suggested before. Java code:
public static int solve(int[] buckets) {
int[][][] dpValue = new int[buckets.length][buckets.length][2];
int[] sums = new int[buckets.length];
sums[0] = buckets[0];
// cumulative sum to be used later in finding partial sums (from i to j).
for (int i = 1; i < buckets.length; i++)
sums[i] = sums[i - 1] + buckets[i];
for (int i = buckets.length - 1; i > -1; i--) {
// if only one bucket left, best decision is to pick it.
dpValue[i][i] = new int[] {buckets[i], buckets[i]};
for (int j = i + 1; j < buckets.length; j++) {
// total worth of gold?
int sumIJ = sums[j] - sums[i] + buckets[i];
for (int k = 0; k < 2; k++) {
// gain the other player gets if we pick first?
int pickFirst = dpValue[i + 1][j][1 - k];
int pickLast = dpValue[i][j - 1][1 - k];
// total worth - best gain for other player = our gain => maximize it by minimizing the other player gain.
dpValue[i][j][k] = sumIJ - Math.min(pickFirst, pickLast);
}
}
}
return dpValue[0][buckets.length - 1][0];
}
I have discussed these four scenarios: competitive/cooperative playing + known/unknown pots. The solution is to use dynamic programming to solve them. Please refer to
1. cpluspluslearning-petert.blogspot.co.uk/2014/12/dynamic-programming-maximizing-gold.html
2. cpluspluslearning-petert.blogspot.co.uk/2014/12/dynamic-programming-maximizing-gold_10.html
3. cpluspluslearning-petert.blogspot.co.uk/2014/12/dynamic-programming-maximizing-gold_14.html
Dynamic programming. O(N^2)
int MaxGold(int pots[], int s, int e)
{
if (s > e)
return 0;
if (s == e)
return pots[s];
int opt1 = pots[s] + MaxGold(pots, s+2, e);
int opt2 = pots[s] + MaxGold(pots, s+1, e-1);
int opt3 = pots[e] + MaxGold(pots, s, e-2);
int opt4 = pots[e] + MaxGold(pots, s+1, e-1); //Partly duplicate of opt2.
return max(max(opt1, opt2), max(opt3, opt4));
}
Here's a cpp solution
#include<vector>
#include<unordered_set>
#include<set>
#include<algorithm>
#include<stdlib.h>
#include<iostream>
#include<utility>
#include<map>
using namespace std;
int n;
int dp[100][100];//,dp2[100][100];
int max1(int a,int b)
{
return a>b?a:b;
}
int sum1(int *arr,int start,int end)
{
int sum=0,i;
for(i=start;i<=end;i++)
{
sum+=arr[i];
}
return sum;
}
int maxGold1(int *arr,int start,int end,bool player)
{
if(start<0 || end>=n)
return 0;
//printf("for %d %d\n",start,end);
if(!player)
{
dp[start][end]=maxGold1(arr,start,end,true);
//printf("\n%d %d %d\n",start,end,dp[start][end]);
return sum1(arr,start,end)-dp[start][end];
}
if(dp[start][end]!=-1)
return dp[start][end];
if(start==end)
{
dp[start][end]=arr[start];
return arr[start];
}
dp[start][end]=max1(arr[start]+maxGold1(arr,start+1,end,false),arr[end]+maxGold1(arr,start,end-1,false));
//printf("%d %d\n",maxGold1(arr,start+1,end,false),maxGold1(arr,start,end-1,false));
//printf("at down %d %d %d\n",start,end,dp[start][end]);
//getchar();
return dp[start][end];
}
int main()
{
int arr[]={10,20,80,30,40},i,j;
n=5;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
dp[i][j]=-1;
}
}
maxGold1(arr,0,n-1,true);
printf("%d\n",dp[0][n-1]);
}
#Two players: a,b. calculates max coin collected by input player
#Using DP: player defines who is the 1st player,assuming you are player a
def coin_game(x,player):
score= [[],[]]
if player == 'a':
curr = 0
else:
curr = 1
for i in range(len(x)):
#print(i)
if len(x)>1:
toPop = 0
# Solution that only you play best
if curr == 0:
if x[0]<x[-1]:
toPop = -1
else:
if x[0]>x[-1]:
toPop = -1
if len(score[curr]) == 0:
score[curr].append(x.pop(toPop))
else:
score[curr].append(score[curr][-1]+x.pop(toPop))
#########################################
# Solution that both the player play best
'''
if x[0]<x[-1]:
toPop = -1
if len(score[curr]) == 0:
score[curr].append(x.pop(toPop))
else:
score[curr].append(score[curr][-1]+x.pop(toPop))
'''
#########################################
if curr == 0:
curr = 1
else:
curr = 0
else:
score[curr].append(score[curr][-1]+x[0])
#print (score)
return score[0][-1]
x = [5,2,1,8,7,9,12,32,85,61]
print coin_game(x,'b')
The idea is that when you start taking coins and you have "n" coins, you can take the coin at the beginning (at index 0) and you are left with coins [1,n-1], or you can take the coin at position n-1 and you are left with coins [0,n-2]. In either case, you are left with a version of the problem where you have n-1 coins and YOUR OPPONENT STARTS.
Imagine now that you have a total of n-1 coins but your opponent is the one who will start the move. In this case there are two options, either the opponent chooses the coin at the beginning or he chooses the coin at the end. in either case you are now left with a total of n-2 coins and YOU START THE MOVE once again.
In the base case when you have once coin, If it is your turn, you pick it, if it is not your turn you gain nothing.
We can solve this problem using dynamic programming. We will basically have two 2-dimensional arrays. The first one caches the max number of coins you can take for every possible start and end in the original array of coins when YOU START. The other 2-D array caches the max number of coins you can get for every possible start and end in the original array when YOUR OPPONENT starts moving, please find the code below
- Amr Gamal October 28, 2014