CareerCup

What is the "win criteria"? is it having 3 of a kind in a row or all the same in a row. If it's the former than this wouldn't work for grids bigger than 3*3.

brilliant solution peng. it can be easily extended by increasing SIZE constant.

kewl soln !

Nice solution. You are however not checking for diagonal conditions though :)

Great Solution. However diagonals need to be handled as IntwPrep pointed out.

if (p == 1){ 
row[y]++; 
col[x]++; 

if (x == y)
   diag ++ // similarly decrement for the other player.

if (y == n - x )
   antidiag ++ // similarly decrement for the other player.

}

// finally check 

diag == SIZE or diag ==  MSIZE 
or antidiag == SIZE or antidiag == MSIZE

Also we can have another counter for number of moves made.
moves=0;
moves++ for every move, If moves = n*n , then game is over

This is to check if a player wins as the game progresses. I understand that you are given a snapshot of the grid at any given time and you need to determine who won.

This works only in case the SIZE of the game determines how many X's or O's you need. 3x3 -> you need to have 3 same symbols. I understood it as an NxN game where you need to have 5 same symbols.

i guess the interviewer was asking the author to check the winning condition in every step during the game

Even then .... For example its 3*3 tic tac toe game and I fill the square 1*1, the program has to check the square
1*1, 1*2, 1*3
1*1, 2*1, 3*1
1*1, 2*2, 3*3

I dont see how this can be done in O(1)

One possinel solution is keep one more row and column and one extra int var. These will store sum of corresponding row column and diagonals. After each move these will be updated. I see only this is the way to solve it in O(1)

it's O(1) space complex. but I don't think it O(1) time comlex........

haha.. is this O(1) coz u wrote it in words?

There should be two diagonals for each location in the grid and both should be checked. On the other hand, as stated in my previous comment, this solution assumes the win criteria is having all items in a row/ column/ diagonal to be the same. Is it the "win criteria" of tic-tac-toe?

this can simply be done in O(1) with the use of a 2X4 array (set of 4 for each player, where each variable keeps count of middle row,middle col,middle diagonal,middle back-diagonal).For each move check update the associated variable. In order to check for winning condition just check whether any variable is equal to N.
Below is the code:

int count[2][4],N;
//assuming the zero based indexing...
void update(int type, int row, int col)
{
if(row == col)++count[type][0]; //diagonal;
if(row == N/2)++count[type][1]; //row;
if(col == N/2)++count[type][2]; //column;
if(row+col == N-1)++count[type][3]; //back diagonal
}

bool win(int type)
{
for(int i=0;i<4;++i)if(arr[type][i] == N)return true;
return false;
}

int main()
{
cin >> N;
int moves = 0;
while(1)
{
int r = getPlayer_row();
int c = getPlayer_col();
int type = getPlayer_type();//0 or 1 corresponding to'X' //or 'O'
update(type,r,c);
moves++;
if(moves >= N*N || win(0) || win(1))break;
}
}

volongoto is right, we need to also track the two diagonals. but only a single variable is enough for each diagonal:

diag=0;
diag_back=0;
if(p==1){
if(x==y)
diag++;
else if (x+y==SIZE) // back-diagonal
diag_back++;
}
else {
if(x==y)
diag--;
else if (x+y==SIZE) // back-diagonal
diag_back--;
}

if (diag == SIZE || diag == MSIZE
|| diag_back == SIZE || diag_back == MSIZE)
return p;
else {
// check rows and columns
}

return 0;

volongoto is right, we need to also track the two diagonals. but only a single variable is enough for each diagonal:

diag=0;
diag_back=0;
if(p==1){
  if(x==y)
    diag++;
  else if (x+y==SIZE) // back-diagonal
    diag_back++;
}
else {
  if(x==y)
    diag--;
  else if (x+y==SIZE) // back-diagonal
    diag_back--;
}

if (diag == SIZE || diag == MSIZE 
   || diag_back == SIZE || diag_back == MSIZE)
  return p;
else {
  // check rows and columns
}

return 0;