一亩三分地论坛

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

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

Two Sigma Onsite面经

[复制链接] |试试Instant~ |关注本帖
diyutianshi 发表于 2016-5-17 11:05:49 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 博士 全职@TwoSigma - 猎头 - Onsite |Pass在职跳槽

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

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

x

上午第一场,Reverse Polish Notation。大概跟他扯了几句直接上手就写了一个以Operator为base class,然后Add,Subtract, Multiply, Divide四个class继承这个Operator base class的写法,一遍写完调过跑通样例。他就说,你这个实现的是基本的binary operator,如果要支持unary或者是ternary怎么办呢?我就把Operate(intval1, int val2)直接改成了Operate(vector<int>& vals),一开始想直接定义一个int NumOperands但是不知道为啥C++居然编译挂了,他就说要不咱们改成一个函数getOperands(),这当然没问题了。写过之后又是传统的follow-up question问怎么才能直接给用户binary,让他们可以自由的添加新的operator。我就说好像听说Java可以,C++我说一个简单粗暴的办法是跟用户约定好DLL然后去call这个DLL……他说倒是也行,不过他觉得更好的办法是做XML / JSON的serialization,我表示认同。然后就没有任何悬念的进入了下一题Remove subtree from tree……其实就是类似于DP的思想,加个visited来做memoization,一开始没处理好边界条件小挂了一下改好之后他说你这个code是work的,但是如果第二次运行会有bug……我思考了一下发现我没有更新arrayTree-> size,而且更新了size之后初始化的时候得用capacity。后来他又说这code还会有啥问题么?我就想了两个case,一是index不合法,二是删除一个已经被删除的subtree的时候size会继续往下减,就不对了,所以加了一个特判。这场面试就愉快的结束了,然后我问他这个题目有没有linear time constant space的做法,他说据他所知没有,我的做法应该就是最好的了。
第二是printtimestamps with diff < 1和website太慢应该怎么办……面经上对于这个题目的意思一直都说的很不清楚,正确的说法是有两个blocking queue,每个queue里面存的是一个tuple <timestamp, value>,我们想找到在这两个queue里面timestamp相差 <= 1的所有pair应该咋做。我一开始一直不理解为什么大家写的code都说要加锁,anyway我就先开始写了,反正大概就是先写calculatePair(queue<int> q1,queue<int> q2)的函数,然后假设是q2新来了一个timestamp,直接判断q1的front中的timestamp是否和q2.back()的timestamp相差值大于1,如果大于1不断pop即可。锁是出现在这儿的,因为两个queue都是blocking queue,也就是说如果调用int val= qs1.Take(),如果这个时候qs1没有来新data那么整个程序会block住,所以如果是一个while (true)的loop去调用calculate(q1, q2)然后calculate(q2, q1)的话整个程序很容易就block了,所以要开两个线程然后加个锁,这个锁应该锁在两个take()函数之后,然后运行完calculate()之后再release。答完之后他说this works,然后就问如果有多个queue,比如10个queue怎么办,我一看这个followup地上好像没说过……看来答的还可以,有戏……我就大概说了一个对每个queue都要维护一个pairwise的pointer headlist,这个可以用一个minHeap维护,然后如果队首的timestamp小于minHeap的最小值就把这个timestamp pop掉,他表示认可。随后就是website太慢怎么办……我就开始画图了,从DNS -> CDN -> SLB -> Cache -> Web Service ->SLB -> Cache -> Message Queue -> Backend DB说了一遍,基本上能说的都说了,反正说到最后他问还有啥的时候都是开始blame user的机器太慢网络太差IE版本太低了……我就估计我基本说的差不多了,他后来想了很久说应该你基本都cover了,我就估计这一轮应该也OK了。
第三轮是wildcardmatching……他给了描述之后我直接给了DP的解法,他一开始还没有理解……自己看那个递归看了很久……看完之后他说你给这个DP的解法太顺利了,咱们就想想linear解法吧……妈的说实话我真的不知道有没有linear解法,LeetCode上那个所谓的linear解法显然是错的,那个是在backtracking……我就尝试问了一些问题比如说你是要worst case linear么还是说只是average case会快不少?我尝试解释了一下two pointer method他马上打断了说你这个本质就是在explore solution space,没有区别……妈的我就觉得这丫在黑我……我就思考来思考去,他就提示我说要用linear的pattern matching algorithm做building block……虽然我不会,但是这个时候还是得展示一下自己懂linear time的pattern matching algorithm……我就赶快说我懂Rabin Karp但是我不知道这个加了*和?怎么做hash。他就说不是这个意思,是要把这个作为building block……我想了很久说可以把通配符拆开,把原pattern string拆成以*和?分开的一些小的pattern string,在原text string上做pattern matching,然后得到一些匹配的index,在这个index上做DP……他说你close了,不过再想想,有更好的办法……我就说也许这个匹配可以greedy……他就问怎么greedy……我说每次取第一个,他就问你能否prove。。。然后后来他说这个greedy好像是错的……anyway,他说我们时间好像不够了,你先写DP吧。我就5分钟写了个DP,他可能觉得太快了……就让我加点testcase,我加完跑完一遍correct,就又开始扯其他的比如说怎么generate large scale的test case云云。后来他解释了一下linear的算法,说是先把不包含通配符的prefix, suffix先match掉,然后整个串就变成了类似于*p1*p2*p3*的样子,然后对于每个p_i可以做取第一个的greedy match……不过我其实并不知道带?的p_i到底应该怎么匹配,当然他这样说了我就点头称是然后说真NB……
中午去了Aurora,反正不是lunch interview我就不多说了,吃完之后我最关心的就是是不是可以回hotel了……HR过来跟我说你准备一下下午面谁谁谁,呵呵呵我居然也通过早上的面试了 =_=
下午第一轮,anyway完全是culture的question,基本就是介绍了一下我的工作以及whyTwo Sigma? 我就一直围绕着nice geek来谈的似乎他还挺满意……
下午第二轮,同样是culture question以及介绍自己以前的project,问了一个很弱的battleship怎么实现hit(int r, int c)的函数的问题……反正这个很脑残了我就不说了
下午第三轮,基本上也是culture方面的question,介绍了一下我的工作,然后他问了一个这样的题目:就是一个train在入站台和出站台的时候需要先减速再加速,问你车的哪个部位在整个站台停留的时间最长。我大概思考了一下乱说了一个head……后来work out math的时候我发现head和tail的时间是相同的,我就开始觉得应该是midway停留的时间最长,(这个时候有一个假设是减速和加速的加速度是相同的)。面试官说对,然后就问how much longer? 然后给了一个提示用s = 1/2 * a * t * t这个公式去推,我大概写了几行跟他说大概是(sqrt{2} - 1) longer,他有点惊讶因为他好像觉得我很多步骤跳掉了……anyway他觉得没问题,后来又问如果减速和加速的加速度不同那怎么办,哪个点停留的时间最长?我直接画了两下猜了一个表达式大概就说是要在车的(a2 / (a1 + a2))分界的地方……面试官就问为啥?我尝试work out math了半天未果,反正大概就是1/2 * a1 * t1 * t1 = x, 1/2 * a2 * t2 *t2 = S - x然后去maximize t1 + t2的值,很明显的我的数学水平已然不足以解决这个问题了……不过面试官说我很惊讶你一开始给的答案就是对的,我就说这个intuitively大概就是这样blah blah,然后他说不用推了我们又开心的聊了一些culture问题结束。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

评分

8

查看全部评分

本帖被以下淘专辑推荐:

leixiang5 发表于 2016-5-17 11:17:48 | 显示全部楼层
好厉害啊。第一次看到地里过了2 sigma的面经。
回复 支持 反对

使用道具 举报

menderr 发表于 2016-5-18 04:24:34 | 显示全部楼层
楼主很强大,很逗比~~
回复 支持 反对

使用道具 举报

dojiangv 发表于 2016-5-18 13:04:08 | 显示全部楼层
没分段看着好累啊
回复 支持 反对

使用道具 举报

mclover 发表于 2016-5-18 14:32:56 | 显示全部楼层
感觉TS喜欢有经验一些的,new grads真心不容易过
回复 支持 反对

使用道具 举报

eternity59 发表于 2016-5-19 02:10:49 | 显示全部楼层
楼主有消息了吗?我也跟你一天去面的
回复 支持 反对

使用道具 举报

 楼主| diyutianshi 发表于 2016-5-19 05:59:33 | 显示全部楼层
eternity59 发表于 2016-5-19 02:10
楼主有消息了吗?我也跟你一天去面的
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
嗯,我面过了
回复 支持 反对

使用道具 举报

eternity59 发表于 2016-5-22 11:14:45 | 显示全部楼层

我好像也是面过了,说给offer,然后又邀请我去纽约一趟是什么鬼?
回复 支持 反对

使用道具 举报

zxu12 发表于 2016-5-22 11:47:15 | 显示全部楼层
eternity59 发表于 2016-5-22 11:14
我好像也是面过了,说给offer,然后又邀请我去纽约一趟是什么鬼?

应该是带你认识一下2016年入职的new grad。去年我也是接到了这个邀请
回复 支持 反对

使用道具 举报

atinjosan 发表于 2016-5-26 08:54:02 | 显示全部楼层
谢谢。面经给的好详细!
回复 支持 反对

使用道具 举报

peterz 发表于 2016-6-19 00:37:43 | 显示全部楼层
感谢楼主分享面试细节,楼主表现太棒了
printtimestamps 有一个问题不太理解:
每次计算pair都拿两个queue的copy吗?还是应该用deque?因为如果拿copy的话没有办法update原来的queue啊

BTW,楼主接受offer了吗?. Waral 鍗氬鏈夋洿澶氭枃绔,
回复 支持 反对

使用道具 举报

 楼主| diyutianshi 发表于 2016-6-19 00:39:50 | 显示全部楼层
peterz 发表于 2016-6-19 00:37. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
感谢楼主分享面试细节,楼主表现太棒了
printtimestamps 有一个问题不太理解:
每次计算pair都拿两个queu ...

我没有接受offer
回复 支持 反对

使用道具 举报

peterz 发表于 2016-6-19 07:03:35 | 显示全部楼层

你提到 用一个 函数 calculatePair(queue<int> q1,queue<int> q2)
不是用 reference, 怎么实现更新queue呢?比如 取了q1.back(), 发现q2.front()比它大1,要pop掉,怎么更新原来的q2呢?-google 1point3acres
谢谢
回复 支持 反对

使用道具 举报

singledog2016 发表于 2016-6-24 01:48:22 | 显示全部楼层
楼主好强! 请问一下onsite 是不是每轮都需要在电脑里写代码,编译通过?
回复 支持 反对

使用道具 举报

singledog2016 发表于 2016-6-26 06:19:58 | 显示全部楼层
你好!看了你的two sigma面经,受益匪浅。请问能否发一下你onsite的源代码啊?gaoyuanyuan82@gmail.com仅仅参考一下,因为光看文字描述仍然不太理解题意。十分感谢!已经加米。
回复 支持 反对

使用道具 举报

hana4205 发表于 2016-7-18 08:43:16 | 显示全部楼层
楼主请问,火车进站那个题,sqrt(2) - 1这个是怎么算出来的啊?
谢谢~
回复 支持 反对

使用道具 举报

b00901192 发表于 2016-7-18 09:26:54 | 显示全部楼层
火車進站那題的第二題用 Cauchy Inequality 即可解出答案
回复 支持 反对

使用道具 举报

b00901192 发表于 2016-7-18 09:30:06 | 显示全部楼层
(t1^2 + t2^2)(1^2 + 1^2) >= (t1 + t2)^2, 當等號成立時,兩個向量平行,故得解。
回复 支持 反对

使用道具 举报

ancen 发表于 2016-8-3 05:45:24 | 显示全部楼层
多谢楼主分享!非常有用的信息。小弟最近也在准备Twosigma的onsite,看了一些其它面经关于楼主面试的这几道题的solution,但是始终觉得有一些bug。可否麻烦楼主发一下您当时onsite时候的solution或者准备onsite的时候写的sample code? 感觉里面需要注意的细节还是很多的。小弟邮箱是 ancenxixi@gmail.com。 多谢楼主!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 21:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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