## Check if someone has won tic-tac-toe

Design an algorithm to figure out if someone has won in a game of tic-tac-toe.

My initial codes:

/**
* @param board
*        2D array of char representation of board
*        '*' - player 0
*        'o' - player 1
* @return 1: no one won
*         0: player 0 won
*         1: player 1 won
*/
public static int checkTicTacToe(char[][] board) {
int n = board.length;

// horizontally
for (int row = 0; row < n; ++row) {
boolean player0Won = true;
for (int col = 0; col < n; ++col) {
player0Won &= board[row][col] == '*';
}
if (player0Won)
return 0;

boolean player1Won = true;
for (int col = 0; col < n; ++col) {
player1Won &= board[row][col] == 'o';
}
if (player1Won)
return 1;
}

// vertically
for (int col = 0; col < n; ++col) {
boolean player0Won = true;
for (int row = 0; row < n; ++row) {
player0Won &= board[row][col] == '*';
}
if (player0Won)
return 0;

boolean player1Won = true;
for (int row = 0; row < n; ++row) {
player1Won &= board[row][col] == 'o';
}
if (player1Won)
return 1;
}

// diagonally
boolean player0Won = true;
for (int i = 0; i < n; ++i) {
player0Won &= board[i][i] == '*';
}
if (player0Won)
return 0;

boolean player1Won = true;
for (int i = 0; i < n; ++i) {
player1Won &= board[i][i] == 'o';
}
if (player1Won)
return 1;

// reverse-diagonally
player0Won = true;
for (int i = 0; i < n; ++i) {
player0Won &= board[i][n - i] == '*';
}
if (player0Won)
return 0;

player1Won = true;
for (int i = 0; i < n; ++i) {
player1Won &= board[i][n - i] == 'o';
}
if (player1Won)
return 1;

return -1;
}

Solution:
The first thing to ask your interviewer is whether the hasWon function will be called just once, or multiple times. If it will be called multiple times, you can get a very fast algorithm by amortizing the cost (especially if you can design your own data storage system for the tic-tac-toe board).

1. Approach #1: If hasWon is called many times
There are only 3^9, or about twenty thousand tic-tac-toe boards. We can thus represent our tic-tac-toe board as an int, with each digit representing a piece (0 means Empty, 1 means Red, 2 means Blue). We set up a hashtable or array in advance with all possible boards as keys, and the values are 0, 1, and 2 Our function then is simply this:

int hasWon(int board) {
return winnerHashtable[board];
}

2. Approach #2: If hasWon is only called once
enum Piece {
Empty, Red, Blue
};

enum Check {
Row, Column, Diagonal, ReverseDiagonal
}

Piece getIthColor(Piece[][] board, int index, int var, Check check) {
if (check == Check.Row)
return board[index][var];
else if (check == Check.Column)
return board[var][index];
else if (check == Check.Diagonal)
return board[var][var];
else if (check == Check.ReverseDiagonal)
return board[board.length - 1 - var][var];
return Piece.Empty;
}

Piece getWinner(Piece[][] board, int fixed_index, Check check) {
Piece color = getIthColor(board, fixed_index, 0, check);
if (color == Piece.Empty)
return Piece.Empty;
for (int var = 1; var < board.length; var++) {
if (color != getIthColor(board, fixed_index, var, check)) {
return Piece.Empty;
}
}
return color;
}

Piece hasWon(Piece[][] board) {
int N = board.length;
Piece winner = Piece.Empty;
// Check rows and columns
for (int i = 0; i < N; i++) {
winner = getWinner(board, i, Check.Row);
if (winner != Piece.Empty) {
return winner;
}

winner = getWinner(board, i, Check.Column);
if (winner != Piece.Empty) {
return winner;
}
}

winner = getWinner(board, -1, Check.Diagonal);
if (winner != Piece.Empty) {
return winner;
}

// Check diagonal
winner = getWinner(board, -1, Check.ReverseDiagonal);
if (winner != Piece.Empty) {
return winner;
}

return Piece.Empty;
}