回复: 9
跳转到指定楼层
上一主题 下一主题
收起左侧

Two Sigma一轮电面面经

全局:

2016(1-3月) 码农类General 博士 全职@twosigma - 猎头 - 技术电面  | | Pass | 在职跳槽

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
一开始面试官还是介绍了一下自己的工作,然后问我的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 heapsolution,然后补充说如果内存不够存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) - 这个还要再细细的想一想。

评分

参与人数 1大米 +1 收起 理由
kradnangel + 1 感谢分享!

查看全部评分


上一篇:Radix Trading电面跪经
下一篇:Two Sigma Onsite面经

本帖被以下淘专辑推荐:

🔗
aojing 2016-5-17 11:17:50 | 只看该作者
全局:
赞,祝lz好运。。。
回复

使用道具 举报

🔗
houqingniao 2016-5-17 12:31:32 | 只看该作者
全局:
bless lz. 请问 在getRandomObject()的时候产生一个随机数,mod到[1, totWeight]这个区间然后就iterate the current elements in the map, 这个啥意思?
回复

使用道具 举报

🔗
houqingniao 2016-5-17 12:31:49 | 只看该作者
全局:
bless lz. 请问 在getRandomObject()的时候产生一个随机数,mod到[1, totWeight]这个区间然后就iterate the current elements in the map, 这个啥意思?
回复

使用道具 举报

🔗
readman 2016-5-17 13:13:53 | 只看该作者
全局:
我就直接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] ?
回复

使用道具 举报

🔗
 楼主| diyutianshi 2016-5-17 13:16:41 | 只看该作者
全局:
readman 发表于 2016-5-17 13:13
不对吧..这个怎么保证概率啊...

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

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

使用道具 举报

🔗
Yoyo00 2016-5-30 14:20:28 | 只看该作者
全局:
最近是出新题目了吗?。。。
回复

使用道具 举报

🔗
feichangh 2016-8-31 10:37:47 | 只看该作者
全局:
getRandom这个题就是这个算法吧?
http://stackoverflow.com/questions/1761626/weighted-random-numbers
回复

使用道具 举报

🔗
maxiaoyao 2018-7-19 08:23:44 | 只看该作者
全局:
请问店面的算法题 是在 Code Pair 上写吗? 我收到了店面通知, 说是用hackerrank's Code pair , 不知道是不是全程算法题   
回复

使用道具 举报

🔗
better1016 2018-10-3 03:57:01 | 只看该作者
全局:
谢谢楼主分享。。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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