Two Sigma 面经

KevinFromJail 发表于 2015-11-22 10:06
绝对不止3轮 我应该至少面过5轮 人太多了 都记不太清有多少个了 第二天还有个manager打电话给我 第三天恰 ...

是吗？可是我问过一个收到offer的。也是下午三轮。再加一轮hr。
不管几轮吧。。收到offer letter才是王道。

感觉光的那道题，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;

caigaa 发表于 2015-11-21 19:16
我当时没做出来，他的折射应该就是直射，直线透过去，我当时傻逼的在想折射率之类的。。。

面完想了下 ...

lz光的直射这道题，题目问的是什么？能详细说明一下么，谢谢！

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;

maplain 发表于 2015-11-23 04:36
我猜：
就是两块玻璃叠在一起，这样有三个平面可以反射，然后问你经历了i次反射的光有多少？

题目理解是对的。

感觉你这个答案是对的。我的想法还是不对， 把重合的光线当同一条了。。。

caigaa 发表于 2015-11-23 09:11
题目理解是对的。

感觉你这个答案是对的。我的想法还是不对， 把重合的光线当同一条了。。。

求问：
1.
  “follow up: 5个stream, 用一个bit set记住需要删除的item,当所有thread都要求删除时从queue里面删去”
  这里的follow up的意思是说任意两个stream中的数在一定范围内就输出么？

2.
  “3. wildcard matching: 先要写test cases, 尽量多写些吧,我也不知道要写多少个”
  就是用JUnit简单的写下各种case么？

3.
  “用dp做的. 最后面试官问有没有更好地办法,稍微说了下这个解法:http://yucoding.blogspot.com/201 ... dcard-matching.html”
   面试官有说什么是“更好的”么？

4.
   “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.”
    请问这里的min sell price, max buy price是说基于某id，或者某company么？具体要实现的函数签名是什么呀。。以及how much does it cost to buy XXX shares又是什么意思？股价不是在变动么。。按照最近交易的价格？

5.
   “和面试官纠结了下bool是存在stack还是register里面. 最后没时间做follow up了.”
   为什么会扯到bool是存在stack还是register的问题。。？以及求问follow up是什么？

问题比较多。。麻烦楼主了！！
谢谢

maplain 发表于 2015-11-23 14:47
求问：
1.
  “follow up: 5个stream, 用一个bit set记住需要删除的item,当所有thread都要求删除时从qu ...

1. 是的. 这样必须所有stream都大于1了才能删除

2. 我用的c++, 直接输出结果和预期结果是否相等, java应该也可以直接输出吧,不过junit应该更好

3. 没有. 不过我知道的最好的就是那个链接里的算法了

4. 按照company来的,id是交易号.股价变动是因为这些交易. 买方会给定自己买的最高价,卖方会给最低价

5. 这个是我实现的时候,用了两个bool存储a,b能否整除. 他先说了有follow up, 但没时间就没接着问我.我也不知道后面要问啥

直接说不move forward？

JamesJi 发表于 2015-11-23 23:51
直接说不move forward？

是啊, 够不上他们家的bar

caigaa 发表于 2015-11-23 23:35
1. 是的. 这样必须所有stream都大于1了才能删除

2. 我用的c++, 直接输出结果和预期结果是否相等, java ...

根据楼主的提示，我对下午第一面第一问的想法是：

用一个map存company -> prices，其中prices用BST来存，TreeNode中同时记录quantity，然后把buy价格改成负的，这样min sell price就是找比0大的第一个元素，max buy price就是最小元素，都是log(n)。然后还有一个map是id -> (Company, price)，这样根据id可以找到这次交易对应的company和价格，然后由company找到对应的BST，然后从BST中删除指定价格的TreeNode, 也是log(n)。
最后how much does it cost to buy XXX shares就是找到company对应的那个BST，找到比0大的所有元素(sell price)，然后一个一个枚举，叠加价格，直到满足我们需要的share为止。in worst case, O(n)？

楼主说的sorted linked list是说，用company -> 两个sorted linked list，一个递增存sell price,一个递减存buy price么？ 因为价格波动范围小，所以近似的add和delete，都是O(1)的时间？

不知道理解的是否正确。。求楼主指正。

谢谢！