牛津剑桥如何面试？

这段时间是英国G5院校发面试offer的高峰期，有同学收到面试通知了吗？收到的同学心情一定很激动吧，离正式offer只差一个面试了！

但G5面试不是走过场。需要精心准备。

到底在面试中，牛剑老师和面试者之间发生了哪些“对话”？牛剑到底想要什么样的学生？为何有人成绩很好，却得不到面试老师的青睐？

在牛津大学的官网上，有一份该校计算机科学专业本科的面试过程实录，虽然比较长，但是值得仔细阅读。感受一下牛剑老师引导学生解题的思路，题目本身不难理解，只要学过数学应该都能看懂。在面试实录的最后，我们总结了牛剑面试的一些关键点。

在这场面试中，牛津的面试老师首先向面试学生提出了下面这道题：

Tidy boxes.
You are given 10 boxes, eachlarge enough to contain exactly 10 wooden building blocks, and a total of 100blocks in 10 different colours. There may not be the same number in eachcolour, so you may not be able to pack the blocks into the boxes in such a waythat each box contains blocks of only one colour. Show that it is possible todo it so that each box contains at most two different colours.

收纳盒问题。
如果你有10个收纳盒，每个盒子能装10块积木，总共有10种颜色的积木100块。由于每种颜色的积木数目不一定相同，因此当你把积木全部装进盒子里时，你可能没法保证每个盒子只装同一种颜色的积木。请证明我们能够找到一种把积木全部装进盒子里的方式，使得每个盒子最多只装两种不同颜色的积木。

随后，面试老师和学生发生了如下对话：
A 代表面试老师
B 代表面试学生

A:  We asked you to think about the problem called tidy boxes. Have you made any progress with it?
A：刚才我们请你思考的这个收纳盒问题，你有什么进展吗？

B:  I haven't got very far: perhaps you could begin by putting each colour in its own box. Some colours would have less than ten bricks, so all of that colour would go in one box. But some colours would have more than ten bricks, and we'd have to find a way to use the extra bricks to fill up the gaps in the other boxes. I can't see a way to dothat.
B：我目前没有特别大的进展：也许你可以先把每种颜色的积木放进每个颜色相对应的盒子里。有些颜色可能有不到10块积木，所以这些颜色中，所有同色的积木都能够放进它们对应的盒子里。但是有些颜色有10个以上的积木，那样我们就得想办法让多出来的那些积木填补到有空位的那些盒子里。我想不出来怎么做。

A:  OK. Let's think about an easier problem to start with: if we had only one box and ten bricks, all of the same colour, could we solve the problem?
A：好。我们先想一个简单点的问题：如果我们只有一个盒子，10块同色积木，我们能解答这道题吗？

B:  Yes, of course: you just put allten bricks in the one box, and it then contains only one colour, so you don't even need the freedom to have two colours in a box.
B：当然可以：你只需要把这十块积木都放进一个盒子里。这个盒子只装一种颜色的积木，我们甚至都不需要把条件放宽到一个盒子装两种颜色。
A:  Good. Now suppose you have two boxes and 20 bricks in two different colours. Could you solve the problem then?
A：很好。现在假设你有两个盒子，2种颜色的积木20块。你能解答这道题吗？

B:  It's still easy: you can just put the 20 bricks into the two boxes any way you like. Then each box might have a mixture of the two colours, but there are still only two of them.
B：依然很简单：你可以把这20块积木随便放进这两个盒子里，这样每个盒子里就可能会混合了两种颜色的积木，但是每个盒子里也只有两个颜色。

A:  So these small versions of the problem are easy. Let's go back to thinking about the original problem, with ten boxes and ten colours of brick. I wonder if, instead of starting to fill all the boxes as you suggested, we could begin by filling just the first box. Can we find a colour with few enough bricks that we can put all of them in the first box?
A：所以这个问题的这几个简易版本很容易证明。那我们现在来思考一下原先的问题：十个盒子，十种颜色的积木。我在想，如果我们先试着装第一个盒子，而不是把所有盒子都装上积木，那么我们能否找到一种颜色，这种颜色的积木数目足够少，使得它们都能够被放进第一个盒子里呢？

B:  You mean a colour with ten bricks or less. We can be sure such a colour exists, because the average number of bricks of each colour is ten. If all colours had more than ten bricks, then they would all be above average, and that can't happen.
B：你是说找一个积木数目少于或者等于10块的颜色。我们可以肯定这种颜色存在，因为每种颜色平均有10块积木。如果所有颜色的积木数目都超过10块，那么每种颜色的积木平均数就会大于10，这是不可能的。

A:  Right. So we choose a colour that's below average (or equal to the average) and we put all of those bricks into the first box. Now there may be a gap to fill, and I'd like to find another colour with enough bricks to fill the gap. Can I be sure of doing that?
A：对。所以我们要选一种颜色，使得这种颜色的积木数目小于（或者等于）每种颜色的积木平均数，然后我们把所有这个颜色的积木都放进第一个盒子里。现在这个盒子里就可能会有空位，然后我想找另外一种颜色，使得这种颜色的积木数目足够填满第一个盒子里的空位。我能确定做到这点吗？

B:  What you could do is to choose a colour with more than the average number of bricks. That colour ought to be enough: the gap to fill must be nine bricks or fewer, and the average is ten.
B：你可以找一个颜色，使得这种颜色的积木数目多于积木平均数。这个颜色的积木肯定满足条件，因为如果想要第一个盒子里的空位，需要九块或更少的积木，而每种颜色的积木的平均数是10块。

A:  Excellent. So we've filled up a box by using all of one colour and some of another colour. Let's suppose we put a lid on that box and push it to one side. What do we have left?
A：非常好。所以我们用了一种颜色的全部积木和另一种颜色的部分积木，装满了一个盒子。假设我们把这个盒子盖上盖子，推到一边，那么现在我们还剩下什么？

B:  There are nine boxes left, andninety bricks of nine different colours.
B：现在剩下9个盒子，以及9种颜色的积木块90个。

A:  So what should our next step be?
A：所以我们的下一步是什么？

B:  We can use the same approach as before, filling a second box by using all of a below-average colour and some of an above-average colour. By carrying on like this, we can eliminate the colours one at a time.
B：我们可以用和刚才相同的方法来装第二个盒子：选一种少于平均数目的颜色，把所有积木装进去，再选一种多于平均数目的颜色，用其中一部分把剩下的空位填满。我们只要重复这一步骤，就可以每步消除一个颜色了。

A:  That's very good. How does the process end?
A：非常好。那么这个过程会怎么结束呢？

B:  When we get down to one box, we will have only one colour left, and that can all be put in the last box, as we said before.
B：当我们只剩下一个盒子时，我们也只剩下一种颜色的积木，然后我们就可以把这些积木全部装进最后一个盒子里了，这就和之前的简易版本问题是一样的。

A:  So we've shown that the problem can always be solved, and you can put the bricks in the boxes with at most two colours in each box. Now I want to think about a slightly harder problem: suppose we have ten boxes but there are 11 different colours of brick. Can we still solve the problem with only two colours in each box?
A：所以我们已经证明了这个题目，我们可以找到方式把所有盒子装满，使得每个盒子里最多有两种颜色。现在我想思考一个再难点的问题：假设我们有10个盒子，11种颜色的积木。我们还能解决这个问题吗？

B:  Well, I suppose we could start the same way as before: find a small colour and put all of it in the first box.
B：嗯，我觉得可以用刚才的方式来试一下：找一种积木数目足够少的颜色，把他们都放进第一个盒子里。

A:  OK: since the average number of each colour is now 100/11 and that's smaller than 10, we can still be sure of finding a colour with 10 bricks or less. But I'm worried about the next part, where we need to find a colour with enough bricks to fill up the gap. Can you work out what will happen?
A：好。既然每种颜色的平均数现在变成100/11，然后这比10小，所以我们肯定能找到一种积木数目小于或等于10的颜色。不过我有点担心下一步，就是我们要找一种颜色的积木，使其足够填满第一个盒子里的空位。你能算一下这一步吗？

B:  The biggest gap we might have is nine, and the average number of each colour is 100/11 = 9 1/11, so we're still all right: at least one colour must have 10 bricks or more, since if they all had nine or less, then they'd all be less than average.
B：第一个盒子里的空位最多能放下九个球，而每种颜色的积木平均数是100/11，也就是9 1/11，所以我们还是可以做到的：至少有一种颜色的积木数目是10或者以上，因为如果所有积木的数目都小于或等于9，那所有颜色的积木数目就都小于平均值了。

A:  So that still works: we can fill up the first box with all of one colour and some of another, then put it to oneside. How does the process continue?
A：所以这还是可以做到的：我们可以用一种颜色的全部积木和另一种颜色的部分积木，装满第一个盒子。假设我们把这个盒子盖上盖子，推到一边，那么现在我们要怎么做？

B:  We carry on filling boxes and eliminating one colour at a time, until we get down to one box and two colours. And we can fill the last box with the two colours that are left to finish offthe problem.
B：我们继续把每个盒子都填满，一次消除一种颜色，直到我们只剩下最后一个盒子和最后两种颜色的积木。然后我们把这两种颜色的积木都装进最后这个盒子里就可以了。

A:  I see. I'm still a bit worried about finding a colour with enough to fill up the gap. Say we had three boxes and four colours: then the average of each colour would be 7½, wouldn't it?  And we couldn't be sure that any colour had as many as nine bricks.
A：我懂了。但我还是在担心我们能不能找到一个颜色，其积木数目足够填满盒子里的空位。假设我们有3个盒子，4种颜色的积木，那么每种颜色的积木平均数就变成7½,对不对？那我们就不能确定有没有哪种颜色可以有9个积木那么多了。

B:  Yes, that is a problem.
B：是，这确实是个问题。

A:  Let's see if we can use a bit of algebra to analyse the situation. Let's suppose we have n boxes and n+1 colours left, and say we find a colour that has x bricks, with x ≤ 10 so that that colour all fits in the next box. Whatis the gap that we have to fill?
A：我们来看看我们能不能用一点代数来分析一下这个情况，假设我们现在剩下n个盒子，n+1种颜色的积木，然后假如说我们找一种颜色，这种颜色有x块积木，而x ≤ 10 ，这样这种颜色的所有积木都能放进下一个盒子里。我们需要几块积木来填补下一个盒子的空位呢？

B:  That's obvious: it's 10 - x.
B：显而易见，需要（10 – x）块。

A:  Right. And how many bricks do we have left, after putting the x bricks in the next box?
A：对。那么当我们把x块积木放进下一个盒子里后，还剩下多少块积木了呢？

B:  Well, we had 10n bricks altogether, so now we have 10n - x.
B：嗯，我们原本一共有10n块积木，所以现在我们有（10n– x）块。

A:  So what is the average number of bricks of each colour that we have left?
A：所以现在我们手上每种颜色的积木平均数是多少？

B:  It's going to be(10n - x)/n, which is equal to 10 - x/n.
B：是(10n - x)/n，也就是（10- x/n）块。

A:  Is that smaller or larger than 10- x?
A：这个数比10 – x大还是小呢？

B:  [Thinks for a moment] Provided n ≥ 1, we have that x/n ≤ x, so 10- x/n ≥ 10 - x.
B：（想了一会）因为n ≥ 1，那么x/n ≤ x，所以 10- x/n ≥ 10 – x。

A:  So what does that mean?
A：这意味着什么呢？

B:  It means we can find a colour with enough bricks to fill the gap, because the average number of each colour remaining is at least as large as the gap.
B：这意味着我们能找到一种颜色，使其有足够数目的积木块填满空位，因为剩下每种颜色的积木数都至少刚好够填满盒子里的空位。

A:  Excellent: so we can solve the problem with ten colours, and we can still solve it with eleven colours. Whatdo you think I want to ask you next?
A：非常好。所以当我们有10种颜色时，这个问题可以有解，当我们有11种颜色的时候也可以有解。那么你觉得我接下来要问你什么问题？

B:  Can we do it with twelve colours?
B：当我们有12种颜色的时候，这个问题有解吗？

A:  Well?
A：你怎么想？

B:  We could begin in the same way asbefore, eliminating colours one at a time. I'm not sure if the calculation wedid would still show that we can fill the gap, though.
B：我们可以跟刚才采取同样的方法，一次消除一种颜色。不过我不太确定刚才的计算能够证明我们可以填满盒子里的空位。

A:  Even if we could always fill the gap, what would we be left with when we got down to one box?
A：即使我们每次都能够填满盒子里的空位，当我们只剩下最后一个盒子时，会出现什么问题？

B:  Well, you'd have eliminated nine of the colours, one at a time, so you'd be left with one box and three colours. Oh, I see, you can't do it, because you're going to have three colours left at the end, and you can't put them all into the last box. So it can't be done.
B：嗯，那样的话你就已经消除了九种颜色，一次一个。所以你就会剩下一个盒子和3种颜色的积木。哦，我明白了，这样做不行，因为你最后剩下了3种颜色的积木，但是你不能把它们都放进最后一个盒子里。所以这样是不行的。

A:  So what you've shown is that we can't solve the problem for twelve colours by using the method we've been talking about, eliminating the colours one at a time. That doesn't mean,though, that there isn't some other method we could use to find a solution. How can we be sure that the problem can't be solved?
A：所以你已经证明了，如果只用我们之前的方法，一次消除一种颜色，那么当我们有12种颜色时这个问题无解。但是这不代表这个问题就不能够用其它方法解决。我们怎么能确定这个问题无论用什么方法都无解呢？

B:  We can't: sometimes it's possibleto fit up to twenty colours in: if you had twenty colours, but they could be arranged in pairs that added up to ten, then that would work.
B：我们做不到：因为有时候我们甚至可以解决20种颜色的问题：如果你有20种颜色的积木，而且这20种颜色可以被两两配对，使得每一对颜色的积木总数都是10，这个问题就有解。

A:  So what's the most we can hope tosay about twelve colours?
A：所以对于12种颜色的问题，我们最多能证明到什么程度？

B:  We could look for an example with twelve colours that definitely couldn't be solved. Then we could say that sometimes you can do it with twelve colours and sometimes you can't.
B：我们可以找一种情况，使得这12种颜色的积木一定无法按照题目要求装进盒子里，然后我们可以说当我们有12种颜色时有时候无解，有时候有解。

A:  OK. Think about this: we have onebrick of each of eleven colours, and the rest of the bricks are another colour,say white. Can that problem be solved?  Where would the eleven coloured bricks have to go?
A：好，思考一下这个问题：这12种颜色的积木里，其中11种的积木我们每种颜色有1块，然后剩下的所有积木都是第12种颜色的，假设说，白色。这个问题有解吗？那11块不同颜色的积木要怎么装盒？

B:  You could only have one of them in each box, and the rest of the box would have to be filled up with white. If you tried to have two in the same box, then there'd be a gap of eight spaces to fill up, and you'd have to use another colour for that, violating the rules.
B：这11种颜色的积木，你必须得在每个盒子里都只放1块，那么盒子里剩下的空位就要全装满白色积木。如果你试图在每个盒子里放2块的话，那么你还得再找8块白色积木来填满盒子里的空位，这样的话每个盒子里就有三种颜色的积木了，不满足条件。

A:  But if you have eleven colouredbricks, you can't put them in ten boxes without having at least two in one ofthe boxes. What does that tell us?
A：但是你有11块不同颜色的积木，如果你要把它们全都放进10个盒子里，就必须得有一个盒子里至少放有2块。那么这说明什么？

B:  That you can't solve the problemfor this combination of twelve colours.
B：那么当我们有12种颜色的积木，并且它们是这种颜色组合时，这个问题是无解的。

A:  So what can we conclude?
A：那么我们可以得到什么结论？

B: With ten or eleven colours, you can always solve the problem, using the method we talked about. But for twelve colours, sometimes the problem can't be solved at all.
B：当我们有10种或11种颜色时，运用我们刚才讨论过的方法，这个问题一定有解。但是当我们有12种颜色时，这个问题有时是无解的。

看完这份面试实录，你有那些感受呢？先说说我的体会：

1. 虽然这是Computer Science专业的面试，题目却没有直接涉及编程，而是一道考察学生底层算法能力的数学题。
即使学生没有编程经验，也能作答。而事实上，在牛津大学计算机学院的官网上明确写着，欢迎没有编程经验的学生报考。

2. 即使学生在刚开始没有给出所谓的“完美答案”，面试老师还是会给予学生一些必要的引导，并根据学生的作答情况，不断提出更深入的问题。
其实牛剑老师在刚开始就没有期待学生能在短短几分钟的时间里给出“完美答案”。他们要看的，就是你的分析、解题过程。

3. 最重要的一点，通过这段实录我们能真切的感受到，牛剑面试的目的：不是为了测试你已经知道了多少，而是要了解你如何思考。而这也正是传统中式教育和欧美教育最大的不同。

面试是通往牛津offer的最后一站，然而很多小伙伴一路披荆斩棘却最终败给面试，实在是遗憾。