一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 3857|回复: 31
收起左侧

Two Sigma 面经

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

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

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

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

x


上午的都是地里出现的题目:

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

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

. 1point 3acres 璁哄潧2. 给两个infinite stream, 每个data是(t_i, v_i), 要求输出两个stream所有(t_i - t_j)不大于一的(v_i, v_j). 不要求上机调试,只需要伪代码. From 1point 3acres bbs
给定的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).
.1point3acres缃设计data structure, 实现min sell price, max buy price, how much does it cost to buy XXX shares. From 1point 3acres bbs
先想的是priority queue,最后发现delete,不好实现. 最后在面试官提醒下才发现binary search tree 更好.. 鍥磋鎴戜滑@1point 3 acres
不过最后面试官说sorted linked list在实际中最好,因为交易都是发生在很小的区间里面, 只涉及前几个item.


给定N, a, b. 打印所有小于N的能被a或b整除的数
如 7, 2, 3, 输出:-google 1point3acres
2, 2
3, 3. 鍥磋鎴戜滑@1point 3 acres
4, 2
6, 2, 3
和面试官纠结了下bool是存在stack还是register里面. 最后没时间做follow up了.
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
2. 聊了一会简历.
两层玻璃叠在一起,一束光斜着照进来.问有几条beam是经过了i次反射.
刚开始没理解清除题目,一直在纠结光的反射和折射.最后没做出来.

然后hr过来说不move forward了.



评分

2

查看全部评分

maplain 发表于 2015-11-23 04:36:15 | 显示全部楼层
jjwqf 发表于 2015-11-23 02:21. 1point 3acres 璁哄潧
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时,
是:. 1point 3acres 璁哄潧
f(i) = g(i);
g(i) = g(i-2) + g(i-1);
g(0) = 1;
g(1) = 2;
回复 支持 3 反对 0

使用道具 举报

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

使用道具 举报

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

使用道具 举报

pennlio 发表于 2015-11-21 06:56:34 | 显示全部楼层
楼主啥时候面的啊?下午面了两轮 好牛,说不定有好消息呢
回复 支持 反对

使用道具 举报

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. from: 1point3acres.com/bbs
hr直接跟你说不给你offer?
. from: 1point3acres.com/bbs
hr直接说就到此为止了,你到下午了已经很优秀了。但是我们bar很高。。。
回复 支持 反对

使用道具 举报

 楼主| caigaa 发表于 2015-11-21 22:17:04 | 显示全部楼层
pennlio 发表于 2015-11-21 06:56
楼主啥时候面的啊?下午面了两轮 好牛,说不定有好消息呢

直接当场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. more info on 1point3acres.com
请问楼主是面的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很高。。。
. 鍥磋鎴戜滑@1point 3 acres
这样的啊....难道是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?
.鐣欏璁哄潧-涓浜-涓夊垎鍦
我当时没做出来,他的折射应该就是直射,直线透过去,我当时傻逼的在想折射率之类的。。。
. visit 1point3acres.com for more.
面完想了下,应该是 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来找到他们想 ...
. 1point3acres.com/bbs
之前也是这么听说的,不过第二轮是个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, 2016-12-8 05:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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