Microsoft Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
All i could think of at that time is to store all the board configurations in a hash so that getting best position of move is a O(1) operation.
Each board square can be either 0,1, or 2.
0 represents empty square. 1 represents a X & 2 represents 0.
So every square can be filled with either of the three. There are approx 3^9 board configurations.
In simple, we need a hash of size 3^9. For hashing,we can go for base 3 representation. Means each number in base 3 will be 9 digits long each digit corresponding to each square.
To search in hash, we need to find the decimal representation of this 9 digit number.
Now, each square can be associated with row number & column number. In order to identify each square uniquely, we can again make use of base 3 representation.
say SQ[1][2] will be 12 in base 3 which is equivalent to 5 in decimal.
Thus, we have effectively designed an algorithm which is fast enough to calculate the next move in O(1).
But, the interviewer insisted in reducing the space complexity as DOS system doesn't have that much amount of memory.
I couldn't think how we can reduce the space complexity with no change in time complexity.
I think symmetry can be used.
Rather than complete board state, consider the 'number of moves' that can be made-- first there are 9, then human plays, and computer can chose from 7, then human plays and computer can choose from 5, 3, until only 1 (unless an earlier win/loss is found).
This means the search set is 9x7x5x3 = 945, instead of 3^9 = 19683
the difficulty with this approach is mapping from the current board state into these choice states, considering they can be applied to the board in 4 rotations. (the first move in the top left corner is the same as the first move in any other corner, rotated appropriately)
@keless, can you shed more light on how to use symmetry.
A pseudo code or an example showing how to map symmetry appropriately would be helpful.
When making a move, the computer first checks to see if it can win by putting an X/O into one of these three squares.
- amnesiac June 15, 2012If it cannot win, it checks to see if it has to block X from winning on the next move by putting an X/O into one of these three squares.
If neither of these two conditions holds, the computer checks to see if it has to move into one of these squares to block X from winning in two moves. If it can't win and doesn't need to block X on the next one or two moves, the computer chooses an arbitrary location for its move.
is there any better way?