Hacker News Reader

>> Log_2 1000.

Actually that's the maximum number of guesses needed (assuming you're aware of the binary search concept), not the minimum. The minimum is 1. This is a trick question and you have failed the first interview question and have been shown the door... Good illustration of why the questions are, in fact, ridiculous unless they are just used as a "jumping off" point for discussion (which is rarely what happens, IME).

I call bullshit. The minimum number of questions is this context implies the minimum number you need to ask to be guaranteed to find a solution. Any other interpretation is meaningless.

But of course, the safe answer would be to explain it in the verbose way and not just shout out "TEN".

I considered this, but rejected it. If you interpret the problem in this way the answer is dependent on an undefined parameter. The clearest interpretation of the problem, the most useful interpretation of the problem, and also a nontrivial interpretation, is "what is the lowest upper bound on the number of guesses".

"If you had 5,623 participants in a tournament, how many games would need to be played to determine the winner?" Let d = Log_2 N. Sum 2^(d-k) for k = 0 ... d

The a-ha solution to this puzzle is to realize that every participant but one has to lose exactly once. Each game has only one loser, so you need 5622 games.

Your method overestimates the number of games needed because you start counting at 0. (Think about the simple case where N=2.) Even if you started counting at 1, your method wouldn't in general give an exact answer (and would typically under- or over-estimate depending on whether you started counting at 1 or 0, respectively), but if you had a nice power of two (say, 2^d on the nose), then the sum from 1 to d of 2^(d-k) would give you exactly 2^d -1, which agrees with the a-ha answer.

Who said that the game they are playing has two participants with a winner and a loser.

Nobody, but it was implicit in the solution proffered by the post I replied to. If the game they are playing has 5623 participants with one winner and 5622 losers, you only need a single game!

I don't get it - if there are 2 participants, you need N-1 == 2-1 == 1 game to determine the winner. The ah-ha answer still works.

The a-ha answer still works, but the orignal answer given has you sum 2^(d-k) from k =0 to d, so in this example would be 2^1 + 2^0, suggesting that you would need 3 games to determine the winner.

Ah, yes, that is much nicer! Yeah, I did make an off-by-one error as well. Eh, constants. ;-)

Not to be too much of a smartass, but I'd be tempted to say "1" for the "minimum number of guesses" question. After all, you could be correct right off the bat and 1 is a technically correct answer to the ? as stated.

If we're going to be a smartass about it, the question never specifies that we're only looking at integers, so I'm forced to assume we're looking at reals.

Thus the probability of you correctly guessing the correct number within any finite number of guesses is zero.

Given the numbers 1 to 1,000

Seems to me like they're asking for integers, but suppose they mean reals. Depending on the distribution, you can still guess the right number with positive probability. It could be dominated by 500!

I don't think you are being a smartass, I believe that's the only correct answer.

That's also the first thing that came into my mind. It seems to me like a completely legitimate answer.

Depends upon the answer - too low, too high, exactly right? Then sure.

But if the answer is binary then the question is "is it larger than 500" and then no, you can't ever be right in one guess.

This is a good number to use. The full table is:

http://en.wikipedia.org/wiki/Random_close_pack#For_spheres

IIRC, there's a passage in Conway and Sloane's comprehensive review of sphere-packing (the same Sloane as EIS, http://oeis.org/)

http://www.amazon.com/gp/product/0387985859/ref=dp_proddesc_...

that says "much of our effort in this book is to find a packing, in arbitrary spaces, that is as efficient as the simple tetrahedral packing is in R^3".

"How many balloons would fit in this room?" .64 length * width * height (distance measurements roughly in feet).*

Ah, but who said anything about the balloons being full?

And balloons are rarely perefect spheres.

If you want to solve the oblate sphereoid packing problem in an interview... I will hire you to do anything you find amusing and patent the results. :)

Displacement of the zoo environment's pool.

That gives you the elephant's volume. What's the density of an elephant?