Two Sigma一轮电面面经

一开始面试官还是介绍了一下自己的工作，然后问我的most challenging project。后面的non-codingquestion就是和面经上的一模一样了。

• What is a hash     table? What do you do to handle hash table collision? 我答了最基本的hash function, hash into a slot, linear probing, chaining     method, etc.
  
• Median in a     stream of integers - 我答了two heap的solution，然后补充说如果内存不够存stream可以用reservoir sampling     sample一个subset来估算。
  
• What is merge     sort? What is quick sort? What are their relative advantages and     disadvantages?
  您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  使用VIP即刻解锁阅读权限或查看其他获取积分的方式
  游客，您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  VIP即刻解锁阅读权限 或 查看其他获取积分的方式
  Unlock interview details and practice with AI
  Curated Interview Questions from Top Companies
  等于(weight of the     element) / (sum of all weights).
  
• setWeight(object, weight) -     update the weight of the object, or insert a new one if needed; if weight     is zero then remove this object.
  

我就直接map<int,int>的实现了一个，同时维护了一个totWeight。在getRandomObject()的时候产生一个随机数，mod到[1, totWeight]这个区间然后就iterate the current elements in the map。在setWeight()的时候注意维护totWeight。

面完之后我觉得这个题目其实是可以改造一下问很多follow-up question的，首先对于samplingfrom a discrete distribution我强烈推荐这个网页:

里面详细的讨论了很多变种以及非常重要的alias method。其次，对于刚才我们的naive的做法，每次sample是O(n)的但是setWeight是O(1)的，一个更好的做法应该可以把整体的复杂度优化到O(logn) - 这个还要再细细的想一想。

赞，祝lz好运。。。

bless lz. 请问 在getRandomObject()的时候产生一个随机数，mod到[1, totWeight]这个区间然后就iterate the current elements in the map， 这个啥意思？

bless lz. 请问 在getRandomObject()的时候产生一个随机数，mod到[1, totWeight]这个区间然后就iterate the current elements in the map， 这个啥意思？

我就直接map<int,int>的实现了一个，同时维护了一个totWeight。在getRandomObject()的时候产生一个随机数，mod到[1, totWeight]这个区间然后就iterate the current elements in the map。在setWeight()的时候注意维护totWeight。

不对吧..这个怎么保证概率啊...

两个objective的weight不相同的时候, 抽出的概率应该也不想同, 所以应该 是mod到[1,currentitem's weight/ totalweight] ?

readman 发表于 2016-5-17 13:13
不对吧..这个怎么保证概率啊...

两个objective的weight不相同的时候, 抽出的概率应该也不想同, 所以 ...

我的意思其实就是产生一个[1, totWeight]的随机数然后去统计cumulative partial sum.

最近是出新题目了吗？。。。

getRandom这个题就是这个算法吧？
http://stackoverflow.com/questions/1761626/weighted-random-numbers

请问店面的算法题 是在 Code Pair 上写吗？ 我收到了店面通知， 说是用hackerrank's Code pair , 不知道是不是全程算法题   

谢谢楼主分享。。