Suppose you have 9 balls and one of the balls is lighter in weight than the others. You also have a simple weight machine. You get two tries to use the machine and your goal is to find the lighter ball.
I've seen that before, but I don't remember the answer. I would take an honest stab at it, but I would also mention that it may be an unintuitive question but it is not a particularly good interview question and it would make me less likely to work there.
wait, crap, this is easy.
weigh three balls vs another three. If they're equal, the third group is the one with the lighter ball, otherwise one of the two groups is. Now weigh two balls out of the group of three you identified in the first weighting, with similar logic. -- er yeah, like what Yofaycesux and Commander Jameson and probably others have already said.
I still stand by my claim that this is a bad interview question. There isn't that much interesting thinking that gets someone from the question to the answer, which means it doesn't tell very much about the candidates. And therefore, it suggests that the hiring organization doesn't know how to look for good candidates and may in fact have a bunch of bad eggs (technically unsound, poor team players, etc).
I get this pretty much every interview.
And this is the
other reason it's a bad interview question: because interview veterans will have remembered this.
I
guess it's kind of interesting insofar as it suggests people who remember it or figure it out on the spot know about binary search type methods, but that seems like a reach to me.
At least
FizzBuzz is some kind of useful filter.
Psssh, typical nonsense response from someone who doesn't know what they're talking about. I interviewed someone once and totally asked them how many ping-pong balls could fit in a 747.
I disagree. The estimate question you posed is a more interesting question than the one posed in the OP, and it worries me that you seem to think they're equally good as interview questions. I think this ping pong ball estimation game gives a few more chances to go on the right track or wrong track and therefore has more ways to tell me if a candidate is a good one or not.
Huh? Maybe I'm not understanding your post, but it sounds like you're saying the problem is that you can't judge someone's ability to think under pressure when they're in an interview because that would be asking them to think under pressure.
The number of days on the job (any job) I've had where I had to think under that much time pressure - and without recourse to references like books or internet - have probably been zero. Just what kind of software development is this? These kinds of 'simulated pressure' aren't good simulations for what you're actually interested in finding out about the candidate.
A game is played between two players on a perfectly round board. Each player has a limitless supply of identical game pieces (think: checkers pieces), in one particular color. Lets say player 1 is white and player 2 is black.
The object of the game is to be the last player to place a piece on the board, or in other words you lose if there is no more room on the board for a piece.
Initially the board is empty, and players take turns placing one piece anywhere on the board.
Having only this information, construct a strategy to win every time. Does this strategy dictate you be given the first turn or does it not matter?
This is actually kind of interesting. Not a full solution, but: I don't think it matters that the board is round though, as long as it's a convex shape. But for simplicity's sake, let's assume the board is the same shape as the pieces and that a piece partially off the board is in an illegal position. Induct forwards from the degenerate cases: (1) the board accommodates exactly one piece, (2) the board accommodates exactly two pieces (in which case the first player actually is guaranteed to win so long as they place their piece to _not_ optimally pack the board, (3) the board accommodates exactly three pieces. The first player should be able to take enough space by eating the center to also be the last player. Basically, a piece controls space around it too. Upon further thought, I think this might be related to a Voronoi diagram drawn inside a circle, with seed points generated by the centers of the pieces in an optimal packing of the pieces?
So I imagine the solution is to generate such a diagram, then count number of segments, then figure out if it's even or odd and therefore whether you should play first or second. Or yeah, what 1138 said.
Actually, Haly's works too and is
much more elegant.
Ever notice how any thread anywhere about programming interview questions becomes a competition? =)
[edit: and just in case it wasn't clear, the whole thing was sarcastic. ronito is a smart dude and really knows his shit when it comes to interviews.]
