Computer Science: Oxford & Cambridge Interview Questions

  • Tell me about binary searches. What about their efficiency? (Oxbridge Applications)
  • Algebraic references with respect to summation formulae and proofs by induction. (Oxbridge Applications)
  • It is a fact that, apart from the peripherals, the whole of a computer can be made from NAND gates. The Egyptians created NAND gates using marbles rolling down shutes and used the them for booby trapping pyramids. Did, then, the Egyptians invent the computer? If not, explain fundamentally why not. (Oxbridge Applications)
  • The game of chess will be played perfectly by the computers of 2010. What is the meaning of this statement and is it likely to be true? (Oxbridge Applications)
  • Why is the pole vaulting world record about 6.5m, and why can’t it be broken? (Oxford Interview Questions)
  • How would you ensure security between two people, A and B? (Oxford Interview Questions)
  • What happens when light has to pass through a medium denser than air? (Oxford Interview Questions)
  • What is the one fundamental difference between a spreadsheet and a database? Surely both hold information, so perhaps there is no fundamental difference? (Oxford Interview Questions)
  • Why is the number 2.7182818… used in mathematics? (Oxford Interview Questions)
  • Explain the principle of the global positioning system (GPS). What factors contribute to its accuracy? (Oxford Interview Questions)
  • How do pirates divide their treasure? A group of 7 pirates has 100 gold coins. They have to decide amongst themselves how to divide the treasure, but must abide by pirate rules: 1) The most senior pirate proposes the division. 2) All of the pirates (including the most senior) vote on the decision. if half or more vote for the division, it stands. If less than half vote for it, they throw the most senior pirate overboard and start again. 3) The pirates are perfectly logical, and entirely ruthless (only caring about maximizing their own share of the gold). so what division should the most senior pirate suggest to the other six? (Oxford University website)
  • Tidy boxes.  You are given 10 boxes, each large enough to contain exactly 10 wooden building blocks, and a total of 100 blocks in 10 different colours. There may not be the same number in each colour, so you may not be able to pack the blocks into the boxes in such a way that each box contains only one colour of block. Show that it is possible to do it so that each box contains at most two different colours. (Oxford University website)
  • Searching for the maximum.  The real-valued function f(x), defined for 0 ≤ x ≤ 1, has a single maximum atx = m. If 0 ≤ u < v ≤ m then f(u) < f(v), and if m ≤ u < v ≤ 1 then f(u) > f(v). You are told nothing else about f, but you may ask for the value of f(x) for any values of x you choose. How would you find the approximate value of m?  How accurately could you find m if you could choose only 10 values of x for which to evaluate f(x)? (Oxford University website)
  • Death by chocolate.  You are locked in a room with your worst enemy. On a table in the centre of the room is a bar of chocolate, divided into squares in the usual way. One square of the chocolate is painted with a bright green paint that contains a deadly nerve poison. You and your enemy take it in turns to break off one or more squares from the remaining chocolate (along a straight line) and eat them. Whoever is left with the green square must eat it and die in agony. You may look at the bar of chocolate and then decide whether to go first or second. Describe your strategy. (Oxford University website)
  • Monkey beans.  An urn contains 23 white beans and 34 black beans. A monkey takes out two beans; if they are the same, he puts a black bean into the urn, and if they are different, he puts in a white bean from a large heap he has next to him. The monkey repeats this procedure until there is only one bean left. What colour is it? (Oxford University website)
  • Lily-pad lunacy. Eleven lily pads are numbered from 0 to 10. A frog starts on pad 0 and wants to get to pad 10. At each jump, the frog can move forward by one or two pads, so there are many ways it can get to pad 10. For example, it can make 10 jumps of one pad, 1111111111, or five jumps of two pads, 22222, or go 221212 or 221122, and so on. We'll call each of these ways different, even if the frog takes the same jumps in a different order. How many different ways are there of getting from 0 to 10? (Oxford University website)
  • Missing numbers.  Imagine you are given a list of slightly less than 1,000,000 numbers, all different, and each between 0 and 999,999 inclusive. How could you find (in a reasonable time) a number between 0 and 999,999 that is not on the list? (Oxford University website)
  • Scribble.  The game of Scribble is played with an inexhaustible supply of tiles, and consists of forming 'words' according to certain rules. Since each tile bears one of the letters PQ, or R, these are not words that will be found in an ordinary dictionary. The game begins with the word PQ on the board; each move consists of applying one of the following rules:
    • If the word on the board is Px, for some shorter word x, you may change it to Pxx. For example, if the word is PQRRQ then you may change it to PQRRQQRRQ.
    • If the word on the board is xQQQy, for some shorter words x and y, then you may change it to xRy, replacing the sequence QQQ with a single R.
    • If the word on the board is xRRy, for some shorter words x and y, then you may change it toxy, deleting the sequence RR entirely.

    (i) For each of the following words, say whether you can make it or not by following the rules of the game:QPRPQQPQRPR. (ii) Given any word, how can you decide whether it can be made or not? (Oxford University website)