This employer has taken extra steps to respond to reviews and provide job seekers with accurate company information, photos, and reviews. Interested for your company? Learn More.

Tags: | brain teaser See more , See less 8 |

Part of a `Software Engineer In Test` Interview Review - one of `2,770` `Google` Interview Reviews

Answers & Comments

▲

0

▼

of 3votes

There's a way to do this in constant time...

▲

6

▼

of 6votes

I think maybe this question is worded a bit wrong, because given a tic-tac-toe board you would need to read in at least some of the values on the board to figure out if someone has won, and this would be impossible to do in constant time (the larger the board, the more values you would have to read).

I think they must mean how can you determine if someone has won during a game in real time, as in checking after every move. This can be solved with a strategy in constant time.

My solution would be: Create an array of size 2n+2 at the beginning of the game and fill it with zeros. Each spot in the array will be a sum of X's or O's horizontally (the first n places in the array), vertically (the second n places in the array) and diagonally (the last 2 places). Then with every move, you add 1 to the 2 places (or 3 if on a diagnol) of the array if X, and subtract 1 if its an O. After adding you check and see if the value of the array is equal to n or -n, if it is, n mean X has won and -n means O has won.

I would bet there is a more elegant solution than creating a large array, but since this isn't my job interview I can't be bothered trying to figure one out. :)

I think they must mean how can you determine if someone has won during a game in real time, as in checking after every move. This can be solved with a strategy in constant time.

My solution would be: Create an array of size 2n+2 at the beginning of the game and fill it with zeros. Each spot in the array will be a sum of X's or O's horizontally (the first n places in the array), vertically (the second n places in the array) and diagonally (the last 2 places). Then with every move, you add 1 to the 2 places (or 3 if on a diagnol) of the array if X, and subtract 1 if its an O. After adding you check and see if the value of the array is equal to n or -n, if it is, n mean X has won and -n means O has won.

I would bet there is a more elegant solution than creating a large array, but since this isn't my job interview I can't be bothered trying to figure one out. :)

▲

1

▼

of 9votes

You would determine the winner by identifying the first player to string together three consecutive X's or O's. The size of the board is irrelevant.

▲

0

▼

of 9votes

You are looking for the winner. The easy and obvious answer is to check the happier player, not the board.

While this may ignore the "engineering" side of the question, it does demonstrate the logic of searching for the simplest answer becuase that solution will be the same regardless of the board configuration.

While this may ignore the "engineering" side of the question, it does demonstrate the logic of searching for the simplest answer becuase that solution will be the same regardless of the board configuration.

▲

3

▼

of 6votes

Happier player doesn't always mean the winner. A father teaching his son how to play tic tac toe for instance could be happier if his son actually beat him at the game. Your "simplest answer" is wrong.

▲

1

▼

of 1vote

Assume that you are handed a board with no prior knowledge of what has happened in the game. Assume that, to win on a board of size NxN, the player must have N 'X' characters or 'O' characters in the same row, column, or diagonal.

Assume that, for our problem, we are only checking if the winner is 'X'. We have to make at least one pass through the game board, but we should be able to solve the problem in one pass without checking any cell twice. Target running time O(N^2) for a board of size NxN.

boolean checkXWinner(int[][] a, int n){

int[] diagonalSums = new int[2];

int[] columnSums = new int[n];

initialize diagonalSums and columnSums with zeroes;

int rowSum = 0;

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)

if (a[i][j] = 'X')

rowSum++;

columnSums[j]++;

if (i == n-1 && columnSums[j] == n) return true

else if (i == j)

diagonalSums[0]++;

if (i == n-1 && diagonalSums[0] == n) return true

else if (i = n-1-j)

diagonalSums[1]++;

if (j == 0 && diagonalSums[i] == n) return true

if (rowSum == n) return true

Assume that, for our problem, we are only checking if the winner is 'X'. We have to make at least one pass through the game board, but we should be able to solve the problem in one pass without checking any cell twice. Target running time O(N^2) for a board of size NxN.

boolean checkXWinner(int[][] a, int n){

int[] diagonalSums = new int[2];

int[] columnSums = new int[n];

initialize diagonalSums and columnSums with zeroes;

int rowSum = 0;

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)

if (a[i][j] = 'X')

rowSum++;

columnSums[j]++;

if (i == n-1 && columnSums[j] == n) return true

else if (i == j)

diagonalSums[0]++;

if (i == n-1 && diagonalSums[0] == n) return true

else if (i = n-1-j)

diagonalSums[1]++;

if (j == 0 && diagonalSums[i] == n) return true

if (rowSum == n) return true

▲

0

▼

of 0votes

(sorry - forgot last line, put this after if (rowSum == n)....)

else rowSum = 0 // Need to reset the row counter

else rowSum = 0 // Need to reset the row counter

▲

0

▼

of 2votes

Ask.

▲

2

▼

of 6votes

Count the number of times X and O appear on the board. Whichever has the greater count is the winner.

▲

0

▼

of 0votes

there can be more than one winner

▲

0

▼

of 0votes

@count : The game can be tied even though one has greater count.

** To comment on this question, Sign In with Facebook or Sign Up **

Tags are like keywords that help categorize interview questions that have something in common.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

We're sorry but your feedback didn't make it to the team. Your input is valuable to us – would you mind trying again?

Browse:

Copyright © 2008–2014, Glassdoor. All Rights Reserved. Your use of this service is subject to our Terms of Use and Privacy & Cookies Policy. Glassdoor ® is a registered trademark of Glassdoor, Inc.

Sign In with Facebook

We do not post on Facebook

Sign In with Facebook

We do not post on Facebook

votes

BonApr 29, 2009Flag Response