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...
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!]
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
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.
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.
Could some kind UKer(s) please explain to this American exactly how Oxford, Cambridge, and the UK university system works? I'm familiar with what A levels are, and that you supposedly apply to a particular college at each of Oxford and Cambridge, but then I hear about university-wide "departments", and I put that in my American-style mental model. Googling hasn't helped me, but perhaps I'm being unimaginative in search terms.
Only some UK universities have a collegiate system (Oxford, Cambridge, Durham, St. Andrews(?)). Most do not (I believe) and I imagine are roughly similar to US universities. At collegiate universities there is a split between what a college is responsible for, and what the university is responsible for. Lectures are university-wide, exams also are (you get your degree from the university not the college), departments belong to the university (so if the Enlgish department needs a new building then the university pays for that). All students (and staff) are affiliated to a college (you choose which college to apply to when you apply to the university, and the college decides whether to admit you). The college is responsible for their students accommodation needs, will usually provide a dining option, common room etc. The college provides teaching (so you go to the same lectures as everyone else, but your small group teaching, feedback on work etc. is organised by the college). I think those are the main distinctions.
Given that the colleges are different, this can mean it's important to choose the right one for you. For example, at Cambridge, Trinity College has an illustrious history in mathematics, and attracts excellent staff, so if you're accepted there then you might end up being taught one-on-two by a world renowned mathematician (Fields Medal winning Timothy Gowers for example). Other colleges with less of a reputation might have more trouble attracting the same type of staff. (this isn't to say that being an expert in your field makes you an excellent teacher of course...)
OK, this really helps; thanks! Let's say that you really wanted to study CS at Oxford; if you pick the wrong college to apply to, are you shut out from the university entirely? Or can you apply to multiple colleges at the same university at once?
If a college thinks you're good at your subject but doesn't want to accept you for other reasons (they have too many candidates, don't think you'd be a good fit) they can "pool" you, which means that other colleges that are interested can interview you.
You can also make an "open application" which is similar to pooling where you say you don't mind which college you get into.
Generally applicants tend to put too much emphasis on the "right" college, the academic differences aren't that great, and a lot of it is just candidates wanting to get into the more prestigious colleges for prestige's sake.
It's different for postgraduates. Undergrads can only apply to one college and to one uni at a time, as @andrew1 mentions. Postgrads can apply to both unis. As for college selection, I had to apply to my department first (ComLab) and then I listed four colleges in order of preference. Once the department accepted my application, it was up to one of the colleges to accept me, though I did get my first choice.
Nope, you can only apply to one college at either Oxford or Cambridge per year (you can't apply to both universities, which probably makes sense as almost everyone who applied to one would probably apply to the other). There is a clearing system I think where if the college you apply to doesn't want you then other colleges can look at your application and choose to interview you, but I think that's fairly rare.
Whilst you're discouraged at all levels from applying to both Ox and Cam, I don't think it's true that you can't. But you're correct about the second interviews (at other colleges). This was actually pretty standard (for Biochem, at Oxford) when I applied and you went for the alternative interview (at a college you're assigned to, you don't get a second choice) before the first has made any sort of decision on you. There is a second safety net, whereby you can be 'pooled' (which is basically what you describe); if you don't have a college preference from the outset, you can apply directly to the pool (again, this is Oxford, not necessarily Cambridge)
Oxford and Cambridge are a bit different from most UK universities. The college system is orthogonal to subject-specific departments. A college provides accommodation, social support. Academic staff are also associated with a college, and teach students from that college in small group tutorials. Lectures however tend to be organised by department rather than by colleges.
As students become more specialised, or if their college doesn't have many professors in their particular subject, they may have tutorials with academics in other colleges.
As a bit of background, you're not required to have any programming knowledge when applying although most candidates will have done D&D Maths which covers topics like graph and bin packing algorithms.
One more thing to keep in mind: Cambridge and Oxford interviews are more about thought process than actual solutions. I've seen candidates with correct answers not get in while peers who never found an adequate solution make it.
As a student at Cambridge, I doubt Oxford is "far" more theoretical. The London Universities like Imperial are also notable for focusing on theory over practice.
I think they assume we can learn practical skills on-the-fly and they are not as beneficial as a solid theoretical grounding.
These Oxford interview questions are more difficult than I expected, especially under Oxbridge interview conditions. Like mentioned above, they want to see how you think over what you already know.
Generally all the top-tier universities are more theoretical than the lower tier universities.
Historically Oxford has been much more focused on the rigorous underpinning of CS by Mathematics than other universities, although in recent years they've been cutting down on this and moving closer to the CS syllabus offered by other top-tier universities.
Here's the course list for first year at Oxford:
• Functional Programming
• Design & Analysis of Algorithms
• Imperative Programming I
• Imperative Programming II
• Digital Systems
• Discrete Mathematics
• Logic and Proof
• Linear Algebra
• Calculus
• Probability
Unless you do CS with Mathematics at Cambridge, you'll probably be doing a much less mathematically intensive course.
In the first year all of us do Computer Science (2 papers), Mathematics (1 paper), and a science subject (1 paper, I did Physics). It is predominantly theoretical (something I found hard to cope with):
Although I think there is far too much content to learn thoroughly in three years, it does provide a broad understanding of what there is to know. Does Oxford have online course material, I'd be interested to take a look? I expect the universities overlap a lot but there might be some worthwhile additions.
Perhaps "theoretical" is the wrong word, what I meant is that Oxford courses tend to take a more formal & mathematical approach to topics than other universities.
I suspect the Oxford\Cambridge undergrad interviews have less to do with assessing technical competency and more to do with providing admissions with a reason to discriminate against state-educated kids. The amount of Oxbridge intake come from private schools is disproportionately high to be due to exam results alone, and is better explained by an ingrained negative view of those with a state education or old boys networks.
I've seen this in action, exceptional state school students turned down from Oxford, and utter buffoons (but with the correct background and accent) being accepted.
There's no statistical evidence showing this is the case. Students from high performing schools are disproportionately likely to apply to Oxbridge, but adjusting for academic performance there's no indication that Oxbridge discriminates.
Pretty much everyone applying to Oxbridge is applying with top grades, plenty of exceptional candidates from both state and private sector schools get rejected.
While I suspect a lot of this probably does have to do with selecting "people like us" I've also had the experience to compare my privately educated son with my own experiences in state education (at a pretty rough school).
What private schools seem particularly good at is instilling a rather outgoing self-confidence that seems pretty uncommon amongst state educated kids. Note that this is effectively orthogonal to actual capabilities - but the end result is that I suspect that a lot of privately educated kids will come across a lot better in these situations than people from state schools.
It's not fair - but to be honest that's why you pay the considerable amounts of money for private education - to give your kids an advantage.
Assume for a moment that the exam results of students follow a bell shaped curve and that the mean and standard deviation of exam results in the state and private sector are the same, then you would expect the proportion of state school pupils accepted by Oxbridge to be the same as the proportion in the general school system. If instead we assume that the mean in the private sector is higher then you would no longer expect the same proportion to be accepted, and indeed that disproportionately many private sector students would get in.
I'm not saying this is the case (although private school students probably do do better in exams on average), but without knowing anything about the situation how can you accuse them of discrimination? The 'oh, I saw a really good person get turned away' argument is silly. Some colleges only offer a few places for some subjects but are presented with 20+ students who all have predicted straight As, good UCAS forms etc. It's inevitable that some good students will not get in, and it doesn't imply discrimination.
I have first hand experience of the Cambridge interview process and was successful despite being a state school candidate.
I read mathematics and my interviews were purely technical. (None of those "hundred uses of a toothbrush" for me - perhaps those were for the arts students ;-) )
In the UK we are in the unfortunate situation whereby school examinations are so easy (as a result of political intervention) that it is effectively impossible to distinguish between the best candidate on examination results alone.
Privately educated students do make up a much larger proportion of the student body than they "should", compared to the overall population. However, it could be (correctly) argued that state school pupils are more reluctant to apply in the first place.
I can confirm that at Cambridge between'97 and '00 there was a concerted effort by the university and the student body to encourage applications from statistically underrepresented sections of society.
All Harvard kids are rich rowers, all Oxbridge students are posh sons and daughters of politicians and aristocrats, and all these state-educated kids were rejected simply because they didn't wear the right clothes, amirite?
Bla.
I do around 50-60 admissions interviews a year, and we don't even know to which schools the applicants went when we question them. What you've seen in action is a few anecdotes and whiny parents who blame external factors for their child's rejection letter.
NB, I'm not saying there isn't a problem. There's still a lot of room for improvement; both universities are doing plenty of outreach work and are fully aware of the situation. But your portrayal of Oxbridge is ridiculous.
That's likely to depend hugely on the subject. I'm privately educated in relevant subjects, and went on to do an engineering degree at a well-regarded university (not Oxbridge, but ranked with them), but there's just no way I had the technical chops at the time to get past these questions. I don't think I'd even read GEB yet.
With a technical subject, it's relatively straightforward to put a meritocratic admissions system in place. I don't think you can make that argument for humanities subjects.
The answer is not probabilistic (that is, the last bean is either white with 100% probability, or black with 100% probability). This took me a while to figure out.
I don't think so. After each drawing the number of whites is congruent modulo 2 to the initial number of whites. Hence, when there are two beans left, one will be white and the other black so the last bean will be white.
The monkey randomly picks two beans from the urn, then puts one (from the pile) back. That is, if the monkey picks two white beans from the urn, he gets a black bean from a pile of beans next to him, and puts that black bean in the urn.
(1) For each color, put all the cubes of that color in their own pile. So, get 10 piles, and in each pile all the cubes have the same color.
(2) Arrange these piles in ascending order from left to right on the number of cubes in each pile. So, a color with the fewest cubes is on the left, and a color with the most cubes is on the right.
(3) If the pile on the left has 10 cubes, then pack each pile in its own box, and we are done.
(4) Else take cubes from the pile on the right and put them on the pile on the left until the pile on the left has 10 cubes.
(5) Go to step (2)
This problem and solution generalize immediately to, for positive integers m and n, n colors, n boxes, and (m)(n) cubes.
Or, if we have n factories where each factory produces cubes of just one color and have n warehouses each of which needs m cubes, and the total number of cubes produced is (m)(n), then it is possible to ship the cubes from the factories to the warehouses so that each warehouse gets cubes of at most two colors. So, there is connection with the 'transportation problem'.
That problem is a special case of least cost capacitated network flows which is a linear programming problem with some special properties. In particular if all the capacities are integers and have an initial flow with all integers, then the simplex algorithm will find a least cost solution with integer flows. So, here is a way to integer linear programming for no extra effort. The general case of integer linear programming is in NP-complete. The simple algorithm on such networks is closely related to spanning trees.
At each move, the number of beans in the urn falls by 1. So, after
23 + 34 - 1 = 56
moves, the number of beans in the urn will be 1.
At each move, the number of white beans in the urn either stays the same or falls by 2. Since the initial number of white beans is 23 and odd, as long as there are any white beans in the urn, the number is odd. Since the number of beans in the urn falls to 1, the number of white beans must fall to 1.
Suppose there is 1 white bean in the urn: If there are no black beans in the urn, then we are done and the last bean is white.
Else we keep playing and observe that at each play the number of white beans in the urn remains 1. That is, there is no way to remove the last white bean from the urn. So, in all cases, the last bean in the urn is white.
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...