Three Example Oxbridge Computer Science Interviews » STEPMaths

Below are three example Oxbridge Computer Science interview questions, worked through by a model student. If you want to practise answering interview style questions, you could always answer the question as best you can first, then work through the script following and trying to do each step before you reach the student’s response. Remember, with interview questions, you are not expected to be able to do them all right at the beginning. The interviewer wants to be able to talk to you about the question and work it through with you.

Question 1 [Iterations]

Question: The “iterated logarithm”, *, is defined as the number of times one needs to apply the base-two logarithm to a number before it is less than or equal to 1. Find a recursive formula for * and use this to find the iterated logarithm of 8.

Many Computer Science interviews focus on mathematical questions, rather than anything explicitly linked to programming or technology.

Interviewer: So are you familiar with the definition of recursive?

Don’t panic if you’re not! The interviewer can explain any terms you’re not familiar with and they’re testing what you can learn, not what you already know.

Student: Yes, it’s when something is defined in terms of itself.

Interviewer: Okay, so let’s find a recursive formula for *.

Student: So recursive formulae have base cases. And in this case we stop applying when the number is less than one. So we have *n=1 if n<1.

Interviewer: Is that correct?

Student: [pauses] Oh, should it be 0 instead of 1? [thinks] Yes, it should be, because you don’t need to apply any times once the number is less than 1… or equal to 1. So it should be *n=0 if n ≤ 1.

Interviewer: Okay, and otherwise?

Student: So that’s the recursive case. If we have a number bigger than 1, then we apply the logarithm. And then we want to find the iterated logarithm of that number. So we have *(n)… And then… [pauses] I’m not sure.

Interviewer: So if I gave you the value of *(n), call it k, what is the value of *n?

Student: So applied k times to n is less than or equal to 1… and then applied k+1 times to n is less than or equal to 1. So it’s *n=*(n)+1. And that applies for n>1.

Interviewer: Okay, good. So then what is the iterated logarithm of 8, using this formula?

Student: So if we start with 8 and take the logarithm… and we’re using base 2… then 23=8 so we get 3. Applying the logarithm again… [pauses] we’re looking for a number where 2x=3. But this isn’t going to be a whole number. [pauses]

Interviewer: Right. Can we work out an upper bound and a lower bound for x?

If you’re stuck, the interviewer will give you hints.

Student: [pauses to think] 21=2 and 22=4 so it should be between 1 and 2.

Interviewer: Yep. What’s the next step?

Student: So if we take the logarithm of 1 we get 0, which is less than 1.

Interviewer: Does the number need to be less than 1?

Student: [looks at formula again] Oh no, actually it can be equal to 1, so we just stop there.

Interviewer: And that means the iterated logarithm of 1 is?

Student: Zero?

Interviewer: That’s right. And the iterated logarithm of 2?

Student: 22=1and then we stop at 1, so it’s 1?

Interviewer: Yes. So what about the iterated logarithm of 8?

Student: So we do it once to get 3 and then a second time to get a number between 1 and 2 and a third time to get a number between 0 and 1 so it’s between 2 and 3.

Interviewer: Can the iterated logarithm be a non-integer?

Student: Oh, it’s the number of times you apply the logarithm so it has to be a whole number. So with 8 we either did it 2 or 3 times.

Interviewer: Which one, 2 or 3?

Student: Well it depends if it’s 1 or 2 after we’ve done it twice.

Interviewer: Can it be exactly 1 or 2?

Student: [thinks for a minute] No, because it’s bigger than 2 and less than 4.

Interviewer: Yes, so we know that our x satisfying 2x=3 is more than 1 and less than 2.

Student: So we do have to apply the iterated logarithm a third time, so it’s 3.

Interviewer: Yes. Now I’d like you to find all numbers which have an iterated logarithm of 3.

Interviewers will often ask questions which generalise facts you have just worked out.

Student: Okay. So those are the numbers that have n ≤ 1. So if we raise each side to the power of two we get n ≤ 2 and then n ≤ 4 and then n ≤ 16.

Interviewer: Is every number less than or equal to 16 suitable?

Student: No, because some of them might have an iterated logarithm of 0, 1 or 2. So we also need n>1. And that’s the same as n>2 or n>4. So then n has an iterated logarithm of exactly 3 if it’s in the range 4<n≤ 16.

Interviewer: Okay, thank you.

Further Hints:

The interviewer might prompt students who are stuck initially to give an example of a recursive formula, and then they can establish what properties recursive formulae have (they consist of base cases and recursive cases). If the student is stuck on how to find all numbers with iterated logarithm 3, the interviewer might help them use the formula they have derived to come up with an equation.

Extending the Question:

When the student takes the equation n ≤ 1 and raises each side to the power of two to get n ≤ 2, this only works because 2x is an “increasing function”. This means that if x>y then 2x>2y. Not every function is increasing e.g. -x or x, so you cannot apply any function you like to both sides of an inequality. The interviewer could ask follow-up questions about this if it comes up in the discussion; for instance, if the student asks if they are allowed to raise each side of an inequality to the power of two.

In fact, * itself is an increasing function. This lends itself to another way of deriving the range in which numbers have an iterated logarithm of 3: find the smallest numbers with iterated logarithms 3 and 4, and then any number with iterated logarithm 3 is between these values. Calculation shows that 22=4 and 222=16 are these bounds, so we get the interval 4<n ≤ 16 as before.

If there is time, the interviewer could ask a follow-up question: for a positive number k, find all numbers n such that *n=k. The solution (which the interviewer will help the student to construct) is to consider a “power tower” of k lots of 2s stacked on top of each other e.g. for k=4, we have 2222=216 (=65536) is the upper bound. Write this number as Power-Tower(2,k). The numbers n which have iterated logarithm k are the ones satisfying Power-Tower(2,k-1) < n ≤ Power-Tower(2,k).

What the Question is Testing:

The question tests the ability to learn a new concept and apply it to your existing knowledge of logarithms. It tests your understanding of recursion and your ability to derive formulae.

Related Topics from University:

Recursion is one of the most common techniques for writing algorithms, and occurs widely throughout computer science as well as mathematics.

The iterated logarithm is used in computer science as a measure of “complexity” of some algorithms – that is, how quickly they run. If you have come across “Big-O notation”, the iterated logarithm (written *) is interesting as it is a function which grows very, very slowly – much slower than any function in O(n) or even O(n).

The additional material relating to “power towers” relates to a function in arithmetic known as “tetration”.

Question 2 [Graph Drawing/Ordering Numbers]

Question: Put the following functions in increasing order in terms of how fast they grow as n tends to infinity: 100n3, n4, n, (n)n, n, nn.

Student: When the question says “log”, does it mean “base 10 log”?

Interviewer: In fact it doesn’t matter, but let’s say it’s the common logarithm. That is, the base 10 logarithm.

Student: Okay. [pause] I’ll start by sketching some of these equations.

Interviewer: Good.

Student: So here’s y=n3. And then here’s y=100n3. And y=n4.

Graphs don’t need to have scales and they can be rough sketches. Remember, however, to always label axes though, as this is important.

So as for which one is bigger… we’re looking at the right hand side of the graph and it looks like 100n3 is the one on the inside so it’s the one that’s growing fastest.

Interviewer: Okay.

Student: No, actually shouldn’t n4 grow faster?

It’s okay to change your answer or to be unsure. It’s best to say your thoughts out loud rather than just sitting in silence, so the interviewer can see how you’re thinking.

Interviewer: Why would that be?

Student: Because 4 is a higher power than 3. [pauses] Okay so maybe n4 overtakes 100n3 higher up.

Interviewer: How can you tell if that happens?

Student: Well if we solve 100n3=n4 then we can see where they intersect. And we get n3(n-100)=0 so they intersect at 0 and 100. [pauses] So the graph of n4 overtakes 100n3 past 100.

Interviewer: Okay, so which is growing slower?

Student: 100n3.

Interviewer: How about the other functions?

Student: So n is going to grow very slow and n will grow even slower.

Interviewer: Why is that?

Student: Well if I draw n…

It’s growing a lot slower than 100n3or n4. And then if we take the logarithm of that then it gets even smaller… [pauses] because y=n grows slower than y=n so if we set n=n then we get that n is slower than n.

Interviewer: Okay. How about the remaining functions?

Student: So by the same reasoning (n)n has to grow slower than nn. And if we compare (n)n to n4… well firstly we have that n4 grows slower than nn because n will be bigger than 4 as n gets bigger and bigger. If we solve (n)n=n4 then we get 10(n)n=10(n)2=10n4.

Interviewer: How about instead, we try to take the logarithm of the equation (n)n=n4?

The interviewer may give you advice if you go down a track which won’t lead you to the answer.

Student: So ((n)n)=(n)(n) and (n4)=4(n).

That means (n)n>n4 if (n)(n)>4(n) which is true if n>4, which is true for n>10104. So (n)n grows faster.

Interviewer: Okay, thank you.

Note: final order (slowest to fastest) is: n, n, 100n3, n4, (n)n, nn.

Alternative Methods:

Lots of comparisons can be done without the use of graphs. For instance, to compare 100n3 and n4, note that we’re comparing 100n3 with nn3. So, the second function will be bigger if n>100. And as n approaches infinity, it is certainly greater than 100, so the second function grows faster.

One way to make functions easier to compare is to take logarithms or powers of both sides. The model student does this in the final moments of the interview. This works because x and 10x are “increasing functions”: if x>y then x >y and 10x>10y.

For example, in comparing (n)n and 100n3, we can take logs to get (n)n=nn and (100n3)=2+3n. We can discount the 2 as it is a constant and we see that as n becomes very large, n>3 so nn>n3. Thus (n)n grows faster than 100n3.

Extending the Question:

The interviewer could introduce more functions such as (n)n, 2n, 3nor (n)(n)n.

What the Question is Testing:

The question requires a thorough understanding of logarithms and exponentials, and of graph sketching. It tests the ability of a student to find ways to approach new ideas and new problems.

Question 3 [Understanding a machine]

At the beginning of the interview, the interviewer hands the candidate the question on a piece of paper and asks them to read the material.

Question: A deterministic finite automaton (DFA) is a machine which is in one of a finite number of states. It starts in an initial state and changes state according to the input it receives. Some states are accepting; if the machine is in an accepting state when the input terminates, then it “accepts” the input. Otherwise it “rejects” the input.

The automaton represented by this diagram accepts a string of 1s. The arrow going into the state 0 indicates that 0 is the start state. The double circle around the state 2 indicates that it is an accepting state. Each arrow labelled with a 1 indicates which state the machine moves to after receiving a 1 as input.

For instance, with the input 111, the machine moves from state 0 to 1 to 2 to 3+ and as 3+ is not an accepting state, this machine rejects 111. What strings does this machine accept?

Let 1n be the string consisting of n repetitions of the character 1. Explain how to construct a DFA which accepts only the string 1n. How can this be extended to make a DFA that accepts a finite set of strings, 1a, 1b, …, 1z?

Student: Okay, so it looks like the only thing this machine accepts is the input 11.

Interviewer: Right, and how can we show that?

Student: So if we put in 11 then the machine goes from state 0 to 1 to 2 and 2 is an accepting state so the machine accepts 11.

Interviewer: Okay. And if we input something else?

Student: Well if we put in 3 or more 1s then the machine goes to state 3+ and stays there forever. And 3+ isn’t an accepting state so it will reject the input. And if we put in just the input 1 then it goes to state 1 which isn’t accepting.

Interviewer: Okay. We can also input the empty string.

Student: So, 0 1s? Then the machine stays where it started, in state 0. And 0 isn’t an accepting state.

Interviewer: Okay, good. Now I’d like you to read question 2.

Student: [after reading the question] So the machine they’ve given us solves this problem when n is 2. And we can do the same method for any n.

Interviewer: Yes. And then if we want to change this to accept the strings 1a, 1b, …, 1z?

Student: So we change the accepting state from n to the numbers a, b, …, z.

Interviewer: Okay. And what is n in this case?

Student: We could just get rid of n and have one state from each number 0, 1, 2, ….

Interviewer: Then the machine is not finite.

Student: Oh, okay. Then we can just go up to the largest number out of a, b, …, z.

Interviewer: Yes, good. Next I’d like you to make a DFA which accepts strings of the form 1n where n is a multiple of 2.

Student: Right. So we can’t just have this chain and make 10, 12, 14, … accepting because that wouldn’t be finite.

Interviewer: No.

Student: So…. [thinks] We only need to know two things, whether there have been an even or an odd number of 1s input. So we can have a state for even and a state for odd. It would look something like this:

Interviewer: Yes. And if instead of multiples of 2, we looked at multiples of n?

Student: Then we need n states. So would this work?

Interviewer: Yes, though it might have been better to label the states 0, 1, …, n-1. Right, now I’d like you to think about DFAs which take as input not just a sequence of 1s but a sequence of digits 0, …, 9. So the number 981 would be represented by inputting a 9 and then an 8 and then a 1. Our diagram can have one arrow per input digit per state. And I’d like you to make a DFA which accepts decimal numbers that are a multiple of 2.

Student: Okay. So again, we just need to know whether the input is even or odd. And we can keep track of that by seeing whether the last digit is 0,2,4,6,8 or 1,3,5,7,9. The DFA would look like this:

An arrow with “1,3,5,7,9” is shorthand for five arrows with 1, 3, 5, 7 and 9 as labels.

Interviewer: Good. Now how could we write a DFA to tell if a number is a multiple of 3?

Student: So we can’t do this just by looking at the last digit, because multiples of 3 can end in any digit. There’s a test to see if a number is divisible by 3 by adding all of its digits together.

Interviewer: And how do you tell if the number is divisible by 3 with that test?

Student: So the number is divisible by 3 if you add all its digits together and get a multiple of 3. Or if that number is still too big to work out if it’s divisible by 3, you can keep adding its digits together until you get down to a single digit number.

Interviewer: Okay. So how can we use this idea to construct a DFA?

Student: Well, we can just keep a running track of the sum of the digits. But we can’t store the number because we don’t know how big it will be.

Interviewer: Okay. Do we need the whole number? [silence] Or just a property of it?

Student: Oh, we just need to know whether it’s a multiple of 3 or not. Or whether it’s 1 more or 2 more than a multiple of 3. So it would look like this.

The interviewer would not make the student add all of the labels, just enough to explain how the DFA works.

Interviewer: Okay, thank you.

Further Hints:

The interviewer would prompt the candidate to correct any small mistakes like forgetting to draw an arrow for the initial state, or a double circle for accepting states.

If the candidate was stuck on the last part, the interviewer might prompt them to think of any divisibility tests for three that they knew, and if they didn’t know any then the interviewer would explain one to them.

Extending the Question:

As well as multiples of 2 and 3, we can make a DFA to test divisibility by any number for which we have a divisibility rule involving the digits they end in, or some type of digit sum.

For instance, a number is divisible by 8 if its last three digits are divisible by 8. So we can have one state for each of the last three digits, from 000 to 999, and make all the multiples of 8 (000, 008, …, 992) accepting states. However, this does require a DFA which has 1000 states. (Can you think of a DFA which does the same thing with fewer states?)

A number is divisible by 11 if its alternating digit sum is a multiple of 11 e.g. 83929032 is a multiple of 11 because 8-3+9-2+9-0+3-2=22 is a multiple of 11. How can we make a DFA for multiples of 11 using this rule?

Additionally, given two DFAs M1 and M2 which accept multiples of m and n, we can make a DFA M3 which accepts multiples of mn. Can you work out how? (Hint: if we enter a number and this causes M1 to move to state x and M2 to move to state y, then we want M3 to be in a state (x,y).)

What the Question is Testing:

Some candidates may already be familiar with deterministic finite automata, perhaps under the name “finite state machines”, but the interviewer is testing how well the candidate can learn new information. Hence, if a candidate already knows some of the background material then they will be pushed further into the extension material, to a point where they are asked a question they have not come across.

The question tests ability to learn new information quickly, and to design abstract machines. Candidates with programming knowledge may have written algorithms to test divisibility of numbers, but with DFAs there is a constraint that only a finite number of states can be used, making things more difficult.

Conclusion

The most important thing with interviews is to stay calm, and think clearly. Don’t be put off if the questions seem impossible to answer at first: that’s a sign that the interviewers are pushing you. For more information, see our guide to how to prepare Oxbridge Computer Science interviews, and what to expect in a Computer Science interview.