One day it is hoped that enough mathematicians will have worked on the problem to have finally, definitively answered Steve Ballmer’s interview question. The job will be shared between them.
With these types of trick questions, it is always interesting what is an acceptable trick and what is not. The question did not specify whole numbers as it does not specify a random selection, but one is in bounds and the other not.
Can't this be solved to some sort of DP way of solving the sub problem?<p>Do the payout between 0 and 1 as the percentage of the amount.<p>With a range of 1 to 1 to pay off is obviously one<p>With a range of 1 to 2 the payout is .5<p>At three values it becomes more interesting. There are two strategies for the candidate either a binary search for the endpoints.<p>At four values you still have one level of binary search possible but after that it devolves down to the two value problem.<p>At five values. If the interviewer thinks the candidate would choose binary search and it becomes too too value problems on each side after removing the middle element.<p>There's definite problems with this but I wonder if he's already possible pay off matrix