Problem
How will you match two board configurations of tic-tac-toe problem?
Solution
This is a quite unexpected interview question as it has nothing to do with your programming skills or algorithms. This is a plain simple question designed to check your problem solving skills.
Consider the tic-tac-toe configurations :
The trick in this question is that any board configuration is rotation invariant and what we mean by that is all 2 the configurations shown above are similar and must match in the logic we use for checking board configurations.
Any given configuration of the board can have 7 other configurations which will be identical to it in terms of rotation invariance. These can be obtained by rotating the matrix either left or right 4 times. And then taking the mirror image of the matrix and again rotating it.
So the entire problem breaks down to reducing the first board configuration to matrix and then rotating it one by one and matching it with the other configuration.
Rotation of the elements of a matrix can be done in multiple ways and we are going to discuss two methods here.
Method 1: Given a matrix we can take it's transpose and to rotate it left exchange the rows and to rotate right, exchange the columns.
1) original matrix
1 2 3
4 5 6
7 8 9
2) transpose
1 4 7
2 5 8
3 6 9
3-a) change rows to rotate left
3 6 9
2 5 8
1 4 7
3-b) or change columns to rotate right
7 4 1
8 5 2
9 6 3
Method 2: We can use the following pesudo-code which directly does the work which is being done while taking transpose and exchanging columns. This works for a given square matrix A of dimension NxN
for n = 0 to N - 2
for m = n + 1 to N - 1
swap A(n,m) with A(m,n)
References
0 comments:
Post a Comment