instagram

Java Pots of gold game – Google Interview

by omt

Pots of gold game: Two players A & B. There are pots of gold arranged in a line, each containing some gold coins (the players can see how many coins are there in each gold pot – perfect information). They get alternating turns in which the player can pick a pot from one of the ends of the line. The winner is the player which has a higher number of coins at the end. The objective is to “maximize” the number of coins collected by A, assuming B also plays optimally. A starts the game.

The idea is to find an optimal strategy that makes A win knowing that B is playing optimally as well. How would you do that?

At the end I was asked to code this strategy!

package com.omt.learn.algo;

import java.util.ArrayList;
import java.util.List;

public class PotsOfGold {


	public static void main(String args[]) {
		// int[] i = { 9, 2, 4, 8, 7 };
		int[] i = { 5, 25, 4, 8, 32, 6 };
		System.out.println("Coins Collected By A: " + startGame('a', i, 0, i.length - 1, new ArrayList<>()));

	}

	private static List<Integer> startGame(char startWith, int[] coins, int start, int end, List coinsCollectedByA) {

		if (start >= end) {
			if (startWith == 'a') {
				coinsCollectedByA.add(coins[end]);
			}
			return coinsCollectedByA;
		}

		int coinCollected = ((coins[start] + coins[end - 1]) > (coins[start + 1] + coins[end])) ? coins[start]
				: coins[end];

		if (((coins[start] + coins[end - 1]) > (coins[start + 1] + coins[end]))) {
			start++;
		} else {
			end--;
		}

		if (startWith == 'a') {
			coinsCollectedByA.add(coinCollected);
			startWith = 'b';
		} else {
			startWith = 'a';
		}

		return startGame(startWith, coins, start, end, coinsCollectedByA);
	}

}

Output :
Coins Collected By A: [5, 4, 32]

Share