That’s it, Times up on the sixth in the series of job interview questions. There were 39 people who answered and the first one to give a correct answer was leppie from the IronScheme project.

The correct answer is that both will return false.

You could sum up the answer by saying Boxing.

An ArrayList hold objects, so when you insert a ValueType into it, it will be boxed and become an object. When you compare List[0] to List[1] you are comparing references, and they will never be the same because they are pointing to different objects. This is the reason for getting the false in both comparison. It is true that in the second comparison you are comparing a double and an int ( 2.0 and 2), but that is not why you get false, it is due to the Boxing.

Damian Brady wrote a beautiful answer in his blog as did Ricky in his blog Crazy Pointer and Siddharth in his blog Some Creativity.

Other correct answers by the order of arrival were by Heiko Hatzfeld, Jason Kikel, Configurator, Jonathan Gilbert, Justin, Ivan, Justin, Tobi, Jon von Gillern, Jonas Christensen, Ryan Emerle, Damian, Jamie Penney, ecco, Rob R, fred, AdamC, sood, kuldip saini, D.L, Jelle Hissink, Xerxes, Greg and pb.

This weeks question:

You are playing the following game:

  1. You and an opponent are placing coins on a round table.
  2. Each player can place one coin on his turn.
  3. Each coin must be placed on the surface of the table (can’t place coins one on top of the other).
  4. The whole coin must be place flat on the table.
  5. All of the coins are of the same size.
  6. 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…

Reminder: Comment with answers will not be approved until next weeks challenge (if readers will see the correct answer in one of the comments, it will become pointless).

Tags :

86 Responses to “A Programming Job Interview Challenge #7 – Coins of The Round Table”


  1. wasabi

    Said on June 9, 2008 :

    You start by placing the first coin in center of the table.
    Then every time it’s your turn you place your coin diametrically opposite to the other players coin.

    So if he has a place to put his coin, you got one as well. Plus you have the center one.

    You are the winner.

  2. William Ellis

    Said on June 9, 2008 :

    The solution is a simple one. On a circular table, place your coin in the exact center of the table as your first move. Your opponent will then place a coin somewhere on the table.

    The key to this game is to mirror your opponent’s move exactly. Place your second coin in a position mirror that on where your opponent placed their first coin. By doing this, you will have an answer to your opponent’s every move, and your opponent will be the one to exhaust the available moves first.

    Consider the base case – a round table that can only hold one coin. You automatically win – he can’t place his coin on top of yours. Expand the case out, to a table with a diameter three times that of the coin (the smallest possible case that allows multiple coins to be placed given our strategy). So long as you place your coins opposite where your opponent places them, you will place the last legal coin and force your opponent to lose the game.

  3. Rudi Angela

    Said on June 9, 2008 :

    Here’s my algorithm:
    On first turn, place the coin precisely in the middle of the table.
    On each following turn, place your coin ‘point-symmetric’ to your opponents last placed coin, where the point of symmetry is the center of the table.
    Explanation: after you have placed the first coin, for every space there is to place a coin (on his turn), there is also an identical space at the other side of the table (diagonally that is). The only situation where the two places coincide is the middle of the table, which was already taken by you.

  4. Caio Romão

    Said on June 9, 2008 :

    Well, if you notice that, in a circle, every “point” but the center has a symmetric one, starting at the center and then placing every other coin in a symmetric position to the one your adversary placed, your win is assured, because every time your opponent can place a coin, you can.

  5. Yoav Zobel

    Said on June 9, 2008 :

    The algorithm is pretty simple:
    1. Place the first coin right in the middle of the table.
    2. For the next coins, put each coin in the direct opposite of the coin that your opponent placed (same radius on the opposite side).

    You will always win.
    I’ve thought of the formal proof (reductio ad absurdum):
    Let’s say I followed the algorithm, and let’s assume I lost, since I didn’t have a place to put a coin. We know it’s not the first turn because in the first turn the table is empty.
    Now look at the last coin placed by my opponent on the table (in the previous turn). The opposite place of this coin is surely not vacant (because if it has been vacant, I would have a place for my coin). Since it’s not vacant, there must be another coin blocking (even partialy) this space.
    Now let’s look at this “blocking” coin. It could have been placed either by me or by my opponent.
    1. If it was mine, then I’ve must have placed it after the opponent placed a coin in the opposite side. But we know that it’s not possible since the opponent wouldn’t have a place to put his last coin.
    2. So it must have been my opponent’s coin. But that option is not possible as well, because if my opponent indeed put this coin, then right after that I would have put my coin in the opposite side. Again, this is not possible since the opponent wouldn’t have a place to put his last coin.
    So we ruled out all of the options, so now we know that if I’ve followed the algorithm, there’s no way I’ll lose the game.

    Horray for me! :-)

  6. Mike

    Said on June 9, 2008 :

    Place your first coin in the center of the table. Make following moves mirroring your opponents last move (i.e. same distance from the center, on the opposite side of the table as your opponents move).

    Since all your moves (except the first) have been mirrored moves, if your opponent has a move available, you will also — meaning that your opponent will be the first to be unable to make a move.

  7. Jonathan Gilbert

    Said on June 9, 2008 :

    The first player should place a coin in precisely the center of the table. Wherever the second player places his coin, the diametrically opposite space will be open for the first player. When the came comes to an end, there will be exactly enough room for two coins, in diametrically opposed positions, and player 1 is guaranteed to place the last coin.

  8. Chris Jobson

    Said on June 9, 2008 :

    Place your first coin with its centre at the exact centre of the table. Thereafter if your opponent places his coin at position (r, theta), using polar coordinates based at the centre of the table, place your next coin at position (r, theta + 180 degrees), i.e. opposite his coin but on the other side of the centre. This is guaranteed to win since after each of your moves the position is symmetrical, and if there is space for your opponent’s next coin there is also space for your next coin.

  9. Igor Ostrovsky

    Said on June 9, 2008 :

    This is a classic puzzle.

    To always win, you choose to take the first move, and place the first coin in the center of the table. Then, always place a coin so that the center of the table is a center of symmetry of all coins on the table.

    That way, your opponent is guaranteed to be the first one who cannot place a coin.

  10. Edward Shen

    Said on June 9, 2008 :

    Ah.. the traditional round table mind bender…
    Make sure to add rule 7:
    7. Coins are smaller than the table.

  11. Tim Niblett

    Said on June 10, 2008 :

    Place a coin in the center, when opponent places coin place yours radially opposite. This means if you draw a line L from your opponent’s coin to the center coin then place your coin in the reflection of your opponents’s coin wrt. the diameter perpendicular to the line L

  12. Baja

    Said on June 10, 2008 :

    And that you can’t move other coins around :)

    Anyway, how is there any way to solve unless you can guarantee that your opponent will place coins in some predetermined pattern beforehand, e.g you might plan to pack coins in as tightly as possible (triangular pattern), your opponent might be placing coins 0.999xdiameter from other coins, but you won’t know until after you start, and even then, they don’t even have to consistently follow this pattern (they might switch to placing coins 0.5xdiameter away from other coins). So… are we to assume that they are always following the “place coins so as to form a packed triangular structure” pattern which would make this problem tractable? And then, do the coins have to fit inside the bounds of the edges of the table? i.e. no overhanging bits?

  13. Shahar Y

    Said on June 10, 2008 :

    Hi Baja,

    1) You can’t assume anything about your opponent moves. He can do what he wants as long as he is following the game rules.
    2) Yes, coins have to fit inside the bounds of the edges of the table.

  14. Abhijit

    Said on June 10, 2008 :

    Place the first coin in the center of the table. Then let the opponent place his coin. After that place your coin in the exactly opposite side of the table in symmetry. In this way we will always have a place to put our coin.

  15. Abhijit

    Said on June 10, 2008 :

    Place the first coin in the center of the table. Then let the opponent place his coin. After that place your coin in the exactly opposite side of the table in symmetry. In this way we will always have a place to put our coin.
    So the algorithm will be that when the opponent places a coin at point say x,y at (20,-40) then we will place our coin at (20,40).

    Thanks

  16. leppie

    Said on June 10, 2008 :

    Dang Edward, that was my answer! hehe, just kidding :)

  17. Kevin

    Said on June 10, 2008 :

  18. ER

    Said on June 10, 2008 :

    This seems straightforward. Always take the absolute center point of the table, centering your coin on it. After EVERY opponent move, duplicate their move (with your coin) exactly opposite along the diameter of the table described by the center of their coin and the table center until the final move. The symmetry of the circular table requires an opposite move for you every time until you make the final move.

    Imagine you have a table of diamater 2*pi*r, and coins diameter (2*pi*r)/3 (which is 1/3 of the diameter). This is the largest coin you can actually play with and not win in a single move (by grabbing the center). You grab the center position. Opponent MUST take a tangent point to your coin (or be off-table). You select opposite – there are now three coins in a row. NOW, opponent can take a skewed position, which you answer (you win) or a tangent-to-two-coin position, leaving 3 spots. You take the opposite tangent position, leaving 2 spots. Opponent is forced to take 1; you take the other, you win.

    ER

  19. website design

    Said on June 10, 2008 :

    parameters: area of table, size of coins
    divide. get count of coins needed. check for remainder. if remainder exists then you know you should go first.

  20. ben

    Said on June 10, 2008 :

    Do you know the accurate relative sizes of the coins and table? Can coins be moved once they have been placed on the table?

  21. raj

    Said on June 10, 2008 :

    put your first coin in the exact middle of the table. after that mirror his placement.

  22. rvh

    Said on June 10, 2008 :

    Solution to Job Interview Challenge #7:

    In order to explain the algorithm, first imagine a x-y Cartesian coordinate system on the table with the origin at the center of the table.

    Game Algorithm:
    1. For the first move, the player places the first coin at the center of the round table (0,0).
    2. The opponent places the coin anywhere available on the table, at position (x,y).
    3. The player mirrors the opponents last move by placing the coin at the position (-x,-y).
    Note: It must be mirrored with respect to both x and y. Placing at position (x,-y) or (-x,y) can easily lead to a loss.
    4. Steps 2 to 3 are repeated until the opponent runs out of available spots to place the coin and thus loses.

    Actually this algorithm isn’t limited to just a round table. It will work with any shape that is symmetric with respect to both x and y axes.

  23. Shahar Y

    Said on June 10, 2008 :

    Hi ben,

    1)Yes, you know the accurate relative sizes of the coins and table. But, pay attention that your opponent can place coins with spaces between them…
    2) No, coins can’t be moved once they have been placed on the table.

  24. Christof Jans

    Said on June 10, 2008 :

    On your first move, place your coin in the middle of the table. Then, each time your opponent places a coin, place your coin exactly opposite of his coin (at the same distance from the center as his coin, but on the opposite side). Eventually your opponent will run out of places to put his coin and you win.

  25. jiji

    Said on June 10, 2008 :

    simple:

    1. place the first coin in the center of the table
    2. let the opponent place a coin anywhere
    3. place your next coin in the opposite position on the center of the table from the coin in 2
    4. keep mirroring your opponents coins position with respect to the central coin

    you will always have place for a coin because you opponent will have a position and you will have the opposite one => pairs of opposite positions

    when all pairs are occupied, it’s your opponent’s turn so you win

    be careful to mirror his moves exactly

  26. Damian Nikodem

    Said on June 10, 2008 :

    the one solution I can think of is..

    Place a coin directly in the center of the table.
    assume tR to be the radius of the table. the coin has a radius between tR/2 and tR.

    Any other solution would allow the player to have a turn and towards the ‘end of the game’ in any set of circumstances there would allways be one option remaining just enough room for only 1 coin.
    And because coins can be distributed in any manner over this table it leaves the computation of the entire game up to chance. Therefore the only solution for this problem is to define either the coin or the table to have a ratio that only allows for one coin to be placed.

  27. Demie

    Said on June 10, 2008 :

    I’d say this is pretty easy if you get to go first.

    Your first move should be to place the coin precisely in the middle of the table.
    After that, whenever your opponent places a coin on the table, place your coin exactly on the opposite side of the table. Since they can’t overlap, you will always have a free space to place your coin and eventually your opponent will run out of space.

  28. u8ijk

    Said on June 10, 2008 :

    Winning strategy: place the first coin in the center, place every other coin in the symmetric spot (wrt to the center) of the previous opponent move.

    Proof: By induction: assuming that at least 1 coin fits in the table, you won’t lose at the first move. If the game got to the n-th move, there are two possibilities: either the (n+1)-th coin of your opponent doesn’t fit (-> you win) or it fits, and in this case your next coin will fit too, since after each one of your moves the coins on the table are symmetric wrt to the center, hence the free areas are symmetric, too.
    Therefore, you can’t lose at the n-th move.
    Since the game is obviously finite, and you can’t lose in any move, you win. CVD.

  29. David Avraamides

    Said on June 10, 2008 :

    You go first and place a coin in the exact center of the table. From that point on you always “mirror” the placement of your opponent: if he puts a coin next to the one you placed on the center, then you do the same on the other side, 180 degrees from his coin. If he places one on the edge, you do the same on the other side of the table.

    Since the table is symmetric, you will always be able to place a coin at the equivalent location on the other side of the table until there are no more open spaces for your opponent to move. The only non-symmetric location is the center of the table, which you already covered.

  30. Trevor

    Said on June 10, 2008 :

    Place your first coin in the exact center of the table. Then, whenever your opponent places a coin, place your next one exactly opposite the center. This means that if he can place a coin, you will always be able to as well.

  31. Sajid Umerji

    Said on June 10, 2008 :

    The winning strategy is simple.

    Place the first coin in the center of the table.

    Whenever your opponent places a coin on the table, imagine a diameter (the table is a circle) passing through his coin and the coin in the center.

    If his coin is a distance x from the center, then place your coin a distance -x from the center.

    This will ensure that you will always be able to mirror his moves and that you will therefore always be the last player able to place a coin on the table.

    QED

  32. Loz

    Said on June 10, 2008 :

    Put your coin in the centre of the table, than place your coins diametrically opposite wherever your opponent plays.

  33. pg

    Said on June 10, 2008 :

    This reminds me of a game I used to play when I was a kid. The goal was to be the one that said “21″. Two players start counting from 1 to 21, and can say only one or two values each time. The way you can win is by always making sure that if you say one or two numbers, you can controll the other to end up in 19 or 20. I guess the solution here is to always make sure to place a coin so that the remaining “area” is divisable by 3 coins … or something like that.

  34. Pieter G

    Said on June 10, 2008 :

    A strategy to always win would be:

    start with the first coin dead in the center of the table.

    after this first move you wait for the opponent to place his coin.

    when he places it you must place your coin on other side of the table, mirroring his move ‘though’ the center piece.

    this spot is always free.
    (if in a previous move a coin ended up there, one would have also ended up at the spot our opponent jsut played).

    becassue of the symmetry WE always have a move to make, but eventualy the opponent wil run out of spots to put his coin.

  35. Cruise

    Said on June 10, 2008 :

    1. Make your first move in the exact center of the table.
    2. Mirror all of your opponent’s moves.

    Since your first move is in the center, no matter where your opponent moves you will be guaranteed to have room on the exact opposite side of the board.

    Ironically this is a well-known losing strategy in the game of Go.

  36. BA

    Said on June 10, 2008 :

    Dead center for your first move, then mirror your opponent for every other move.
    By placing dead center, you occupy a space that cannot be mirrored by your opponent. By then mirroring your opponent, you are always placing in spots that can be placed in.

  37. zack

    Said on June 10, 2008 :

    On your first move, put your coin directly in the center of the table. Wherever your opponent places their coin, put your next coin diametrically opposed to theirs. Keep doing that and you will win.

  38. herbie

    Said on June 10, 2008 :

    Solution:

    Place the first coin in the center. Mirror every one of your opponents moves. Mirroring means to place your coin on the same diameter line as theirs an equal distance from the center. By this definition, if they can place one at any space, no coin has placed in the opposite space. This continues until all viable space has been filled and they have no more options.

  39. Ben

    Said on June 10, 2008 :

    I think I’ve solved it: On each turn place your coin into the middle of the largest gap on the table.

    On the first turn this would obviously be the middle of the table.

    This will work because after placing the coin into the largest gap there will either be no room for any more coins, in which case you have won, or there will be room for more than one coin (because you placed the coin in the middle of a space there should be relatively equal room around it).

  40. xyzzy

    Said on June 10, 2008 :

    Place the first coin in the centre of the table.

    Whenever your opponent places a coin, place your coin at the reflection of their coin about the centre.

    This place is always vacant, so you will win the game.

  41. Mike Harris

    Said on June 10, 2008 :

    Place your first coin in the exact center of the table. For every following coin, place your coin exactly opposite the coin your opponent just placed. Imagining a line representing the diameter of the table that intersects the center and your opponents coin, your coin should be on that diameter, exactly the same distance away from the center as your opponent’s coin (but on the opposite side of the table).

  42. Saurabh Khurana

    Said on June 10, 2008 :

    Please find the solution at –

    http://khuranasaurabh.blogspot.com/

    Thanks

  43. Jim Lebeau

    Said on June 10, 2008 :

    Place the first coin centered at the center of the table. Then whatever move your oponent makes, place your coin in the exact oposite position relative to the center of the table. Thus, after your oponent places his last coin, you place your last coin, and win.

  44. Alex

    Said on June 10, 2008 :

    My solution would be to be a total copycat.

    1)Start off by placing your first coin dead center on the table

    2)Let Opponent Move

    3)Place your coin the same distance from center that his coin is, but on the opposite side of the table.

    4) Repeat steps 2 and 3 until the table is filled up.

    This should work because since coins are going down in pairs (after you’ve taken care of the center coin), he can only place a coin down in a space who’s opposite, “sister space” is available.

  45. Justin Henzie

    Said on June 10, 2008 :

    Simply place the first coin in the very center of the table, thereafter, symmetry guarantees that wherever your opponent places their next coin there is guaranteed to be an opposite location for you to place your coin.

  46. Mark R

    Said on June 10, 2008 :

    Question: are you allowed to move coins that have already been placed on the table? If not, I have a simple solution.

    You start first and put a coin in the exact center of the table. Now for every coin placed by your opponent, you place one at the same distance from the center but on the opposite side of the center. This maintains the symmetry of the table, and guarantees that as long as your opponent can find a place to put a coin, you can as well.

  47. Leo

    Said on June 10, 2008 :

    Solution:

    For the first move, place one coin in the exact center of the table.

    Afterward, whatever your opponent does, make the move on the opposite side of the table that maintains the symmetry of the coins (radial symmetry).

  48. andrew

    Said on June 10, 2008 :

    1. Place first coin in the center.
    2. Whatever the opponent does, do the same but in the opposite direction from the center, eg. if the opponent places the coin at 0.35 radius of the table at 89 degrees from some common reference position in the last move, place the coin at 0.35 radius at 271 degrees.
    3. This induces a symmetry, such that if the opponent can place a coin, you have a symmetric position to place your coin, and if the opponent cannot place a coin, you also cannot, but the opponent encounters that situation first so you win!

  49. Mike Stok

    Said on June 10, 2008 :

    Solution:

    For the first move place the coin on the centre of the table. After that just duplicate your opponent’s move diametrically across the centre. As you are following the opponent and creating a symmetrical pattern there must be space “opposite” wherever the opponent plays, so the opponent will be the first to discover the table is full.

  50. Joost

    Said on June 10, 2008 :

    Easy, just place a coin in the middle of the table and for every move your opponent makes, take the mirrored (relative to the center point of the table) point to place yours.

  51. Jamie Macey

    Said on June 10, 2008 :

    I hate interview questions like this, as it’s just a race to see who gets the a-ha moment first.

    In this case, it’s a win for player one by playing a coin in the very center of the table, and then mirroring their opponent’s moves with 180 degree rotational symmetry around the center.

  52. Adrian Quark

    Said on June 10, 2008 :

    Make your first move in the exact center of the board. For each subsequent move, place your coin exactly opposite the last coin placed by your opponent (in other words, given a vector from the center of the table to their coin, multiply it by -1 and place your coin there). This is a cheap question because in reality nobody can place coins this accurately.

    Proof: if your opponent has a move, then you have a move, therefore you cannot lose. Proof by contradiction: if you cannot move, that means the opposite position is already taken, i.e. your opponent played opposite an existing coin. But that is not possible. If he played that existing coin, you already played in the opposite spot, and if you played it, it was because he already played in the opposite spot. The only place without a distinct opposite is around the center of the board, and you have already played there. QED.

  53. Tom A

    Said on June 10, 2008 :

    Start by placing your coin in the dead centre of the table. Then place each subsequent coin in exactly opposite where your opponent placed theirs. As long as the opponent has somewhere to go, then so do you, by the symmetry of the arrangement. You’ll need to place your coins very accurately, but you’ll always win.

  54. Rodrigo Marcuschi

    Said on June 10, 2008 :

    How about… placing a coin at the center of the table, and everytime your opponent places a coin, you ‘mirror’ it, i.e. you place it where the ‘reflection’ would be if the imaginary line dividing the table in half were a mirror, so that, if he places a coin, you sure will have a spot to place yours, and he will run out of places to put his coin first.

  55. Tom Ritchford

    Said on June 10, 2008 :

    This is not a good interview question.

    What does it tell you about someone’s engineering ability? Little. It’s a brain-teaser; either you get it or you don’t.

  56. Tom Ritchford

    Said on June 10, 2008 :

    And the answer is that the first player places the coin in the center of the table and then proceeds to place his coins radially symmetrical to the other player. First player win.

    This is true in the case that you’re only allowed to play on the top of the table. :-D

    If you have glue and are allowed to play on the bottom of the table too, then it depends on whether the table has a central support on the bottom; if it does, it’s still a first player win, if it doesn’t (suspended by wires?), it’s a second player win (they respond to the coin in the middle of the top with a coin in the middle of the bottom).

  57. Shahar Y

    Said on June 10, 2008 :

    Tom Ritchford,

    1) That is your opinion, and it is fine.
    2) My opinion is that thinking is much more important than knowing the syntax of a specific programming language. Languages change all the time, a good thinker would easily learn new syntaxs. If you consider yourself as a software developer than you should know how to solve puzzels. I do agree that you can’t base your opinion about someone according to just one question, but this is not a real job interview, it is just for the challenge and for fun :)

  58. Alex

    Said on June 10, 2008 :

    My browser keeps hating on me and giving error messeges every time I submit, so if I already posted an answer, I apologize…

    My solution is as follows.
    1)Since you’re going first, place the first coin in the dead center of the table.
    2)Let opponent move.
    3)In your head draw an imaginary line through the center of the table that intersects with the coin your opponent placed. Place your next coin on that line, the same distance from the center as your opponent’s coin, but on the opposite side.
    4) Repeat steps 2 and 3 until you emerge victorious.

    This should work because after the first dead-center coin, the coins are essentially being laid down in pairs. Each potential coin position only has one opposite position, and it’s reflexive: if position a’s opposite position is position b, than position b’s opposite is position a. In other words, as long as you follow this system, no matter where your opponent places a coin, you will have a matching empty position where you can place a coin.

    In practice, given a big round table and a stack of quarters, it would be impossible to eyeball this system to the degree of accuracy required to pull this off (and your opponent could probably use your error in gauging distance to mess you up by clustering coins,). However, this is a hypothetical situation, and a sound algorithm-assuming you can gauge distance perfectly or have a computer do it for you:)

  59. Anton Irinev

    Said on June 10, 2008 :

    place first coin in the center and repeat opponent’s moves symmetricaly

  60. Dustin

    Said on June 10, 2008 :

    The answer is this: Place the first coin in the center of the table (center of the coin should be exactly in the center of the table). Since the table is circular, it is symmetrical, which means any place your opponent places a coin, you should place your coin in the corresponding point to keep the table symmetrical. Since you took the only point to not have a corresponding point (the center), you will be able to counter every move your opponent makes, and eventually he will run out of places to put a coin.

  61. Jörgen

    Said on June 10, 2008 :

    Place a coin with diameter > table radius.

  62. ElmerFudd

    Said on June 10, 2008 :

    (1) place your coin in pocket
    (2) walk out the door
    (3) buy lunch
    (4) find a different place to interview

    Quoting from:

    http://www.speakeasy.org/~jmabel/brain1.html

    my favorite reason NOT to engage in this nonsense:
    “The interviewee may already know the problem. If he/she is dishonest, and a moderately good actor, he/she can appear (falsely) brilliant. You’ve just enhanced your chances of hiring a sociopath.”

  63. Dustin Potter

    Said on June 10, 2008 :

    this is like the bat game (hand-over-hand). the first 99.9% of the game makes no difference, it’s how well you work backwards from the very last move that matters. here’s my answer by level of detail…

    level 0: to win you just make sure that only an odd number of coins will fit on the table, and thus that you will go last. how?

    level 1: once the table is mostly full, you’ll be left with “holes” to try to fill with coins. the most minimal holes we’re interested in are those that will allow either one or two coins, depending on the spacing. place coins with the goal to get down to the point that these are the only holes left. you can now control the game and force a win. how?

    level 3: so you’re down to only minimal “double” holes and it’s your go. if there are an odd number of “doubles”, start with a “block” (a double hole with a single coin taking up the whole hole). if there are an even number of holes, start with a “pass” (placing the coin so a second coin will also fit in the same hole). after this, it’s tit-for-tit. if your opponent plays a “block”, you do the same. at the end there will either be an open “double” for you to play as a “block” for the win, or your opponent will be the one to start helping you fill in an even number of “pass”‘ed “double” holes, which means you’ll get the last placement and therefore win.

    level 4: an opponent who knows how level 3 works will likely be able to manipulate the game so that the “double” holes are all filled by the end of the game and it’s down to filling a single large hole with room for more than two coins. at this point it’s essentially a recursive problem. the hard parts are the precise estimation of coin size vs. hole size and physically placing them such that they block the area you need them to. no algorithm can do that for you… so the skill is in placing coins so that your opponent mis-estimates the distances or mis-counts how many coins will fit in the available holes. in a computer vs. computer match, whoever goes first always wins tho…

  64. Josh

    Said on June 10, 2008 :

    How/where the coins are placed doesn’t really matter.

    No rules say you cannot move coins already on the table.

  65. Michael

    Said on June 10, 2008 :

    I cannot see a place where I can submit my solution, so here it is in the comments:

    Place the first coin in the middle of the table, and then place successive coins opposite to the coin your opponent places. Playing in turn guarantees the opposite side to have an empty space, so you never lose.

    Just wait for your opponent to run out of space.

    Cheers.

  66. Matt

    Said on June 10, 2008 :

    Solution:

    Place the first coin directly in the center, from that point forward copy the moves of your opponent but on the opposite side of the table.

    You will be the last to place a coin because once your opponent’s “half” is full your “half” will still have one more spot, after your move the whole table will be full.

  67. Fahri Basegmez

    Said on June 10, 2008 :

    Place your coin so that:

    1- A line drawn from your coint to your oponnent’s coin goes through the center of the table.

    2- The distance from your coin to the center is the same distance from your oponnent’s coin to the center.

    This way if he can place his coin so can you.

  68. Michael Mrozek

    Said on June 10, 2008 :

    Make your first play in the center of the table. After each of your opponent’s plays, mirror the location of their coin across your center coin and play directly opposite it, the same distance away and 180 degrees around the table. This location will always be free since there is a bijective, symmetric map between his play location and your responding play location. The only reflexive play (which would defeat this scheme) is when distance = 0 (the center of the table), and you have eliminated this option by playing there before your opponent has the opportunity

  69. Grey

    Said on June 11, 2008 :

    If an even number of coins fit on the table let the other player play first.

    If an odd number of coins fit on the table play first.

    An even number of coins fit on the table if the diameter of the table, rounded down is an even number of coins.

    Odd number fit on the if the diameter of the table, rounded down is an even number of coins.

  70. Shahar Y

    Said on June 11, 2008 :

    ElmerFudd,

    You are taking it too seriously… I bet that there are many readers who do think it is a good question for a job interview, so who is right? You can take it as a fun challenge and try to handle it…

  71. Shahar Y

    Said on June 11, 2008 :

    Josh,

    If you are asking, you cannot move coins already on the table, of course.

  72. Binil Thomas

    Said on June 11, 2008 :

    1. On the first turn, place the coin on the exact center of the table
    2. For every coin placed on the table by your opponent, place a coin diametrically opposite.

    Step 1 is always possible because the whole table is empty. Step 2 is also always possible because if it were not possible, it would mean that there is a coin there, which implies either you or your opponent placed it there. If your opponent had placed the coin there, you would have placed a coin diametrically opposite to it – which is a contradiction, because we know that that space was empty until your opponent just placed a coin there in her last turn. Alternatively, if you had placed a coin there (since it is not the center), it means that your were forced to do so by your opponent placing a coin diametrically opposite to it previously – which is also a contradiction.

  73. Hal

    Said on June 11, 2008 :

    Place first coin in center of table. After that, simply mimic your opponents move symmetrically. If he can place a coin, so can you. When he can no longer place a coin, you win.

  74. WarGames

    Said on June 11, 2008 :

    The only way to win is to not play the game.

  75. Ali Pang

    Said on June 11, 2008 :

    Place your first coin in the center of the table. Now for every move your opponent makes, place a coin on the other side of the table (ie rotate 180 degrees around the center coin).

    That way you will always be able to move after your opponent and you will always win.

  76. Ben Kavanagh

    Said on June 11, 2008 :

    To solve this problem I dropped down a dimension to get insight. On the real number line this would be an interval, where the players try to place the last subinterval. To win all player 1 has to put an interval exactly in the middle and mirror the moves of player 2, keeping both sides equivalent. Player 1 can do this in two dimensions by taking the position in the center and whenever player 2 moves player 1 takes the same move rotated by 180 degrees. P2 can never stop P1 from taking this move as if there is a point on his move that when rotated by 180 degrees is already covered then that point was covered by either a previous move of either P1 in which case the point he is taking was already covered by a previous P2 move -> contradiction; or P2 in which case subsequent move by P1 covered the point he is taking -> contradiction. Since P1 can always take the 180 degree move and eventually space will run out P1 will win.

  77. Krystian Cybulski

    Said on June 12, 2008 :

    1. You place your first coin in the very center of the table
    2. Your opponent places his coin anywhere
    3. You place your coin the same distance from the center of the table directly opposite of the table from his coin. If you imagine a line between your coin and his, that line’s center would be the table’s center.

    Why it works:
    After your opponent makes a move, you are always guaranteed to have a place for your coin.

  78. ER

    Said on June 12, 2008 :

    Hi Shahar

    I’m on your side. In an interview, who gives a GD about how best to use a friend class. You HAVE to prove that you can think creatively. When I first got to this site (reddit?), I thought I’d see lots of brilliant over-thinkers, ready to talk about stuff like whether curved nails could work or how to make an underwater vehicle of cardboard. Instead, I see whiners about “I QUIT THIS GAME!” and I’m sorry about that. Keep up the good fight. I got hired for a dCOM job where I had no experience at all. But I could “get” what they were asking me, and when I solved some musical encoding thing, I got hired. The technology comes easily, the thinking doesn’t.

    ER

  79. Mark R

    Said on June 13, 2008 :

    I figured out a way to describe this more algorithmically than my first answer.

    Let coordinate (0,0) represent the center of the table, with x and y axes chosen any way you want – the table is circular, so it makes no difference.

    Play (0,0)
    For each opponent move (x,y):
    Play (-x,-y)

    I’m not sure I would have been able to come up with any of this in the stress of an interview.

  80. Vivek

    Said on June 15, 2008 :

    The answer:

    Place the first coin in the exact center of the table.Thereafter each coin the opponent places, you should be able to place one exactly opposite to it.
    This is a sure win.

  81. Jonas Christensen

    Said on June 15, 2008 :

    Just came home from vacation, but ill give it a quick try its a fun challenge.

    There can be excat 6(even) coins around an other coin. Assume you alwase place the coins next to each other, the one starting will win. If you dont as the challenge suggest its an other issue :).

    Step 1: Place the first coin anywhere on the table.

    Step 2: When he place his coin check if there can be an equal or odd amount of coins around it. If equal dont place your coin around it, if odd place it.

    Keep doing step 2 till you win.

  82. Jonas Christensen

    Said on June 15, 2008 :

    Edit:

    Step 2: When he place his first coin check if there can be an equal or odd amount of coins around it. If equal dont place your coin around it, if odd place it there.

    If equal; make sure there are space for 2 coins.

  83. Ricardo

    Said on June 14, 2010 :

    This is a bogus problem. The question is how many coins can the table hold? if it’s even, then you always loose if you’re the first player, if it’s odd, then you always win if you’re the first player. There’s no strategy to win unless u know how if the number of coins that fit in the table is odd or even. –Ricardo

  84. Brian

    Said on January 25, 2011 :

    The solutions suggesting that someone placing a coin at the center, followed by the symmetric addition of subsequent coins assumes that the second player will place the coin in such a way as to maintain either hexagonal packing or a d6 symmetry.

2 Trackback(s)

  1. Jun 16, 2008: A PROGRAMMING JOB INTERVIEW CHALLENGE #8 - A NEEDLE IN A HAYSTACK | Dev102.com
  2. Jun 18, 2008: Honest Illusion : DEV102's Programming Job Interview Challenge #8

Post a Comment