2020牛津线上面试如何准备？不妨先来看看这场面试官和学员间的绝密对话

最近是牛津大学发面试邀请的关键时机，很多同学都应该在准备牛津大学面试了，虽然今年的面试是以线上的形式，但是面试的内容还是和往常线下一样，想知道2020牛津线上面试如何准备吗？先来看看牛津大学计算机科学专业的面试官和学员之间的对话吧！

题目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?

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?

B：当然可以：你只需要把这十块积木都放进一个盒子里。这个盒子只装一种颜色的积木，我们甚至都不需要把条件放宽到一个盒子装两种颜色。

A:  Good. Now suppose you have two boxes and 20 bricks in two different colours. Could you solve the problem then?

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?

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?

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?

B：现在剩下9个盒子，以及9种颜色的积木块90个。

A:  So what should our next step be?

B：我们可以用和刚才相同的方法来装第二个盒子：选一种少于平均数目的颜色，把所有积木装进去，再选一种多于平均数目的颜色，用其中一部分把剩下的空位填满。我们只要重复这一步骤，就可以每步消除一个颜色了。

A:  That's very good. How does the process end?

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?

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?

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?

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.

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?

B：显而易见，需要（10 – x）块。

A:  Right. And how many bricks do we have left, after putting the x bricks in the next box?

B：嗯，我们原本一共有10n块积木，所以现在我们有（10n– x）块。

A:  So what is the average number of bricks of each colour that we have left?

B：是(10n - x)/n，也就是（10- x/n）块。

A:  Is that smaller or larger than 10- x?

B：（想了一会）因为n ≥ 1，那么x/n ≤ x，所以 10- x/n ≥ 10 – x。

A:  So what does that mean?

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?

B：当我们有12种颜色的时候，这个问题有解吗？

A:  Well?

B：我们可以跟刚才采取同样的方法，一次消除一种颜色。不过我不太确定刚才的计算能够证明我们可以填满盒子里的空位。

A:  Even if we could always fill the gap, what would we be left with when we got down to one box?

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?

B：我们做不到：因为有时候我们甚至可以解决20种颜色的问题：如果你有20种颜色的积木，而且这20种颜色可以被两两配对，使得每一对颜色的积木总数都是10，这个问题就有解。

A:  So what's the most we can hope tosay about twelve colours?

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?

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?

B：那么当我们有12种颜色的积木，并且它们是这种颜色组合时，这个问题是无解的。

A:  So what can we conclude?

B：当我们有10种或11种颜色时，运用我们刚才讨论过的方法，这个问题一定有解。但是当我们有12种颜色时，这个问题有时是无解的。

同学们看完了这些对话是不是能看出来面试官更注重对于学员底层算法能力的考察呢？面试官会根据同学们的回答不断诱导你最初更深入的思考与回答，我们也能够明显的看出牛津大学的面试官更看重的是同学们的分析、思维展现的过程。 牛津大学的面试即将到来，如果您想增加面试成功率的话，就一定要来唯寻模拟面试，前牛剑招生官和你一对一面对面交谈。

点击2020牛津物理专业面试buff来了 前牛津面试官给你做1对1模拟面试

2021牛津面试时间已出 各学院面试真题助你斩获了解更多。