Oxford Msc CS

附剑桥的面试，当时在实验室，没有中文输入法，只有英文版的…………（坛子上的应该都看得懂英文）：http://www.1point3acres.com/bbs/thread-51844-1-1.html
中英合作，3+1
GPA:中方89.21（top 2%) 英方 78 （英国70是A)
因为拿到了剑桥的ad之后oxford才来的面试，所以也没准备就直接裸面了，显然没有剑桥面的那么好。
是1月4日压着奖学金的deadline申的（当然Msc怎么可能有奖学金呢= =）
1月中发了个几道题，48小时内答完，当时心情不好也没找大神问，自己一个人闷着做了。

（题干，前面两题问有什么选课兴趣，就不贴了）

3.)  Suppose you have a wire mesh which is N by M units long, made up of unit square with wire at the edges.  (So there are N+1 parallel wires all M long and, perpendicular to these, M+1 all N long).

An ant starts off at the bottom left corner of this grid (co-ordinates (0,0) and crawls on the wires the shortest possible distance to reach the top-right corner (N,M).

How long is the shortest route.

How many different shortest routes are there? (Namely, find a formula in terms of N and M)  You might want to try this for small values of N and M and see if you can work out how the number for (N,M) relates to those for (N,M-1) and (N-1,M)

If you build up a table of these numbers you might recognise them from elsewhere in mathematics so that might help you find the formula, but you also try to explain the connection.

4.) Consider the following (unrealistic!) investment problem.

We have a set S of n potential investments, each given by a pair of floating point numbers (amount, estimated return)  There is a total amount A to invest; we want to select investments to maximise the return on this amount.

One may select each investment (a,r) as a whole (spending all of a, and getting r return) or only can select only a fraction f (spending (f*a), and getting (f*r) return). The estimated return of a set of selections is the sum of the returns of the individual selections. Obviously, in selecting elements of S, we cannot spend more than the total amount A available.

Describe an efficient algorithm for computing the maximum estimated return that can be realised with amount A and set of investments S. What is the time complexity of your algorithm (in big-oh notation)?

Is it the best possible?

第一道高中题从(0,0)到(m,n)有几种走法
还有一道排序的题根据数据的大小的分情况给了两种算法，第二种的复杂度我也没算就交了。。。

3月5日发邮件说要面试，要了电话号码，说需要纸和笔，3月8日电话面试。

---------------------------------------------------
老师：你本科是EE，为什么要学CS
我：（牛津没有EE啊，大哥= =）其实吧……我是参加了些小项目小比赛，虽然没有奖，但觉得CS挺有意思的
老师：你是代表学校参赛还是朋友组团
我：朋友组团（如实交代，没那么牛。）
老师：哦，话说你CV上这个奖学金是怎么回事。
我：balabala，学院排名高给的，前x%给的。
老师：是高考考的高给的么？（怎么连高考都知道）
我：不是（我能说高考考top2落榜了么= =）是学校平常表现还行给的
老师：你这个中英合作办学是怎么回事？
我： 巴拉巴拉……

. 1point3acres老师：我看你成绩单上有Java，那课你上了多少小时
我：40小时
老师：那lab
我：忘了，大概有10个小时。
老师：你编过程么
我：Why NOT!（必须啊！没编过程还是Java么）
老师：你编过啥
我：打个纸牌游戏

老师：哦，行，你有paper么？
我：没有……是要我submit篇paper给你么，学术无力没paper
老师：我是问你有没有纸和笔，来咱们做两道题
我：………………………………………………………………有…………………………
--------------------------------------------------
答题环节（(⊙o⊙)）

老师：你还记得你邮件答得题么，问(0,0)到(m,n)的有多少种走法
我：记得啊，答案就是C(M+N,N)（不会说英语的C(M+N,N）真是伤不起，凭感觉说的，索性对方也听懂了）
老师：现在改成三维的从(0,0,0）到(M,N,P)，有多少种走法
我：（秒答。毕竟高中题么……）C(M+N+P,M)*C(N+P,N)*C(P,P)
老师：为什么
我： balabala（这块略过了……大家都知道为什么）
老师：挺好，来到一下题，问下O(nlog(n))是怎么定义的
我：balabala（还好还记得）
老师：挺好，那咱们算下O(2^N)和O(N^LogN)谁更糟糕
我：（自己虽然看了这么多年英文课本，但发现从来没有系统培训过英文的数字公式该怎么读，他的数字描述挺咬不准的，让他重复了好几遍）
（重复了几遍）终于咬准了……大脑开始短路了……半天不知道怎么办（总想着N^LogN也许能换成e^N，也不知道当时怎么想的= =）
老师：你丫太菜了，你看他们底……
我：（打断他）应该换底- -，然后把换底结果告诉他，光比幂就行了N,(logN)^2
老师：然后呢？
我：（又短路了= =) 带个大点的N试试？
老师：你这是作弊……
我：（话音刚落） 噢噢噢噢！求导求导，得到1和logN/N
老师：然后呢
我：1>logN/N，所以……
老师：……那这样吧……
我：（数据结构没好好学，哎，但也能看出面试的题都非常基础）
-------------------------------------------------------
老师：你想学啥
我：AI NLP什么的，挺好玩的
老师：我看你毕设做的这个，问下Expectation Maximaziation是干嘛的
我：balbala...........
老师：答得还行，你有什么问题么？
我：牛津Msc有多少继续读博士的？
老师：这个不敢保证，我们班每年招50人，我估计可能5-10个，也可能更多的继续读了博士。 因为除了留在牛津的还有些同学去了剑桥或者CMU继续读了，我不是很确定。
我：好吧，没啥问题了。。。（纯裸面也懒得问牛津小农村和伦敦大城市学术工业有什么区别没有）
-----------------------------------------------------------
下周出结果，总之裸面么……
1.心得，你要会拿英语说数字…… C(M,N) 2^5怎么说这些问题……大学四年一直不注意，这下真是伤不起= =
2.问的题都很基本，如果本科学习没偷懒，面试前根本不需要特别复习，这些题很容易就能答出来。
没什么了，有问题跟帖囧。

如果牛津拿到了那你是去剑桥还是牛津？

想去美国- -，但除了UMD来了个Rejected剩下都没消息。

哈哈，paper那个好有趣