|
244. Given a 4x4 board with pieces in it ....
Microsoft Interview Questions and Answers
(Continued from previous question...)
244. Given a 4x4 board with pieces in it ....
Question:
Given a 4x4 board with pieces in it, find if the board has 4 identical pieces. Each piece has a shape and a color. Two pieces are identical if have the same shape and color. The pieces for this board have 6 colors and 6 shapes.
maybe an answer:
board nxn, s - shapes, k - colors.
I encoded each piece as follows:
Shape_0 has colors 0, 1, ... ,k - 1
Shape_1 has colors k, 1, ... ,2k - 1
...
Shape_s has colors s*(k-1), 1, ... ,s*k-1
Using an array/hastable, we can count the "numbers" from the board. When we found in a slot the value n, we return true.
Space O(s*k), time O(n^2).
maybe an answer2:
Take a hash table where the key and the color as the key.
Now traverse every square on the board and insert this into the hash. If already there then increase the freq in the hash.
Once the value of any hash is 4 then return true
Time Complexity : O(NXN)
Space Complexity : O(NxN)
(Continued on next question...)
Other Interview Questions
| 