4 ms·
Given the numbers 1 to 1,000, what is the minimum number of guesses needed to find a specific number, if you are given the hint 'higher' or 'lower' for each gue
by aphyr 16y ago
Given the numbers 1 to 1,000, what is the minimum number of guesses needed to find a specific number, if you are given the hint 'higher' or 'lower' for each guess you make?
Log_2 1000.
"How many balloons would fit in this room?"
.64 * length * width * height (distance measurements roughly in feet).
"How do you weigh an elephant without using a scale?"
Displacement of the zoo environment's pool.
"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
""You have three boxes. One contains only apples, one contains only oranges, and one contains both apples and oranges. The boxes have been incorrectly labeled so that no label accurately identifies the contents of any of the boxes. Opening just one box, and without looking inside, you take out one piece of fruit. By looking at the fruit, how can you immediately label all of the boxes correctly?"
The fact that no label is correct reduces the degrees of freedom by one, making the problem solvable.
"How many ..."
The packing efficiency of randomly organized spheres is .64. Know this number. Fear it.
- bartonfink 16y agoNot 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.
- hugh3 16y agoIf 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.
- orijing 16y agoGiven 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!
- Fargren 16y agoI don't think you are being a smartass, I believe that's the only correct answer.
- deleted 16y ago[deleted]
- dvdhsu 16y agoThat's also the first thing that came into my mind. It seems to me like a completely legitimate answer.
- JoeAltmaier 16y agoDepends 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.
- deleted 16y ago[deleted]
- mturmon 16y agoThis is a good number to use. The full table is: http://en.wikipedia.org/wiki/Random_close_pack#For_spheres 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://oeis.org/) http://www.amazon.com/gp/product/0387985859/ref=dp_proddesc_1?ie=UTF8&n=283155 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".
- drbaskin 16y ago"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.
- jtdowney 16y agoWho said that the game they are playing has two participants with a winner and a loser.
- drbaskin 16y agoNobody, 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!
- JoeAltmaier 16y agoI 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.
- drbaskin 16y agoThe 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.
- aphyr 16y agoAh, yes, that is much nicer! Yeah, I did make an off-by-one error as well. Eh, constants. ;-)
- georgemcbay 16y ago>> 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).
- wlievens 16y agoI 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".
- aphyr 16y agoI 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".
- hugh3 16y ago"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?
- a1k0n 16y agoDisplacement of the zoo environment's pool. That gives you the elephant's volume. What's the density of an elephant?