Interview Question for Software Development Engineer In Test (SDET) at Microsoft:

Tic-Tac-Toe is game like soduku or checkers that is represented as having columns and rows which translates as a 2 Dimensional array. In this case a 3x3 array. Represented as [0][0] [1][0] [2][0] You would therefore permutate each possibility.
.... ..... ......
...... ..... ..... [2][2]

It's all about state. You can only win on the placement of a token so check the possible ways to win from this position. So say the user places a value in the bottom left corner. Then you need only check the vertical, horizontal and the diagonal from this position. From the center position you will need to check 4 different positions (+ and x). This retains a O(1) solution but then again this only works if you can keep count of how many moves have already occurred.