News for hackers. Stuff that matters.
Re:The most ridiculous job interview questions by aphyr on Tuesday April 05, 2011 @07:29PM (#2413235)
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.

Re:The most ridiculous job interview questions by georgemcbay on Tuesday April 05, 2011 @08:37PM (#2413432)
>> 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).

Re:The most ridiculous job interview questions by wlievens on Wednesday April 06, 2011 @06:30AM (#2414551)
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".

Re:The most ridiculous job interview questions by aphyr on Wednesday April 06, 2011 @01:24PM (#2415979)
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".
Re:The most ridiculous job interview questions by drbaskin on Tuesday April 05, 2011 @08:28PM (#2413408)
"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.

Re:The most ridiculous job interview questions by JoeAltmaier on Wednesday April 06, 2011 @10:20AM (#2415149)
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.
Re:The most ridiculous job interview questions by drbaskin on Wednesday April 06, 2011 @10:47AM (#2415257)
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.
Re:The most ridiculous job interview questions by aphyr on Wednesday April 06, 2011 @01:26PM (#2415989)
Ah, yes, that is much nicer! Yeah, I did make an off-by-one error as well. Eh, constants. ;-)
Re:The most ridiculous job interview questions by jtdowney on Wednesday April 06, 2011 @05:37AM (#2414479)
Who said that the game they are playing has two participants with a winner and a loser.
Re:The most ridiculous job interview questions by drbaskin on Wednesday April 06, 2011 @10:12AM (#2415118)
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!
Re:The most ridiculous job interview questions by bartonfink on Tuesday April 05, 2011 @07:38PM (#2413261)
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.
Re:The most ridiculous job interview questions by hugh3 on Tuesday April 05, 2011 @07:57PM (#2413320)
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.

Re:The most ridiculous job interview questions by orijing on Tuesday April 05, 2011 @09:48PM (#2413580)
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!

Re:The most ridiculous job interview questions by Fargren on Tuesday April 05, 2011 @08:20PM (#2413378)
I don't think you are being a smartass, I believe that's the only correct answer.
Re:The most ridiculous job interview questions by dvdhsu on Tuesday April 05, 2011 @09:02PM (#2413481)
That's also the first thing that came into my mind. It seems to me like a completely legitimate answer.
Re:The most ridiculous job interview questions by JoeAltmaier on Wednesday April 06, 2011 @10:21AM (#2415158)
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.

Re:The most ridiculous job interview questions by mturmon on Tuesday April 05, 2011 @08:19PM (#2413377)
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".

Re:The most ridiculous job interview questions by hugh3 on Tuesday April 05, 2011 @08:58PM (#2413470)
"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?

Re:The most ridiculous job interview questions by wlievens on Wednesday April 06, 2011 @06:31AM (#2414554)
And balloons are rarely perefect spheres.
Re:The most ridiculous job interview questions by aphyr on Wednesday April 06, 2011 @01:30PM (#2416010)
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. :)
Re:The most ridiculous job interview questions by a1k0n on Wednesday April 06, 2011 @03:06PM (#2416466)
Displacement of the zoo environment's pool.

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