Oxford Undergrad CS Admission Interview Problems

http://www.comlab.ox.ac.uk/admissions/ugrad/Sample_interview_problems

by sjp602 • 16 years ago

30 48 16 years ago

comlab.ox.ac.uk

ig19• 16 years ago

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.

apl2• 16 years ago

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.

Interesting questions, though.

ig19• 16 years ago

I should hope that's true of interviews everywhere.

It's worth noting as well that Oxford is by far the most theoretical of all the CS departments in the UK.

sachinag2• 16 years ago

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.

ximeng• 16 years ago

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.

andrew14• 16 years ago

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...)

sachinag2• 16 years ago

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?

ig19• 16 years ago

Also relevant is the pre-interview aptitude test:

http://www.comlab.ox.ac.uk/csatox/images/d/d4/Test10.pdf

smcl• 16 years ago

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.

barry-cotter• 16 years ago

Evidence against this hypothesis; Charles went to Oxford, William to St. Andrews.

sabatier• 16 years ago

Charles did not go to Oxford. In fact, I'm pretty sure none of the current British royal family attended Oxford.

arethuza• 16 years ago

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.

andrew14• 16 years ago

Have you done any research on this?

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.

ig19• 16 years ago

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.

If you want to understand the real issues in social mobility I suggest reading the Milburn report which I think is one of the best reports I've ever seen a government produce: http://www.bis.gov.uk/assets/biscore/corporate/migratedd/pub...

JoeAltmaier2• 16 years ago

I didn't see that claim supported by that report. Did I miss it?

regularfry• 16 years ago

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.

apl2• 16 years ago

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.

arctangent• 16 years ago

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.

viraptor2• 16 years ago

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...

JoachimSchipper4• 16 years ago

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!]

jacobolus2• 16 years ago

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

jacobolus2• 16 years ago

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.

viraptor2• 16 years ago

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.

JoachimSchipper4• 16 years ago

[SPOILER for 4 - "Monkey beans"]

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.

djhworld3• 16 years ago

I'm confused at the first hurdle

What if the money picks out 2 white beans at the start?

"If they are the same he puts a black bean back in the urn"

jws• 16 years ago

I think the sentence's grammar is awkward. That pile next to the monkey has both black and white beans in it.

JoachimSchipper4• 16 years ago

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.

hasha• 16 years ago

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.

JoachimSchipper4• 16 years ago

That's the right answer, yes (you can even skip "Hence, when there...the other black"); but what do you mean by "I don't think so"?

djhworld3• 16 years ago

Looking at these questions just makes me feel stupid. ...and that kids is why I never went to Oxford.

Glad they're keeping standards high in those places mind.

davidcollantes• 16 years ago

> Looking at these questions just makes me feel stupid

"Stupid is as stupid does."

JoeAltmaier2• 16 years ago

All Discrete math, which it turns out is pretty useful for computer programmers

HilbertSpace2• 16 years ago

For the first problem, "1. Tidy boxes":

(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.

HilbertSpace2• 16 years ago

For the problem 4. Monkey Beans:

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.

Oxford Undergrad CS Admission Interview Problems

Related Stories