Interview Questions

228. Given 2 points a chess board .....

Microsoft Interview Questions and Answers


(Continued from previous question...)

228. Given 2 points a chess board .....

Question:
I was given 2 points a chess board, interviewer asked my to use the as less bit as I can to store those to points, I was thinking to use 3 bits to represent each x and y, then totally is 12 bits, but he was looking for less than that

Suppose you are given 2 points on the board(x1, y1), (x2, y2), then if you want to represent any one of those four coordinates, you need 3 bits, since 3 bits can represent 8 numbers.

But like what you said, if you map all location on the board to 0 - 63, you will be using 6 bits to represent any one in that range, then two position will still be 12 bits


maybe an answer:


First of all, it's 64 * 63 / 2 because the points don't have any particular order. You can pick the first point in 64 different ways, the second in 63 different ways, but now each pair appears twice, so you divide by 2.

It is actually important that the 2 points are distinct, otherwise the math below would not work ...

Anyway, since we have 64*63/2 possibilities, we need at least 11 bits to represent this. In other words, 11 bits is the best we can do! So let's do it ...

Number all the points on the board from 0 to 63. We will represent the 2 selected points by a pair (P1, P2-P1-1). P1 can be represented using 6 bits--that's easy. Now, If you select P1 correctly, P2-P1-1 < 32, and you can represent this using just 5 bits! How? Do all math mod 64! That's it :-)

So the exact formula is (assume P1 < P2):

if (P2-P1) <= 32 then (P1, (P2-P1-1) mod 64) = (P1, P2-P1-1). Note that P2-P1-1<=31 if (P2-P1) > 32 then (P2, (P1-P2-1) mod 64) = (P2, 64+P1-P2-1). Note that 64+P1-P2-1<31!

Knowing point P and distance D, P1=P, P2=(P+D+1) mod 64

Examples:
P1=10, P2=30. Choose P1 as the first, P2 as second, so the representation is (10, 30-10-1) = (10, 19).

To get the points back, P1=10, P2=10+19+1=30.

P1=10, P2 = 60. 60-10-1=49 -- too big. So we do (10-60-1)%64 = (-51)%64 = (64-51)%64 = 13. Then representation is (P2, (P1-P2)mod 64) = (60,13)!

To get the points back, P1=60, P2=(60+13+1) mod 64 = 10.


maybe an answer:


Let us represent each point in the form (c,x,y)
c will be the color bit - 1 represents black and 0 represents white since a chess board is 8 x 8, if we split the chess board into 2 sub boards (ie the black sub board and the white sub board, then we will have two 4 x 4 boards to deal with);
In a 4 x 4 board any point can be represented in 4 bits (2 for the x coordinate and 2 bits for the y coordinate)

So in effect, (c,x,y) is equivalent to representing a point using 1+2+2=5 bits For 2 points, we need 10 bits in this representation..

(Continued on next question...)

Other Interview Questions