WorldQuant的笔试题

zhiqiang11月 26, 2008 科学

今年找工作并且常在水木混的人对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。

动态规划？

都不怎么会做

查看更多关于worldquant, 笔试的内容。

你可能感兴趣的

At 2008.11.26 19:23, xiaorsz said:

这题太变态了！！

[Reply]
At 2008.11.26 23:48, bobye said:

第二题第k个人和第（100－k）个人可以看成翻的方向相反（一个顺时针，一个逆）。

[Reply]
At 2008.11.27 09:04, dasd said:

asdasd

[Reply]
At 2008.11.27 09:34, Teddy said:

蛋糕是m 种豆？

[Reply]
At 2008.11.27 09:48, Teddy said:

开门的题目门没有序的东西在里面，开一扇门看不出某种划分啊。要我就先走到头，在往另外一头，哈哈
最坏情况 (x/n) = 3

[Reply]
- At 2008.11.27 10:22, Teddy said:
  
  试着证明一下，权当笑话。
  首先所有门都要打开，一个下届是2，假如不用全打开，那么可以设置最坏情况为未打开的门来反证。
  
  算法必然要经过两个端点。加入增加一个时间y轴，画出算法的路径，那么做断电和右端点就是必达的边界，在这个过程中，两个端点的到达必有先后，至少要先到一个端点，那么至少就是n，然后再到另一个端点，至少+2n。
  
  [Reply]
- At 2008.11.27 10:29, zhiqiang said:
  
  你这个最坏情况是2n+1，比如你往左边走到头再回到右边，这时候右边第一个门特别差。
  
  [Reply]
  - At 2008.11.27 10:39, Teddy said:
    
    是啊，这就是这个策略的最坏情况，我只是想证明所有的策略都是需要必然经过两个端点的，那么最坏情况的下界就是（n + 2n)。如同基于比较的排序下界一样. 不过不知道这个证明是不是有问题！
    
    如果没问题，那么这个策略本身就是可行的。
    
    [Reply]
    - At 2008.11.27 11:39, zhiqiang said:
      
      你证明了总长度至少为2n+n，这个没有问题。但是题目要求的不是总长度的下界，你再仔细读一读题目吧。
      
      [Reply]
      - At 2008.11.27 13:53, Teddy said:
        
        Sorry,的确错了！
        
        [Reply]
  - At 2008.12.27 23:31, Cofeeling said:
    
    数据解构~
    
    [Reply]
At 2008.11.27 10:18, AI said:

第三题第四题题目都看不懂，google "interview cake bean different" "interview street door" 也没找到正常表述的题目，Faint

[Reply]
At 2008.11.27 16:20, ynifbs215 said:

眼镜那题你解错了吧，虽然最后答案是对的~

[Reply]
At 2008.11.28 17:31, Changyuan said:

开门问题最好的确定性算法是9近似算法。
策略：假设初始位于0点，先向右走到1，再向左走到-2，再向右走到4，再到-8，再到16，再-32，。。。。

参考文献为这篇文章：
R. Baeza-Yates, J. Culberson, and G. Rawlins. Searching in the plane. Inform.
Comput., 106:234{252, 1993.

[Reply]
- At 2008.12.10 00:48, Think said:
  
  http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.3991
  可以下到Searching in the plane。
  
  [Reply]
At 2008.11.28 17:37, Changyuan said:

上面是针对不知道门在多远的情况。
如果知道门在一定距离内，也有篇论文做了这个。
How to Find a Point on a Line within a Fixed Distance.
Christoph Hipke, Christian Icking, Rolf Klein, Elmar Langetepe.
http://www.pi6.fernuni-hagen.de/publ/tr220.pdf

[Reply]
- At 2008.11.29 18:57, AI said:
  
  赞，原来题目说得是这个意思
  
  [Reply]

« 中国崛起策三十八：以全国统一的失业保险来抵御经济危机

分析一个旧笑话 »

WorldQuant的笔试题

查看更多关于worldquant, 笔试的内容。

17条留言 -> 跳到留言表格

阅微堂