Two Sigma面经 - 未名空间MITBBS历史存档

z*u2012-06-02 07:06

1 楼

面的sde。
1 对two sigma有什么了解，等等，自己的project，有什么application. 为什么选
择他们而不是Google 等。然后出了一个编程题，很简单。估计前面聊得不好，随
便出了个题意思意思。
2。8皇后问题，以及一个stock 为背景的统计问题，挣扎了很久，没弄懂题目，对
金融不了解。题目大概意思是别人愿意在一定的价格愿意买和卖，我们愿意在一定的
价格愿意买和卖， stock以一定的概率上涨或下跌，问我们挣得钱的期望是多少。
3。一个quant。
1。如何生成一组数据，使他们的distribution是正态分布 (不是写程序）
2。一个如何design 假设检验，来判断两个概率分布的均值是否相同。
3。一个人在森林里迷了路，森林与外部又一个直线的边界，已知目前位置距离边界
垂直距离是1mile，如何design strategy，使得走的路最少，然后能走到森林外部
去。
面完三面就让走人了。

d*o2012-06-02 07:06

2 楼

Not too hard and all are the basic question...

b*e2012-06-02 07:06

3 楼

看来吃到中饭了，再接再厉吧。
题目都不难，但是跟传统IT公司不一样，需要一点统计的知识。
即使不读John Hull,还是应该复习一下基本的统计知识。
3。1 just google box muller transform
3.2 should already be some statistical test for this, or ANOVA
3.3 recursion or dynamic programming

【在 z******u 的大作中提到】

: 面的sde。
: 1 对two sigma有什么了解，等等，自己的project，有什么application. 为什么选
: 择他们而不是Google 等。然后出了一个编程题，很简单。估计前面聊得不好，随
: 便出了个题意思意思。
: 2。8皇后问题，以及一个stock 为背景的统计问题，挣扎了很久，没弄懂题目，对
: 金融不了解。题目大概意思是别人愿意在一定的价格愿意买和卖，我们愿意在一定的
: 价格愿意买和卖， stock以一定的概率上涨或下跌，问我们挣得钱的期望是多少。
: 3。一个quant。
: 1。如何生成一组数据，使他们的distribution是正态分布 (不是写程序）
: 2。一个如何design 假设检验，来判断两个概率分布的均值是否相同。

y*g2012-06-02 07:06

4 楼

好难，，lz是统计的？

【在 z******u 的大作中提到】

: 面的sde。
: 1 对two sigma有什么了解，等等，自己的project，有什么application. 为什么选
: 择他们而不是Google 等。然后出了一个编程题，很简单。估计前面聊得不好，随
: 便出了个题意思意思。
: 2。8皇后问题，以及一个stock 为背景的统计问题，挣扎了很久，没弄懂题目，对
: 金融不了解。题目大概意思是别人愿意在一定的价格愿意买和卖，我们愿意在一定的
: 价格愿意买和卖， stock以一定的概率上涨或下跌，问我们挣得钱的期望是多少。
: 3。一个quant。
: 1。如何生成一组数据，使他们的distribution是正态分布 (不是写程序）
: 2。一个如何design 假设检验，来判断两个概率分布的均值是否相同。

t*72012-06-02 07:06

5 楼

直接跪了

p*o2012-06-02 07:06

6 楼

3.3我在一次面试中也遇到了。我给的答案是朝一个方向走x mile，然后从那点开始沿
以x为半径的圆弧走，最多走部分圆弧。最后以x 为参数 minimize 所走距离的长度，
求得结果x = 1 mile。不是很合理，后来在面试官提示下找到了答案。

【在 z******u 的大作中提到】

: 面的sde。
: 1 对two sigma有什么了解，等等，自己的project，有什么application. 为什么选
: 择他们而不是Google 等。然后出了一个编程题，很简单。估计前面聊得不好，随
: 便出了个题意思意思。
: 2。8皇后问题，以及一个stock 为背景的统计问题，挣扎了很久，没弄懂题目，对
: 金融不了解。题目大概意思是别人愿意在一定的价格愿意买和卖，我们愿意在一定的
: 价格愿意买和卖， stock以一定的概率上涨或下跌，问我们挣得钱的期望是多少。
: 3。一个quant。
: 1。如何生成一组数据，使他们的distribution是正态分布 (不是写程序）
: 2。一个如何design 假设检验，来判断两个概率分布的均值是否相同。

d*f2012-06-02 07:06

7 楼

这些其实不是统计，这个quant很明显是物理背景的，问得都是MC的东西

【在 z******u 的大作中提到】

: 面的sde。
: 1 对two sigma有什么了解，等等，自己的project，有什么application. 为什么选
: 择他们而不是Google 等。然后出了一个编程题，很简单。估计前面聊得不好，随
: 便出了个题意思意思。
: 2。8皇后问题，以及一个stock 为背景的统计问题，挣扎了很久，没弄懂题目，对
: 金融不了解。题目大概意思是别人愿意在一定的价格愿意买和卖，我们愿意在一定的
: 价格愿意买和卖， stock以一定的概率上涨或下跌，问我们挣得钱的期望是多少。
: 3。一个quant。
: 1。如何生成一组数据，使他们的distribution是正态分布 (不是写程序）
: 2。一个如何design 假设检验，来判断两个概率分布的均值是否相同。

s*y2012-06-02 07:06

8 楼

正确的应该是什么

【在 p*****o 的大作中提到】

: 3.3我在一次面试中也遇到了。我给的答案是朝一个方向走x mile，然后从那点开始沿
: 以x为半径的圆弧走，最多走部分圆弧。最后以x 为参数 minimize 所走距离的长度，
: 求得结果x = 1 mile。不是很合理，后来在面试官提示下找到了答案。

j*g2012-06-02 07:06

9 楼

有大侠知道
3。一个人在森林里迷了路，森林与外部又一个直线的边界，已知目前位置距离边界
垂直距离是1mile，如何design strategy，使得走的路最少，然后能走到森林外部
去。
这个题怎么做嘛。。。题目都看不懂。。。请赐教！谢谢~~~

N*N2012-06-02 07:06

10 楼

有点像lost cow problem的变种
不过现在你不是在寻找一个距离未知方向确定的点，而是寻找一条距离确定方向未知的
直线

【在 j********g 的大作中提到】

: 有大侠知道
: 3。一个人在森林里迷了路，森林与外部又一个直线的边界，已知目前位置距离边界
: 垂直距离是1mile，如何design strategy，使得走的路最少，然后能走到森林外部
: 去。
: 这个题怎么做嘛。。。题目都看不懂。。。请赐教！谢谢~~~

d*o2012-06-02 07:06

11 楼

问题就是方向未知距离可知
我想了一个办法，就是随便找一方向走，距离2^0.5，走到右转，走到右转。走完一个
正边形如果走到原点，就不转，最多走3个正边形就可以走到边界。
我没做过面试题，抛砖引玉。

【在 j********g 的大作中提到】

: 有大侠知道
: 3。一个人在森林里迷了路，森林与外部又一个直线的边界，已知目前位置距离边界
: 垂直距离是1mile，如何design strategy，使得走的路最少，然后能走到森林外部
: 去。
: 这个题怎么做嘛。。。题目都看不懂。。。请赐教！谢谢~~~

l*82012-06-02 07:06

12 楼

一个正方形边长4sqrt（2），3个不就是12sqrt（2）了。走出1mile，然后沿着以最初
的位置为原点，1 为半径的圆走，最多也就1+2 Pi 就找着了

【在 d**o 的大作中提到】

: 问题就是方向未知距离可知
: 我想了一个办法，就是随便找一方向走，距离2^0.5，走到右转，走到右转。走完一个
: 正边形如果走到原点，就不转，最多走3个正边形就可以走到边界。
: 我没做过面试题，抛砖引玉。

c*r2012-06-02 07:06

13 楼

大侠，可否说经提示后的合理答案是什么？

【在 p*****o 的大作中提到】

: 3.3我在一次面试中也遇到了。我给的答案是朝一个方向走x mile，然后从那点开始沿
: 以x为半径的圆弧走，最多走部分圆弧。最后以x 为参数 minimize 所走距离的长度，
: 求得结果x = 1 mile。不是很合理，后来在面试官提示下找到了答案。

N*N2012-06-02 07:06

14 楼

圆似乎是理论上最优解？但是实际中好像没有操作性，沿着1km外的圆心走一个圆这种
事情几乎不可能做到
如果面试的人指出这个问题的话，那我能想到的一个办法是这样：走出sqrt(2) km，如
果没出去，就返回原地，右转90度，重复上一步。这样在最坏的情况下就是前三个方
向各走出sqrt(2)然后返回，最后一个几乎到头才出去，一共走了7*sqrt(2) km，大约
是10。
最终走的路线相当于一个以原点为中心，边长为2的正方形的两条对角线。所有到原点
距离为1的直线（包括森林边界）必然是正方形内切圆的切线，这样的直线必然会和四
条对角线之一相交。
或者也可以走出一条对角线之后开始沿着边走，这样是8+sqrt(2)，稍短一点点。

【在 l********8 的大作中提到】

: 一个正方形边长4sqrt（2），3个不就是12sqrt（2）了。走出1mile，然后沿着以最初
: 的位置为原点，1 为半径的圆走，最多也就1+2 Pi 就找着了

f*c2012-06-02 07:06

15 楼

应该用角度来做？
假定圆弧半径是r，则定义角度 x 使得 r=1/cos(x)
我算的答案是 x 需要满足 cotan(x) = (pi-x)/2

【在 c********r 的大作中提到】

: 大侠，可否说经提示后的合理答案是什么？

t*g2012-06-02 07:06

16 楼

最后一个题可以用等边三角形?
某一边跟树林外围重合,当前所站位置为三角形重心
行走路线: 前行距离a至三角形某顶点，然后最多走完另外一条边，一定能到树林外围
计算结果是最大行走距离 2+2*sqrt(3)

【在 z******u 的大作中提到】

: 面的sde。
: 1 对two sigma有什么了解，等等，自己的project，有什么application. 为什么选
: 择他们而不是Google 等。然后出了一个编程题，很简单。估计前面聊得不好，随
: 便出了个题意思意思。
: 2。8皇后问题，以及一个stock 为背景的统计问题，挣扎了很久，没弄懂题目，对
: 金融不了解。题目大概意思是别人愿意在一定的价格愿意买和卖，我们愿意在一定的
: 价格愿意买和卖， stock以一定的概率上涨或下跌，问我们挣得钱的期望是多少。
: 3。一个quant。
: 1。如何生成一组数据，使他们的distribution是正态分布 (不是写程序）
: 2。一个如何design 假设检验，来判断两个概率分布的均值是否相同。

m*d2012-06-02 07:06

17 楼

最后一个题我直觉认为按照圆的渐开线走。但是不知道怎么证明。

f*c2012-06-02 07:06

18 楼

题目没有限制有没有办法保持圆形路径，比如用GPS定位出发点就可以走圆形路径
圆形路径的最优半径是r=1.2889 （假定出发方位是均匀分布）
这样算得的最糟情况（即走完半径然后沿大圆弧）须走7.63 mi.

【在 N**N 的大作中提到】

: 圆似乎是理论上最优解？但是实际中好像没有操作性，沿着1km外的圆心走一个圆这种
: 事情几乎不可能做到
: 如果面试的人指出这个问题的话，那我能想到的一个办法是这样：走出sqrt(2) km，如
: 果没出去，就返回原地，右转90度，重复上一步。这样在最坏的情况下就是前三个方
: 向各走出sqrt(2)然后返回，最后一个几乎到头才出去，一共走了7*sqrt(2) km，大约
: 是10。
: 最终走的路线相当于一个以原点为中心，边长为2的正方形的两条对角线。所有到原点
: 距离为1的直线（包括森林边界）必然是正方形内切圆的切线，这样的直线必然会和四
: 条对角线之一相交。
: 或者也可以走出一条对角线之后开始沿着边走，这样是8+sqrt(2)，稍短一点点。

f*c2012-06-02 07:06

19 楼

渐开线不可能是最优，可以证明对于每一渐开线走法，都存在一圆弧走法使得其最遭情
况优于该渐开线最糟情况

【在 m******d 的大作中提到】

: 最后一个题我直觉认为按照圆的渐开线走。但是不知道怎么证明。

k*n2012-06-02 07:06

20 楼

先走x (x>1)，然后沿切线走到圆上 sqrt(x^2-1)，
假设此时半径和走出来的直线所夹圆心角为 a, (cos(a) = 1/x)
然后沿大圆弧走 2(pi-a) 就可以了
因为已覆盖圆心角为2*a的所有切线，只用走到下面对称的切点
总路程
1/cos(a) + tan(a) + (1-a/pi)*2*pi
0当 a = pi/6 时上述值最小，为 5/6*sqrt(3) + 5/3*pi ~= 6.68
当然这个优化的是worst case
如果优化均值就更复杂了