225. suppose you are given 2 points on the board(x1, y1), (x2, y2) ......
Microsoft Interview Questions and Answers
(Continued from previous question...)
225. suppose you are given 2 points on the board(x1, y1), (x2, y2) ......
Question:
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.
(Continued on next question...)
Other Interview Questions
|