2
\$\begingroup\$

I was asked this question in interview yesterday:

Write the code for winning condition in an NxN matrix for tick tack toe.For example A function named "input_event(player_info, x_position, y_position)" will be triggered when the player inputs O or X, how will you check if the player has won inside this function ? Given: NxN matrix N>=3 and <=100

I managed to answer this by checking by loops horizontal, vertical and diagonal elements depending upon the current position. But the interviewer was not pleased and wanted me to achieve this without using so many repeated loops.

I searched on the internet on how to achieve this optimally and found this. I have posted the my implementation below:

#include <iostream>
#include <vector>
using namespace std;

class TicTacToe {
  vector<vector<char> > board;
  vector<int> winArr;
  int N;
public:
  TicTacToe(int sz) : N(sz) {
    board.resize(N);
    winArr.resize(2*N+2, 0);
    for(int i = 0; i < N; i++)
      board[i].resize(N, '.');
  }
  void playMove(char player, int nRow, int nCol) {
    cout << player << " Marks board[" << nRow << "]["<<nCol << "].\n";
    board[nRow][nCol] = player;
    updateWinArr(player, nRow, nCol);
    checkWinCondition();
  }
  void updateWinArr(char player, int nRow, int nCol) {
    int nVal = (player == 'X' ? 1 : -1);
    winArr[nRow] += nVal;
    winArr[N + nCol] += nVal;
    // check diagonals :
    if(nRow == nCol) // left diagonal
      winArr[2*N] += nVal;
    else if(nRow+nCol == N-1) // right diagonal
      winArr[2*N+1] += nVal;
  }
  void checkWinCondition() {
    bool bWin = false;
    char winner = '\0';
    for(int i = 0; i < winArr.size(); i++) {
      if(winArr[i] == -N) {
        bWin = true;
        winner = 'O';
        break;
      }
      else if(winArr[i] == N) {
        bWin = true;
        winner = 'X';
        break;
      }
    }
    if(bWin == true)
      cout << "Congrats!, " << winner << " has won the game\n";
  }
};

int main() {
  TicTacToe tt(3);
  tt.playMove('X', 0, 0);
  tt.playMove('O', 0, 2);
  tt.playMove('X', 1, 1);
  tt.playMove('O', 0, 1);
  tt.playMove('X', 2, 2);
  return 0;
}

I welcome any suggestions since I'm a beginner in C++.

\$\endgroup\$
  • 1
    \$\begingroup\$ If I were the interviewer, you would have immediately failed with the using namespace std; statement. It shows that there is no understanding of namespaces with is an important part of C++ and some other languages. \$\endgroup\$ – pacmaninbw May 24 '17 at 14:46
  • \$\begingroup\$ No I was asked only to write the method, not whole program. \$\endgroup\$ – Rohan Kumar May 24 '17 at 15:36
6
\$\begingroup\$
  1. You should not use namespace std. It is bad practice, that will hurt you in the long run.

  2. I do not really like your constructor:

    TicTacToe(int sz) : N(sz) {
       board.resize(N);
       winArr.resize(2*N+2, 0);
       for(int i = 0; i < N; i++)
          board[i].resize(N, '.');
    }
    

    The argument should be const. Then you should use the initializer list for all variables:

    TicTacToe(const int sz) 
        : board(sz, std::vector<char>(sz, '.')), winArr(2*sz+2), N(sz) {}
    
  3. In your updateWinArr() function you only check the diagonal in one direction:

    // check diagonals :
    if(nRow == nCol) // left diagonal
        winArr[2*N] += nVal;
    else if(nRow+nCol == N-1) // right diagonal
        winArr[2*N+1] += nVal;
    

    However, there are 4 attached diagonal points you should check.

  4. You logic is flawed. An X negates all previous 'O's. However, in your code you simply decrement:

    int nVal = (player == 'X' ? 1 : -1);
    winArr[nRow] += nVal;
    winArr[N + nCol] += nVal;
    

    This will make the following sequence a win, although it is not valid:

    Sequence: X X O X X
    Values  : 1 2 1 2 3
    
  5. I think it would be better to create a simple struct, that holds the relevant information:

    X or O
    left diagonal value
    right diagonal value
    horizontal value
    vertical value
    

    Now you can calculate the appropriate values by first checking, whether the mark is the right one and then add the horizontal value of the left/right neighbor and so on.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.