Microsoft Interview Question for SDE1s


Team: Outlook
Country: United States




Comment hidden because of low score. Click to expand.
8
of 12 vote

You can represent 2^n values with n bits.

However, you can represent
2^n + 2^(n-1) + 2^(n-2) + ... 1 = 2^(n+1) - 1
values with *atmost* n bits

So you can represent 2^11 - 1 = 2047 different values using just 10 bits.

Now here's the catch in the problem, as brennahan already mentioned - the order of the pieces doesn't matter.
So there are 64C2 = 2016 possible ways to arrange two pieces on an 8x8 chessboard.

Therefore, it should definitely be possible to represent 2016 ways using 10 bits.
In fact, you can represent 2016 values using all 5, 6, 7, 8, 9 and 10 bit sequences.

Here's one method:

Consider all possible relative positionings:

1. There are 7*8 = 56 possible ways of having two pieces horizontally adjacent = | P | P | 

2. There are 8*7 = 56 possible ways of having two pieces vertically adjacent = | P | 
                                                                               -----
                                                                               | P | 

3. There are 7*7 = 49 possible ways of having two pieces like this = | P |   |   
                                                                     ---------
                                                                     |   | P |   

4. There are 7*7 = 49 possible ways of having two pieces like this = |   | P | 
                                                                     ---------
                                                                     | P |   |

Just keep on repeating this procedure, using all sequences of 5, 6, 7, 8, 9 and 10 bits
You should be able to represent 32 + 64 + 128 + 256 + 512 + 1024 = 2016 ways to arrange the pieces.

Edit: I just wrote a program to automatically assign bit sequences to every possible configuration. There are a lot of them for 8x8 so I'll just show a solution for a 4x4 chessboard(120 configurations) using atmost 6 bits:

-----------------
| P | P |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
000

-----------------
|   | P | P |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
001

-----------------
|   |   | P | P |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
010

-----------------
|   |   |   |   |
-----------------
| P | P |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
011

-----------------
|   |   |   |   |
-----------------
|   | P | P |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
100

-----------------
|   |   |   |   |
-----------------
|   |   | P | P |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
101

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
| P | P |   |   |
-----------------
|   |   |   |   |
-----------------
110

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   | P | P |   |
-----------------
|   |   |   |   |
-----------------
111

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   | P | P |
-----------------
|   |   |   |   |
-----------------
0000

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
| P | P |   |   |
-----------------
0001

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   | P | P |   |
-----------------
0010

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   | P | P |
-----------------
0011

-----------------
| P |   | P |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
0100

-----------------
|   | P |   | P |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
0101

-----------------
|   |   |   |   |
-----------------
| P |   | P |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
0110

-----------------
|   |   |   |   |
-----------------
|   | P |   | P |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
0111

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
| P |   | P |   |
-----------------
|   |   |   |   |
-----------------
1000

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   | P |   | P |
-----------------
|   |   |   |   |
-----------------
1001

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
| P |   | P |   |
-----------------
1010

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   | P |   | P |
-----------------
1011

-----------------
| P |   |   | P |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
1100

-----------------
|   |   |   |   |
-----------------
| P |   |   | P |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
1101

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
| P |   |   | P |
-----------------
|   |   |   |   |
-----------------
1110

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
| P |   |   | P |
-----------------
1111

-----------------
| P |   |   |   |
-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
00000

-----------------
|   | P |   |   |
-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
00001

-----------------
|   |   | P |   |
-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
00010

-----------------
|   |   |   | P |
-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
00011

-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
00100

-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
00101

-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
00110

-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
00111

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
| P |   |   |   |
-----------------
01000

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
|   | P |   |   |
-----------------
01001

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
|   |   | P |   |
-----------------
01010

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
|   |   |   | P |
-----------------
01011

-----------------
| P |   |   |   |
-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
01100

-----------------
|   | P |   |   |
-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
01101

-----------------
|   |   | P |   |
-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
01110

-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
01111

-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
10000

-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
10001

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
|   | P |   |   |
-----------------
10010

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
|   |   | P |   |
-----------------
10011

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
|   |   |   | P |
-----------------
10100

-----------------
|   | P |   |   |
-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
10101

-----------------
|   |   | P |   |
-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
10110

-----------------
|   |   |   | P |
-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
10111

-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
11000

-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
11001

-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
11010

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
| P |   |   |   |
-----------------
11011

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
|   | P |   |   |
-----------------
11100

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
|   |   | P |   |
-----------------
11101

-----------------
| P |   |   |   |
-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
11110

-----------------
|   | P |   |   |
-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
11111

-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
000000

-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
000001

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
|   |   | P |   |
-----------------
000010

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
|   |   |   | P |
-----------------
000011

-----------------
|   |   | P |   |
-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
000100

-----------------
|   |   |   | P |
-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
000101

-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
000110

-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
000111

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
| P |   |   |   |
-----------------
001000

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
|   | P |   |   |
-----------------
001001

-----------------
| P |   |   |   |
-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
001010

-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
001011

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
|   |   |   | P |
-----------------
001100

-----------------
|   |   |   | P |
-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
001101

-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
001110

-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
| P |   |   |   |
-----------------
001111

-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
010000

-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
010001

-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
010010

-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
010011

-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
010100

-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
010101

-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
010110

-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
010111

-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
011000

-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
011001

-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
011010

-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
011011

-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
011100

-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
011101

-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
011110

-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
011111

-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
100000

-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
100001

-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
100010

-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
100011

-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
100100

-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
100101

-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
100110

-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
100111

-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
101000

-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
101001

-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
101010

-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
101011

-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
101100

-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
101101

-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
101110

-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
101111

-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
110000

-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
110001

-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
110010

-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
110011

-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
110100

-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
110101

-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
110110

-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
110111

-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
111000

-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
111001

-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   | P |   |
-----------------
111010

-----------------
|   | P |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
111011

-----------------
|   |   | P |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
111100

-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   | P |   |   |
-----------------
111101

-----------------
| P |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
|   |   |   | P |
-----------------
111110

-----------------
|   |   |   | P |
-----------------
|   |   |   |   |
-----------------
|   |   |   |   |
-----------------
| P |   |   |   |
-----------------
111111

- anotherguy August 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 4 votes

I can't seem to edit my answer. I have a much more elegant solution which uses a maximum of 10 bits, based upon pretonesio's 11 bit solution:

1. If the two pieces are on opposite vertical halves, the first 5 bits should represent the location of the piece in the first half and the next 5 bits should represent the location of the piece in the second half = 10 bits

2. If the pieces are in the same vertical half but in different quarters, use 1 bit to represent which half they are in, the next 4 bits to represent location of piece in upper quarter, next 4 for location of lower quarter piece = 9 bits

3. If they are in the same quarter but in different vertical eighths, use 2 bits to represent which quarter they are in, next 3 bits for location of piece in left eighth and next 3 bits of location of piece in right eighth = 8 bits

4. If they are in the same vertical eighth but in different sixteenth, use 3 bits for the eighth they are in, 2 bits for the piece in upper sixteenth and 2 bits for the piece in lower sixteenth = 7 bits

5. If they are in the same sixteenth but in different vertical thirtysecondths, use 4 bits for the sixteenth and 1 bit each for the location of each piece in respective thirtysecondth = 6 bits

6. If they are in the same thirtysecondth, use 5 bits to represent the location of that thirtysecondth = 5 bits

- anotherguy August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

Nice!!! I think you got it! Love your solution, great job!

- pretonesio August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

... As nice and elegant as this is, you still have to have a preconceived idea of where they are in order to decode from any given bit representation among all of them... which would require more bits to store that info. X_X

I mean if having extra information outside of the bit-representation is allowed this is a wonderful solution. If not, then you're trying to mash 2016 different combinations into a bit representation that at max holds 1024 and I'm not entirely sure if its possible.

Edit: tl;dr Given only the bit-representation, there is no schema to fit 2016 explicit combinations into 1024 slots using bit-representation.

- brennahan August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

You're treating space differently from 0, which means your number system is not strictly base 2, and your solution cannot qualify as using only 10 bits.

@Brennahan: it is not possible to mash 2016 combinations into a bit representation that holds 1024 combinations at max. Consider any function that maps a 10-bit value to a set of 2 positions. Clearly, since there are only 1024 possible inputs, there are only 1024 possible outputs. Some of the 2016 sets of 2 positions therefore have no 10-bit value that can represent them.

- eugene.yarovoi August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@brennahan: The limitation you're talking about is true for any encoding/decoding scheme. Even the 11 and 12 bits schemes. If you're using the 12 bit scheme, you have to know which 6 bits stand for the first piece's location and which for the second's. And how the locations are encoded to 6 bits. When you're using the 1 bit representation, you have to specify the combination that '0' represents and the combination that '1' represents. Which can also be phrased like this: It is not possible to have an encoding/decoding scheme whose decoder is an empty program.

@eugene.yaravoi: Yes you're correct, the solution is not strictly base 2. You cannot use a 10 bit integer datatype to represent all 2016 configurations. However, it seemed to me that the phrasing of the question allowed for this solution.

- Anonymous August 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how will u represent 2^(n+1) - 1 nos with atmost n bits? explain.
with atmost n bits only 2^n nos can be represented..

- poorvisha April 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
3
of 5 vote

One way of doing it with 11 bits is like the following:
You use 6 bits to represent your first position, and you use 5 bits to represent your second. You first position is represented by a simple x,y bit scheme. The second position will be represented as follows:
If 5 bits for the second position are passed in, make a x,y grid on the opposite half of the board and use the 5 bits to locate the second position.
If 4 bits are passed in, do the same thing as previously but in the opposite quadrant on the same half of the first picked point.
If 3 bits, use them to find it on the opposite eight on the same quadrant
If 2 bits , on the opposite sixteenth of the same eight
If 1, on the same thirtysecondth of the same sixteenth
if no bits, the second position is right below/above the first one

So basically you exploit the fact that no 2 pieces can be in the same place and save a bit

- pretonesio August 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

(I am Bren, just logged in to acct.)
The only other way I can think of is the case where order does not matter. In this case, you can have a base piece and a moving piece. The base piece sits on a spot, and the moving piece would cover the rest of the "NEW" combinations of spots. This mean you just have a summation for the total combination. 63 summation comes out to 2016 possible combinations, though again, you would still need 11 bits to cover it all.

- brennahan August 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Exactly! But I know there is a way of solving the problem with only 10 bits. However I'm not sure how.

- pretonesio August 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how are u concerned about two adjacent positions, two positions could be any where in chess board

- ravi August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@pretonesio.

>> If 5 bits for the second position are passed in, make a x,y grid on the opposite half of the board and use the 5 bits to locate the second position.

Could you please define/elaborate what you mean by 'opposite half of the board'?

If the first piece is located at position (0,0) and the second piece is located at (8,8), how will 5 bits suffice to identify the second piece relative to the first? Please clarify.

- Murali Mohan August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@m@}{: your solution seems to be the most elegant one if I am not missing anything.

3 bits - to represent 'quarter' (0,1,2,3)
3 bits - to represent 'x' inside quarter (0,1,2,3)
3 bits - to represent 'y' inside quarter (0,1,2,3)

- aka August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

@m@}{: I'm not sure what you're trying to do, but I think your solution uses 9 bits to store the position of 1 piece, which can be done with just 6 bits. Moreover, your code doesn't compile!

- anotherguy August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

Let's consider how many ways there are to place two pieces on an 8x8 chessboard. The first piece can be placed in one of 64 locations. The second piece can be placed in any one of the 63 remaining locations. Then, assuming you don't care about the order of locations, every pair of locations (i, j) is equivalent to the pair (j, i), so to get the total number of different pairs of locations, we need to divide by 2.

We get 64 * 63 / 2 = 2016.

There is therefore no way to do this with 10 bits, since a 10-bit value can only have one of 2^10 = 1024 possible values. With only 10 bits, only 1024 of the 2016 possibilities could have a representation. All the claims in this thread that you can do it with 10 bits are groundless.

With 11 bits, you can represent 2048 values, which is sufficient. The algorithm for encoding two locations as an 11-bit value is relatively straightforward. Give each chess square a number from 1 to 64. Then represent a pair of locations as the smaller number followed by the larger number. Map an integer to each pair in order, like this:
(1, 2) -> 0
(1, 3) -> 1
...
(1, 64) -> 62
(2, 3) -> 63
(2, 4) -> 64
...
(2, 64) -> 124
(3, 4) -> 125
...
(63, 64) -> 2015

You can do some simple math to compute the mapping efficiently.

The locations then have a 1-to-1 correspondence with integers between 0 and 2015. 11 bits are necessary and sufficient to represent these.

- eugene.yarovoi August 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if you consider 00010 and 10 as two different numbers then the whole argument you made will not hold good..

- kkr.ashish September 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

If you consider 10 and 00010 as two different numbers, you are not working in base 2. You've implicitly introduced a third type of symbol: the space. The designation "bit" applies to a 0 or 1 symbol in base 2.

- eugene.yarovoi September 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes you are right but if you take any bit compactness .. golomb , exp golomb..you would use start and end symbol which inherently will give you space symbol

- kkr.ashish September 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The idea of some compression schemes is that you can save space on frequently-occurring bit sequences by encoding them with shorter bit sequences. You would then save on the more frequently-occurring bit sequences at the expense of the less frequently-occurring ones.

That's not really what we're talking about, though. To represent just one object (just one selection of two positions on an 8x8 chessboard), if you want to be able to represent all 2016 possibilities, you cannot do it in less than ceil (log_2(2016)) = 11 bits. There is no way around this.

For that matter, even if we talk about space usage when you need to store N objects, you can't be guaranteed to be able to represent N such objects in less than (roughly) 11N bits. Compression schemes are only effective when some objects occur more frequently than others. Unless you know for a fact that your distribution of objects is non-random, you can't be guaranteed any space savings.

- eugene.yarovoi September 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

There are 4,032 total combinations for 2 different positions on a chessboard (=64*63(2 pieces can't occupy the same space assuming chess rules)) 2^12 would be 4096 so we would need 12 bits in order to cover all possibilities for the 2 positions.

In terms of determining the exact positions from the bit representation, you would need to set up a schema to translate(i.e. the first 6 bits determine where the first position is and the later 6 bits represent the second position is.)

- Bren August 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is true that a naive way can use 12 bits. All you need to do is label the different rows and columns of the board from 0-7 and use that as a x,y guide. That way, just like you described, you can use 12 bits. However, I know there is a way of doing it with only 10 bits. I'm just not sure how.

- pretonesio August 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

6 bits.. bcz.. on an 8x8 chess board... there can be 64 boxes... thus... in the worst case... we need atleast 6 bits.. to distinguish all d boxes dintinctly

- ayushsethi22031992 August 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's good enough to only represent one position. We need to represent 2.

- pretonesio August 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

lets see the possible number of combinations possible
8*8*8*8/2 = if positions mutually independent = 12 bits
otherwise
8*8*(8*8-1)/2 = 2016 combinations
total number of combinations possible with 3 bits=
0,1,00,01,10,11,000,001,010,011,100,101,110,111
2+2^2+2^3 = 14 = 2 (2^3-1)
total combination with 10 bits=
2(2^10-1)= 2046 combinations.. i will update the answer with a logical division or some1 can work it out

- kkr.ashish September 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

combinations for one 8x8 grid = 64
we have two pieces to take into account = 64 *2
two pieces cannot occupy the same space = (64 * 2) - 1
how many bits we need = floor(Lg2((64*2) - 1)
answer: 6

- paul.nikonowicz September 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There are 64 squares and 32 pieces.
I take it, that 2 positions means the state of ALL of the white and black pieces at a given time or a "snapshot".
To represent 2 positions: won't you need 32 longs (each with 64 bits), so that each long represents a chess piece and each bit (long has 64 bits) in that long represents the position on any one of the 64 squares.

- game October 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

what do you thing about this solution:
we can use 5 bits for the white squares and 5 bit for the black squares.
then you have another bit to tell if you need to refer to a white or a black square
i think even you can do this only with 6 bits:
one bit is for the color and let say if color is white then you go to the 5 bit positions by starting at 00000 and if is black you start at 00001 then each loop you move two positions

- Avraham August 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I dont know where you all get those ideas...

An 8x8 chessboard with two pieces, where each position is represented as tuple (x,y) and the two pieces using two tuples as a set (since order does not matter), like {(x1,y1),(x2,y2)}...
That is the basic mathematic abstraction of the input space. Now for the real question. We are to find the number of all possible, different tuple-sets, which is given by

256!/(254! 2!) - 256 = 32384

Minus 256 in the end, because thats the amount of tuple-sets, where both tuples are equal, a case that is not possible.

Now that makes 14 < log2(32384) <15, so we can conclude that we can save one bit, that is encode the whole thing with 15 bits instead of the obvious 16...

- Anonymous September 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

You realize, with the way this question is asked, the answer of '2 bits' suffices. You are only asking bits to represent two positions out of 64 positions, not every possible combination of the 2 positions on the board...

- John December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not a very plausible interpretation of what the question asker likely meant.

- Anonymous December 18, 2013 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More