WorldQuant的笔试题

作者:, 发表于

今年找工作并且常在水木混的人对WorldQuant这个公司应该不陌生,因为它在各求职版周期性发帖,标题是「美国著名对冲基金!   超百万收入!!!」,而且中英文轮流上,让人不注意也难。

WorldQuant的笔试以难度注明,考试时间也超长,5个小时以上,绝对是智力和体力的双重挑战。

今年这次校园招聘马上就要开始了。先贴一个网上找到的去年的WorldQuant笔试题(好像去年才进入中国,所以也只有这么一次的样本)。大家先热身一下。

300层楼,3个一样的小球,设计一个策略,得到小球摔碎的临界层数,并且要求最坏情况下所试次数最少。

经典的扔鸡蛋问题,只不过现在有三个鸡蛋。解题思路一样的,都是动态规划。

记F(n, k)为n层楼,k个球时所需要的最少尝试次数,则

F(n, k) = min ( F(n-r, k) + 1, F(r-1, k-1) + 1), r = 1, 2, …, n;

F(n, 1) = n;

一百个眼镜,摆成一个圈,全部正面向上,第一个人将每个翻动一次,一共翻了100次;第二个人从no.2开始隔一个翻一次,也翻100次;第3个人从no.3开始隔两个翻一次,翻100次,问100个人之后,多少眼镜正面向上

以前有个类似的题目说的是眼镜在一个直线上,现在这个版本要难一些。

对序号为 \(x\) ( \(x=1,2,\cdots, 100\) )的眼镜,如果 \((100,i)|x\) ,它在第 \(i\) 轮翻动的次数为 \((100, i)\) ,否则没有被翻动。所以它总共被翻动的次数为

\[\sum\limits_{(i,100)|x} (100, i) = \sum\limits_{d|(x,100)} d\varphi(\frac{100}{d})\]

其中这里 \(\varphi(z)\) 为1到 \(z\) 中与 \(z\) 互素的数的个数。注意到上面式子右边要么 \(d\) 为偶数,要么 \(\varphi(\frac{100}{d})\) 为偶数,所以所有眼镜都被翻动偶数次,从而最后所有眼镜都是正面朝上的。

一个蛋糕,切成连续的n块,有m个豆,问如果每小块上放一种豆,并且要求相邻的2块上的豆不一样,有多少种方法。

???

一条东西向长街,你站在街中间,街北是一排门,你有一把钥匙,请写出一种策略,要求X/N在最坏情况下最少,X为你到达正确的门时所走的总路程,N为正确的门距原点的距离,可以假设门与门之间距离为1。

动态规划?

都不怎么会做 :(

Q.E.D.


上一篇:网易笔试题2008年10月30日
笔试多了,便会发现题目大同小异,很多笔试考的时候就是考经验和见世面。下面收集一些。 Fibonacci数列中,一个Fibonacci数如果与它之前的Fibonacci数均

下一篇:绿皮书里的智力面试题2009年3月25日
题目来源:《A practical Guide to quantitative finance interviews》,解答和书上的可能不一样。


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。