Google Interview Question
Software Engineer / DevelopersWhat 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.
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.
How can it be done in O(n). If we are checking the contents of Row(n) wont it take O(n) time.
I think it will take O(n) + O(n) +O(n) + O(n)
Check through the row n, check through the column n, check through the left diagonal and the right diagonal
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)
We can do it in o(1) time. There are possible 6 winning conditions i.e H1, h2, h3, V1, V2, V3, D1, D2 where H stands for horizontal, v for verticle and d for diagonal and number stands for its level.
Now when we have any entry increment the value in the concerned level. e.g if user enters something in center than each condition will be incremented. Hence with this the one which got value of 3 will be the answer.
add above for diagonal elements also
diag[3]={0};
if(p==1){
if(x==y)
diag[x]++;
}
else
diag[x]--
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;
If someone enters a 1 in (m,n), add 1 to row[m], col[n]; also if m==n add to diagonal[m], and if m==(N-n), add to antidiag[m]. If 0 is entered, add -1 instead. If at any point of time, the updated row/col/diag/antidiag entry becomes either N or -N, you have a winner; if N, then you have 1 winnig; if -N then you have 0 winning. Since it invovles only a constant number of updates at every turn, it is O(1) checking for victory (at every turn).
My solution:
- Peng Du February 12, 2010{{
#define SIZE 3
#define MSIZE -3
int row[SIZE];
int col[SIZE];
int init () {
int i, j;
for (i=0; i<SIZE; ++i)
row[i] = 0;
for (j=0; j<SIZE; ++j)
row[j] = 0;
}
// 0: no win
// 1: 1st player win
// 2: 2nd player win
int check (int x, int y, int p){ // O(1)
if (p == 1){
row[y]++;
col[x]++;
}
else {
col[x]--;
row[y]--;
}
if (row[y] == SIZE ||
row[y] == MSIZE ||
col[x] == SIZE ||
col[x] == MSIZE)
return p; //
return 0;
}
}}