Bloomberg LP Microsoft Interview Question
Software Engineer / DevelopersRohit, we do have a solution as stated above by Kapil "Its not possible". The chess board has 64 squares, 32 white and 32 black. when you remove the diagonal squares you either remove 2 white or 2 black squares and you would be left with 30 white and 32 black or 30 black and 32 white. No matter where you place your domino, each domino will cover one black and one white square. Using this reasoning, after you have placed 30 dominos you would have covered 30 white and 30 black squares. However the remaining 2 squares on the chess board are both white or both black. So there is no way that they are going to lie next to each other for you to place the last domio.
All the genius' above, have you considered the possibility that the interviewer did not place any restriction on the way each domino is placed.
Hence you do not have to assume that each domino will occupy 1B and 1W, some of then can also occupy 2B or 2W if placed diagonally. If you have some time try it out, IT IS POSSIBLE...
To start you off:
Assume the top left is square 1 and the square below it is square 9. remove squares 8 and 57
Place the first domino covering squares 1 and 10 both are same color. However all are not diagonal, some are vertical and spome horizontal as well
Consider it to be a Complete Chess Board with 64 small Squares. This square can be filled with the Dominoes perfectly. Now Notice that on removing the cells in the question(from Corner), you remove the cells of similar colour, also , you are left with 62 cells. After arranging the Dominoes for 60 cells, The Dominoes can not cover the remaining two cells of similar colour as these will not be adjacent.
You can't. Every domino will sit on one white square and one black square. Squares at opposite corners are of the same color, so after removing two opposite corners you're left with 30 white squares and 32 black ones (or vice versa). At best you can put down 30 dominoes, each of which will use up one white and one black square, but after that you'll be left with two squares of the same color. These can't be next to each another, so your last domino won't go anywhere.
- srihari January 12, 2006