News for hackers. Stuff that matters.
Re:Oxford Undergrad CS Admission Interview Problems by viraptor on Friday January 14, 2011 @09:09AM (#2103489)
I really like those questions - they seem very tricky until you think of some way to do it in a smaller subset or try to figure out the solution by doing the actual actions in your head. I think they're very different from the typical hiring interview logic puzzles you'd see in the companies, but I can't really express the difference...

Then again, I can't really figure out (an optimal) solution to the second one... [spoiler alert] Since you cannot know more about the function than the value itself, is there a better option than dividing the range into 3 equal segments, choosing the one with maximum and recursing? That would give 1/3^5 accuracy. On some values generated in a natural way, you could introduce bias to the segment-selection based on the values you get - but then you could prepare some data which would actually lower the accuracy that way...

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

Re:Oxford Undergrad CS Admission Interview Problems by jacobolus on Friday January 14, 2011 @09:34AM (#2103569)
Question #2 also doesn’t clearly state whether we learn the value of each guess before making the next guess.

As for your idea, 1/3^5 accuracy is not correct. You need to think a bit more carefully about what you can actually learn from testing a pair of points.

Re:Oxford Undergrad CS Admission Interview Problems by viraptor on Friday January 14, 2011 @09:45AM (#2103614)
Ah - thanks for catching that stupid mistake :) Writing to fast and confused myself - I was thinking about ½, ½+epsilon - which is 3 segments, but not equal of course - and it went downhill from there. But yeah - I basically wanted f' at some point. More or less ½^5 accuracy.

Nice observation about learning the value before making another choice too.