6 ms·
Oxford Undergrad CS Admission Interview Problems
- ig1 16y agoAs 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.
- apl 16y agoOne 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.
- ig1 16y agoI 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.
- TheBoff 16y agoSorry, what is your source for this?
- mjac 16y agoAs 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.
- ig1 16y agoGenerally 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.
- mjac 16y agoIn 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): 1st year: http://www.cl.cam.ac.uk/teaching/0809/part1a-cst.html http://www.cl.cam.ac.uk/teaching/0809/part1a-cst.html 2nd year: http://www.cl.cam.ac.uk/teaching/0910/part1b.html http://www.cl.cam.ac.uk/teaching/0910/part1b.html 3rd year: http://www.cl.cam.ac.uk/teaching/1011/part2.html http://www.cl.cam.ac.uk/teaching/1011/part2.html 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.
- ig1 16y agoPerhaps "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.
- arjunnarayan 16y agoAs someone who studied computer science at Cambridge, I can assure you that Cambridge teaches at a very formal and mathematical level.
- sachinag 16y agoCould 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 16y agoOxford 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.
- andrew1 16y agoOnly 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...)
- ig1 16y agoAlso relevant is the pre-interview aptitude test: http://www.comlab.ox.ac.uk/csatox/images/d/d4/Test10.pdf http://www.comlab.ox.ac.uk/csatox/images/d/d4/Test10.pdf
- smcl 16y agoI 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.
- kwoks 16y agoI got into Cambridge without any specific 'accent' or favour. Btwn, i come from a minority group.
- kwoks 16y agoI got into Cambridge without any specific 'accent' or favour. Btwn, i come from a minority group.
- barry-cotter 16y agoEvidence against this hypothesis; Charles went to Oxford, William to St. Andrews.
- arethuza 16y agoWhile 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.
- viraptor 16y agoI 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...
- JoachimSchipper 16y agoI 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!]
- jacobolus 16y agoMeasuring 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
- JoachimSchipper 16y 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.
- djhworld 16y agoI'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 16y agoI think the sentence's grammar is awkward. That pile next to the monkey has both black and white beans in it.
- djhworld 16y agoAh I see, this is what confused me, there's no stipulation as to what beans are sitting next to him in a pile.
- JoachimSchipper 16y agoThe 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 16y agoI 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.
- JoachimSchipper 16y agoThat'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"?
- djhworld 16y agoLooking 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 16y ago> Looking at these questions just makes me feel stupid "Stupid is as stupid does."
- JoeAltmaier 16y agoAll Discrete math, which it turns out is pretty useful for computer programmers
- HilbertSpace 16y agoFor 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.
- HilbertSpace 16y agoFor 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.