WorldQuant的笔试题_求职面试

您所在的位置：程序员俱乐部 > 非技术区 > 求职面试 > WorldQuant的笔试题

WorldQuant的笔试题

2010/12/2 10:22:42 程序员俱乐部我要评论(0)

摘要：今年找工作并且常在水木混的人对WorldQuant这个公司应该不陌生，因为它在各求职版周期性发帖，标题是“美国著名对冲基金！超百万收入！！！”，而且中英文轮流上，让人不注意也难。WorldQuant的笔试以难度注明，考试时间也超长，5个小时以上，绝对是智力和体力的双重挑战。今年这次校园招聘马上就要开始了。先贴一个网上找到的去年的WorldQuant笔试题（好像去年才进入中国，所以也只有这么一次的样本）。大家先热身一下。300层楼，3个一样的小球，设计一个策略
标签：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})$ 为偶数，所以所有眼镜都被翻动偶数次，从而最后所有眼镜都是正面朝上的。