Amazon Interview Question
Software Engineer / Developersif the turns are even, opponent should first,
if the turns are odd, we should start first.
Assuming that we know the area of the table and the coin in advance, we can divide the table in to multiple slots where the coins can be placed in a structured manner. If the first player should always win then make the number of slots odd.
The first post assumes that every circle on a table can be filled by even number of coins. What if circle can be filled by odd number of coins.
Erik,
Suppose the first player places a coin in the exact center.
Now no matter where the second player places the next coin, the first player will place the coin in a diametrically opposite fashion.
And, the matter of "filling" the table with odd/even number of coins... So what if you can? How does that particular arrangement of coins prove anything?
In this case, the first player _forces_ an arrangement, such that he always has a spot to put a coin in. Does not matter how you can fill the table with some other arrangement.
I agree with try4fun's solution but there might still problem if
the size of perimeter of circular table is not good enough to hold even numbers of coins.
So, logically his ans is perfect but does not make sure that his algorithm works.
1. put your 1st coin in the center.
- try4fun December 08, 20082. wherever your opponent put his coin, place your coin in the mirror position based on your 1st coin.
Reason: whenever your opponent can find a place, so will you.