Re:Oxford Undergrad CS Admission Interview Problems
by jacobolus on Friday January 14, 2011 @09:37AM
(#2103578)
Measuring 1/3, 1/2, and 2/3 does not tell you which 1/3 of the range you should look. There are 3 cases to consider:
1. f(1/3) is the biggest. In this case you learn that m is between 0 and 1/2.
2. f(1/2) is the biggest. In this case you learn that m is between 1/3 and 2/3.
3. f(2/3) is biggest. You learn that m is between 1/2 and 1.
* * *
Edit: as for measuring 1/2 + epsilon, it’s no worse for “adversarial input”. You just need to remember that your first pair of measurements tell you that either 0 ≤ m ≤ .5+ε or else .5 ≤ m ≤ 1
1. f(1/3) is the biggest. In this case you learn that m is between 0 and 1/2.
2. f(1/2) is the biggest. In this case you learn that m is between 1/3 and 2/3.
3. f(2/3) is biggest. You learn that m is between 1/2 and 1.
* * *
Edit: as for measuring 1/2 + epsilon, it’s no worse for “adversarial input”. You just need to remember that your first pair of measurements tell you that either 0 ≤ m ≤ .5+ε or else .5 ≤ m ≤ 1