Oxford Undergrad CS Admission Interview Problems

Post by HilbertSpace » Sun, Jan 16, 2011, 10:24 PM UTC

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.

Post by HilbertSpace » Mon, Jan 17, 2011, 6:22 AM UTC

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.

Re: Oxford Undergrad CS Admission Interview Problems

Re: Oxford Undergrad CS Admission Interview Problems