One of my recent job interviews asked me to devise an algorithm to find a winner in a Tic-Tac-Toe grid. Because this was the first technical interview of that day, I was far too nervous or stressed about impressing the two dudes talking to me and I ended up not paying close enough attention to the white board while I was speaking pseudo-confiden…

FindWinnerInTicTacToeAlgorithm

My first attempt was a brute force attempt.  I didn't even try to come up with the (time) complexity of this, at least while I was on-site.

// in Objective C everything is 0 (zero) based... but on my white board
// my tic-tac-toe grid object was 1 based...

// we might want to check if the game is valid even before
// we waste time looking to see if there's a winning set of three
- (BOOL) isValidGame: (Grid *) grid
{
    int totX = 0;
    int totO = 0;
    
    for( int i = 1; i < 4; i++ )
    {
        for( int j = 1; j < 4; j++ )
        {
            if(grid[i][j] == "X")
                totX++;
            if(grid[i][j] == "O")
                totO++;
        }
    }
    
    // if there is a bigger difference than one in terms of the total
    // number of X's and Y's, then we have an invalid game board
    if( abs(totX - totO) > 1 )
        return NO;
    
    return YES;
}

// this is the *brute force* solution
- (NSString *) whoIsAWinner
{
    int winnerX, winnerO;
    
    // initialize "winner" to zero... there can be at most only one winner
    winnerX = winnerO = 0;
    // first check for three X's or three Y's in a column
    for( int column = 1; column < 4; column++)
    {
        totX = 0; // <-- I neglected to put this on my white board, which might have gotten
        totO = 0; // <-- me a "thumbs down for not paying attention to detail" vote
        for( int row = 1; row < 4; row++)
        {
            if(grid[row][column] == "X")
            {
                totX++;
            }
            // I also scribbled "Y" on the white board instead of "O" throughout my code :-(
            if(grid[row][column] == "O")
            {
                totO++;
            }
        }
        if(totX == 3)
            winnerX++;
        if(totO == 3)
            winnerO++;
    }

    // second check for three X's or three Y's in a row
    for( int row = 1; row < 4; row++)
    {
        totX = 0; // <-- I neglected to put this on my white board, which might have gotten
        totO = 0; // <-- me a "thumbs down for not paying attention to detail" vote
        for( int column = 1; column < 4; column++)
        {
            if(grid[row][column] == "X")
            {
                totX++;
            }
            if(grid[row][column] == "O")
            {
                totO++;
            }
        }
        if(totX == 3)
            winnerX++;
        if(totO == 3)
            winnerO++;
    }

    // lastly, check the X (i.e. two three-in-a-row diagonal possibilities)
    // I talked about -- but didn't put on the board -- this code as I thought of a different solution
    // which I'll describe in a moment
    
    // see who is in the center
    if(grid[2][2] == "X")
    {
        if(grid[1][1] == "X") && (grid[3][3] == "X")
            winnerX++;
        if(grid[3][1] == "X") && (grid[1][3] == "X")
            winnerX++;
    }

    if(grid[2][2] == "O")
    {
        if(grid[1][1] == "O") && (grid[3][3] == "O")
            winnerO++;
        if(grid[3][1] == "O") && (grid[1][3] == "O")
            winnerO++;
    }

    // it's an invalid game if there are more than one lines of 3 X's or O's
    if(winnerX > 1) || (winnerO > 1)
    {
        return NULL;
    }

    // tie - no winners
    if((winnerX == 0) && (winnerO == 0))
    {
        return NULL;
    }
    
    if(winnerX == 0) && (winnerO == 1)
    {
        return @"O";
    }
    
    if(winnerX == 1) && (winnerO == 0)
    {
        return @"X";
    }
    
    return NULL;
}


Another approach I spoke about (and would have worked up had I had time within the one hour window) would have been to have separate all possible lines of three into different groups.  

E.G. [1,1][1,2][1,3]; [2,1][2,2][2,3];…;…;[1,1],[2,2],[3,3];[3,1][2,2][1,3]

And then look for three matching symbols within each set of triplets.