一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

一亩三分地官方iOS手机应用下载
查看: 6361|回复: 37
收起左侧

Two Sigma 面经

[复制链接] |试试Instant~ |关注本帖
caigaa 发表于 2015-11-21 05:13:34 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 博士 全职@TwoSigma - 内推 - Onsite |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x


上午的都是地里出现的题目:. from: 1point3acres.com/bbs

1. Design reverse polish notation. 主要是问怎么设计operator, 好方便添加新的.
上机写了加法和乘法,用了factory mode, 但是是用switch做判断. . 1point3acres.com/bbs
follow up, 如何添加新的operator, 并且不能改现有code (switch需要改代码). 没有思路,面试官说可以用map 存储所有的operator

用一个array存储一个树,每个节点存着父节点的index, 还有一个bool代表当前节点是否valid.
要求实现删一个子树.
允许添加新的data field到节点里面, 最后加了一个visited flag, 然后用recursion来删除节点.碰到visited 就返回,否则recur父节点

2. 给两个infinite stream, 每个data是(t_i, v_i), 要求输出两个stream所有(t_i - t_j)不大于一的(v_i, v_j). 不要求上机调试,只需要伪代码
给定的api是getNext(), 能够返回stream里面下一个data,但是如果没有data,就block.
最后用了两个thread,两个thread-safe queue来实现. 每次call getNext(), 和另一个queue里存的每个 item相比, 相差大于一就删除, 否则输出. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
follow up: 5个stream, 用一个bit set记住需要删除的item,当所有thread都要求删除时从queue里面删去

3. wildcard matching: 先要写test cases, 尽量多写些吧,我也不知道要写多少个.
用dp做的. 最后面试官问有没有更好地办法,稍微说了下这个解法:http://yucoding.blogspot.com/201 ... dcard-matching.html

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 吃过饭没被赶,还以为有机会.结果下午面两轮就被赶了...
1. 交易所的book里面有两个函数, add (id, company, prices, quantity, sell/buy), delete (id).
设计data structure, 实现min sell price, max buy price, how much does it cost to buy XXX shares
先想的是priority queue,最后发现delete,不好实现. 最后在面试官提醒下才发现binary search tree 更好.
不过最后面试官说sorted linked list在实际中最好,因为交易都是发生在很小的区间里面, 只涉及前几个item.


给定N, a, b. 打印所有小于N的能被a或b整除的数.1point3acres缃
如 7, 2, 3, 输出:
2, 2
3, 3
4, 2
6, 2, 3
和面试官纠结了下bool是存在stack还是register里面. 最后没时间做follow up了.

2. 聊了一会简历.
两层玻璃叠在一起,一束光斜着照进来.问有几条beam是经过了i次反射.
刚开始没理解清除题目,一直在纠结光的反射和折射.最后没做出来.

然后hr过来说不move forward了.



评分

2

查看全部评分

本帖被以下淘专辑推荐:

maplain 发表于 2015-11-23 04:36:15 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
jjwqf 发表于 2015-11-23 02:21
lz光的直射这道题,题目问的是什么?能详细说明一下么,谢谢!

我猜:
就是两块玻璃叠在一起,这样有三个平面可以反射,然后问你经历了i次反射的光有多少?

比如:
经历了0次反射的光只有一束,那就是最初射入的那束光线,在每一个平面都穿过去(当然了,实际情况有衰减),最后从第三个平面穿过永远地离开了玻璃们;

经历了1次反射的光有三束,因为最初射入的那束光线可以分别在第一,二,三个平面选择反射后沿着既定方向离开玻璃;

经历了i次反射的光的数目其实就是fibonacci数列。记:从第一个平面(由对称性,第三个平面也是一样的)向内部发射的光经历了i次反射后离开玻璃们的数目为g(i),那么g(i)(i>=2时)应该由两部分组成:
1. 在第二个平面反射一下,然后回到第一个平面,再反射一下后的那部分光,也就是g(i-2);
2. 穿过第二个平面,在第三个平面反射一下,也就是g(i-1);
所以。。就是fibonacii数列咯。只不过g(0) = 1, g(1) = 2;

所以按照我的这个理解,结果是:
f(0) = 1, f(1) = 3, i >= 2时,
是:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
f(i) = g(i);
g(i) = g(i-2) + g(i-1);
g(0) = 1;
g(1) = 2;
回复 支持 4 反对 0

使用道具 举报

leixiang5 发表于 2015-11-21 05:56:49 | 显示全部楼层
关注一亩三分地微博:
Warald
楼主下午的第一个面试和我一个面试官。。题目完全一样。。面试官是个vp。然后做high frequency的...我当时傻逼到第二题没想出来。。面试官看不下去直接改我code- -。只能说当时被上午折磨的脑子不好使里。
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-11-21 05:57:16 | 显示全部楼层
hr直接跟你说不给你offer?
回复 支持 反对

使用道具 举报

pennlio 发表于 2015-11-21 06:56:34 | 显示全部楼层
楼主啥时候面的啊?下午面了两轮 好牛,说不定有好消息呢
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

LYJALEX__ 发表于 2015-11-21 09:12:24 | 显示全部楼层
楼主面的是什么职位啊?
回复 支持 反对

使用道具 举报

RichardCen 发表于 2015-11-21 14:34:42 | 显示全部楼层
请问楼主是面的houston 还是 ny office?

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| caigaa 发表于 2015-11-21 22:14:59 | 显示全部楼层
leixiang5 发表于 2015-11-21 05:56
楼主下午的第一个面试和我一个面试官。。题目完全一样。。面试官是个vp。然后做high frequency的...我当时 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
可能是同一个,是个vp。第二题不知道他想问啥,没时间做follow up
回复 支持 反对

使用道具 举报

 楼主| caigaa 发表于 2015-11-21 22:16:00 | 显示全部楼层
leixiang5 发表于 2015-11-21 05:57
hr直接跟你说不给你offer?

hr直接说就到此为止了,你到下午了已经很优秀了。但是我们bar很高。。。
回复 支持 反对

使用道具 举报

 楼主| caigaa 发表于 2015-11-21 22:17:04 | 显示全部楼层
pennlio 发表于 2015-11-21 06:56
楼主啥时候面的啊?下午面了两轮 好牛,说不定有好消息呢
.鏈枃鍘熷垱鑷1point3acres璁哄潧
直接当场reject了,下午本来三轮的,没能到最后啊
回复 支持 反对

使用道具 举报

 楼主| caigaa 发表于 2015-11-21 22:17:22 | 显示全部楼层
LYJALEX__ 发表于 2015-11-21 09:12
楼主面的是什么职位啊?

software engineer, new grad
回复 支持 反对

使用道具 举报

 楼主| caigaa 发表于 2015-11-21 22:18:00 | 显示全部楼层
RichardCen 发表于 2015-11-21 14:34. 鍥磋鎴戜滑@1point 3 acres
请问楼主是面的houston 还是 ny office?

NYC,不过他们家面试都一样吧?
. from: 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

shawnzx 发表于 2015-11-21 22:31:49 来自手机 | 显示全部楼层
谢谢分享。请问光的反射和折射最后应该是怎样理解的?  用DP?
回复 支持 反对

使用道具 举报

KevinFromJail 发表于 2015-11-21 23:44:22 | 显示全部楼层
我当时下午面了不止3轮,一直面到了6点钟,见了很多不同组的老大
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-11-22 01:56:19 | 显示全部楼层
caigaa 发表于 2015-11-21 22:14. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
可能是同一个,是个vp。第二题不知道他想问啥,没时间做follow up

--第二题就是fizzbuzz- -
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-11-22 01:58:49 | 显示全部楼层
caigaa 发表于 2015-11-21 22:16
hr直接说就到此为止了,你到下午了已经很优秀了。但是我们bar很高。。。

这样的啊....难道是manager也能拒绝人的啊?我以为他们上午通过了之后。。然后下午的manager来找到他们想要的人。。不是应该三个都试了。如果没人要的话。那就是拒绝啊。
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-11-22 01:59:59 | 显示全部楼层
KevinFromJail 发表于 2015-11-21 23:44
我当时下午面了不止3轮,一直面到了6点钟,见了很多不同组的老大
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
你当时收到offer了?下午应该就是三轮manager的。上午3轮。。然后最后一轮hr跟你谈一下。
回复 支持 反对

使用道具 举报

 楼主| caigaa 发表于 2015-11-22 03:16:42 | 显示全部楼层
shawnzx 发表于 2015-11-21 22:31
谢谢分享。请问光的反射和折射最后应该是怎样理解的?  用DP?

我当时没做出来,他的折射应该就是直射,直线透过去,我当时傻逼的在想折射率之类的。。。

面完想了下,应该是 f(0) = 1, f(1)=3, n >= 2, f(n) = floor(n/2) + floor((n+1)/2)*2.
回复 支持 反对

使用道具 举报

 楼主| caigaa 发表于 2015-11-22 03:18:41 | 显示全部楼层
leixiang5 发表于 2015-11-22 01:58
这样的啊....难道是manager也能拒绝人的啊?我以为他们上午通过了之后。。然后下午的manager来找到他们想 ...

之前也是这么听说的,不过第二轮是个senior vp,估计他可以直接reject吧
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-11-22 04:39:34 | 显示全部楼层
caigaa 发表于 2015-11-22 03:18
之前也是这么听说的,不过第二轮是个senior vp,估计他可以直接reject吧

下午都是senior vp了吧。我的下午三轮最senior是第二轮。。就是你的第一轮那个..first name k...last name y....其他都是代替组来的..可以问问hr feedback。。我问了。他就给我了。。可是hr给的太vague..看不懂。。说什么looking for stronger technical performance in regards to programming knowledge..不知道是不是说java水平太烂了...
回复 支持 反对

使用道具 举报

KevinFromJail 发表于 2015-11-22 10:06:42 | 显示全部楼层
leixiang5 发表于 2015-11-22 01:59
你当时收到offer了?下午应该就是三轮manager的。上午3轮。。然后最后一轮hr跟你谈一下。

绝对不止3轮 我应该至少面过5轮 人太多了 都记不太清有多少个了 第二天还有个manager打电话给我 第三天恰好他们cto在我们学校 还见面聊了一下 然后第四天收到offer
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-2-28 21:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表