We pay for user submitted tutorials and articles that we publish. Anyone can send in a contributionLearn More
The eighth post of the series of programming job interview challenge is out. 68 readers provided answers to job interview challenge #7 and most of them had the correct solution. As rvh mentioned, the trick here was to understand that the round table has a symmetric shape and: 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. I couldn’t describe the correct answer better than Yoav Zobel, as he was the first one who also formally proved his algorithm:
The Correct answer (as provided by Yoav Zobel):
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.
2 Readers wrote blog entries about last week’s challenge:
Those are the commentators who answered correctly:
wasabi, William Ellis, Rudi Angela, Caio Romão, Yoav Zobel, Mike, Jonathan Gilbert, Chris Jobson, Igor Ostrovsky, Tim Niblett, Abhijit, ER, raj, rvh, Christof Jans, jiji, Demie, u8ijk, David Avraamides, Trevor, Sajid Umerji, Loz, Pieter G, Cruise, BA, zack, herbie, xyzzy, Mike Harris, Jim Lebeau, Alex, Justin Henzie, Mark R, Leo, andrew, Mike Stok, Joost, Jamie Macey, Adrian Quark, Tom A, Rodrigo Marcuschi, Tom Ritchford, Anton Irinev, Dustin, Michael, Matt, Fahri Basegmez, Michael Mrozek, Binil Thomas, Hal, Ali Pang, Ben Kavanagh, Krystian Cybulski and Vivek.
As to the wrong solutions, due to the fact that there were a very small amount of them and I didn’t see the same mistake twice, I won’t get into details about them. But, if someone wants an explanation, please leave a comment and I will answer immediately.
This week challenge:
You are writing a software component that receives a binary record every 20 millisecond. Your component function as a pipe, meaning it can’t store the binary records, it should do whatever needed on the current record and than pass it to the next component in the pipeline. Your component goal is to alert whenever it identifies a specific expression (which is provided at the initialization process) in the stream of records - you are looking for a specific combination of binary records. If the incoming records assembles such a combination (with the other ones that came before it), alert about it (raise an event, for instance). Provide the most efficient algorithm to solve this problem, just remember the following issues:
Reminder: You can provide your answers either by leaving a comment or by posting it in your blog (better). Comment with answers will be approved only next week, because if readers will see the correct answer in one of the comments, it will become pointless.
Tags :challengeexpressionjob interviewObjecctOpponentPatternpipequestionrecognition
Copyright © 2012 Dev102.com
Breeze : Designed by Amit Raz and Nitzan Kupererd