I've been debating for awhile now about what my first post on my development blog should be. Should I write a brief intro about myself? Describe some of the projects that I'm working on? Talk about some of the technology I'm interested in? After a few months of putting this off, I figured the best way would be to simply dive right in and forget the intro. So here goes:
Recently, I have been following a weekly series of programming job interview questions posted on dev102. For those unfamiliar with the series, basically every week a sample programming interview question is posted. Readers then submit their answers via comments / blog posts. At the end of the week the optimal solution is revealed along with everyone's submissions and the process repeats itself. The following question is the 7th installment of this series:
You are playing the following game:
-
You and an opponent are placing coins on a round table.
-
Each player can place one coin on his turn.
-
Each coin must be placed on the surface of the table (can’t place coins one on top of the other).
-
The whole coin must be place flat on the table.
-
All of the coins are of the same size.
-
The last who can still place a coin on the table wins.
Assuming that you gets to start playing first, provide
an algorithm that will always win this game. You don’t have to write
code, it is much more important that you will explain your solution -
how it works and why will it win the game.
Can you solve this problem? Accept the challenge and provide your answers…
My solution:
On the first turn I place my coin (call this coin A) in the center of the round table. After my opponent places his/her coin (call this coin B) somewhere on the table, I place my coin (call this coin C) in a way such that all three coins (A, B, and C) are in a straight line with coin A directly between coin B and coin C. I repeat this process for each of my opponent's turns, placing my coin exactly opposite my opponent's last coin, until the game is over.
The reason this works:
Before my opponent places his/her coin, the table will always be perfectly symmetrical. This means that no matter where my opponent moves, I will always have the same move available to me on the opposite side of the table. Therefore, since I will always have a move available to me on my turn, there is no way for me to lose.
Enjoyed this post? Share it with others!