Cambridge Computer Science Interview Questions and Mock Interviews

In a network of servers, every server has exactly three direct links to other servers. No pair of servers is joined by more than one link, and no server is linked to itself. One link is critical: if it fails, the network splits into two parts with no route between them. Show that such a network must have at least 10 servers. Then describe a network with exactly 10 servers that meets all of these conditions.

A display shows a whole number from 0 to 11 and counts like a clock face, so that after 11 it goes round to 0. It starts showing 0. Button X adds 4 to the display and button Y adds 6, going round past 11 when needed. The buttons can be pressed in any order and as often as you like. (a) Which numbers can the display ever show? (b) A second display shows the numbers 0 to 14 (fifteen numbers) and starts at 0, with one button that adds 6 and one that adds 10. Which numbers can this display ever show? (c) Can you state a rule that works for any display size and any two button amounts, and explain why it is correct?

Here is an attempted proof by induction that 2^n is at most n^2 + 1 for every whole number n from 1 upwards. Base case: for n = 1, 2^1 = 2 and 1^2 + 1 = 2, so the claim holds. Step: suppose that 2^k is at most k^2 + 1 for some k. Then 2^(k+1) = 2 times 2^k, which is at most 2k^2 + 2. Now 2k^2 + 2 is at most k^2 + 2k + 2, which equals (k+1)^2 + 1, because k^2 is at most 2k. So the claim holds for k + 1, and by induction it holds for all n. Check the claim for n = 1 to 6. Something has gone wrong: say exactly where the argument fails, and why. Can you then find a similar inequality that you can prove correctly by induction?

In decimal, 0.375 means 3 tenths, 7 hundredths and 5 thousandths. In the same way, the binary fraction 0.011 means 0 halves, 1 quarter and 1 eighth, which makes 3/8. (a) Write 5/16 as a binary fraction. (b) Start to write 1/10 as a binary fraction, and explain why the expansion never ends. (c) Which fractions, written in lowest terms as a whole number over a whole number, have binary expansions that end? (d) Computers keep only a limited number of binary digits for each number. What does this suggest about storing a length of 0.1 metres?

A machine reads a word made of the letters a and b, one letter at a time, starting in state S. The rules are: in state S, reading a moves to P and reading b stays in S; in state P, reading a stays in P and reading b moves to Q; in state Q, reading a moves to P and reading b moves to R; in state R, reading either letter stays in R. The machine accepts a word if it finishes in state R. (a) Which of the words bab, aabb, ababb and abab does it accept? (b) Describe in plain English exactly which words it accepts, and say what each of the states S, P and Q remembers about the letters read so far. (c) Why does reading a in state Q lead to P and not back to S? (d) How would you change the rules so that it accepts exactly the words containing aab?

Seven rooms stand in a row, numbered 1 to 7, and each holds some people. Whenever a room holds 2 or more people, two of them may leave it together, one walking into each neighbouring room. At an end of the row, the person who would have walked beyond room 1 or room 7 leaves the building and is lost. The process continues for as long as some room holds 2 or more people, and you may choose which such room to empty next. At the start, room 4 holds 6 people and the other rooms are empty. (a) Carry out the process and find the final arrangement. (b) Explain why the process must always stop, whatever choices are made. (c) Would a different order of choices ever give a different final arrangement? Explain your answer.

A long corridor has 5 switches in different places, and all of them control one light. A rule says, for each of the 32 ways in which the five switches can be set up or down, whether the light is on. The rule must satisfy this requirement: flipping any single switch, whichever it is and whatever positions the others are in, always changes the light from on to off or from off to on. (a) Describe a rule that meets the requirement, and say what happens to the light if two different switches are flipped one after the other. (b) How many different rules meet the requirement? Justify your answer. (c) Explain why the rule 'the light is on when at least three of the five switches are up' does not meet the requirement.

You mention a program, game or small tool that you have written. What does it take in, what does it produce, and how did you check that it gave the right answers? If I gave it an unusual input, what do you think would happen?

You mention a maths or puzzle problem that you spent a long time on. What did you try that did not work, what made you change your approach, and can you state the general idea behind the eventual solution without using the specific numbers?

You mention an algorithm or technique that you have read about, such as a way of searching, sorting or finding routes. Explain what problem it solves and roughly how the work it does grows as the input gets larger. Then describe an input on which it would do far more work than usual, and say whether a different method would suit that case better.

A password is exactly 8 characters long and each character is a lowercase letter. A program can test a million passwords every second. Roughly how long would it take to try every possible password? Then compare two ways of making the password harder to find by trying everything: making it two letters longer, or allowing digits as well as lowercase letters in each of the 8 places. Which helps more, and by roughly what factor?

Ten people are given 1000 exam scripts in a random order and asked to put them into alphabetical order by surname as quickly as they can. They have a large room and plenty of tables. How would you organise the ten people? Roughly how much faster than one person working alone could they finish, and what stops them from being ten times faster?

A test rig has three dials, each set to a digit from 0 to 9. One click turns a single dial to the next digit up or the next digit down, and 9 and 0 count as neighbours, so one click from 9 goes to 0. The rig starts showing 000, and a technician wants to put it through all 1000 possible settings. (a) Why does this need at least 999 clicks? (b) Show how to do it in exactly 999 clicks, so that no setting is repeated. (c) Can the route be a loop, so that one more click after the last new setting brings the rig back to 000 and the whole route takes 1000 clicks? (d) Explain why your method would still work with four dials, or with any number of dials.