News for hackers. Stuff that matters.
Re:Oxford Undergrad CS Admission Interview Problems by JoachimSchipper on Friday January 14, 2011 @09:25AM (#2103540)
I don't really see what you mean ("3 segments" suggests asking for f(1/3) and f(2/3) to me, but that's not enough data to know anything). I'll type what I thought, which may be the same thing.

If a < b < c, f(a) <= f(b) and f(b) >= f(c) then a <= m <= c; choosing e.g. 1/4, 1/2 and 3/4 [EDIT: was 1/3, 1/2, 2/3, which is not optimal - see reply by jacobolus] allows you to find out in which 1/2 [EDIT: was 1/3] of the range you should look with three measurements.

You could recurse on the above, e.g. by measuring 1/4 + 1/8 and 1/4 + 3/8 if 1/4 <= m <= 3/4 [EDIT: match above corrections.]

Another interesting trick is measuring 1/2 + epsilon, which (almost) bisects the range with only two measurements. [EDIT^2: removed "(with negligible probability of m being in [1/2, 1/2 + epsilon] - we just hope that doesn't happen, so this doesn't work for adversarial input!). [EDIT: this actually works pretty well for non-adversarial input.]"].

[EDIT^2: I should've paid a bit more attention when writing this, thanks for the (many) corrections jacobolus!]

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