一亩三分地论坛

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

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

Two Sigma一轮电面面经

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

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

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

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

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.. From 1point 3acres bbs
  • 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? 我主要说了merge sortstable sort而且可以比较方便的去sort linked list或者是用k-way merge sortsort external     files, quick sortin place sort,比较快。
  • Design patterns?     What is your definition of design pattern? Give me some examples? 我答了singleton, factory     pattern以及MVC,并且补充说MVC应该是high-levelarchitecture     design pattern
  • Differences     between threads and processes and how to communicate? 我主要说了threadshared same     process and same memory space, low overhead; processseparate memory     spaces, high overhead. Process通信可以用file, socket, pipe等等, thread通信就用shared memory     variable.
  • What is throughput? What is     latency? What are their relationships?
Latency is the time involved to complete any sort of process.Throughput is the amount of information a system can process within a giventime period (actual rate that the information is transferred). Latency andthroughput are not necessarily correlated, because of data density. A systemthat has high latency but can transfer a huge amount of data can still havehigher throughput than a low-latency system.

然后他说我们来coding的时候我以为是要Reverse Polish Notation呢…结果给了个其他的题目,让设计一个datastructure,这个data structure里面存的是object和它对应的weight。
要求支持这两种操作:

  • getRandomObject()     - 返回一个random object,概率等于(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.
    . From 1point 3acres bbs

我就直接map<int,int>的实现了一个,同时维护了一个totWeight。在getRandomObject()的时候产生一个随机数,mod到[1, totWeight]这个区间然后就iterate the current elements in the map。在setWeight()的时候注意维护totWeight。
. visit 1point3acres.com for more.
面完之后我觉得这个题目其实是可以改造一下问很多follow-up question的,首先对于samplingfrom a discrete distribution我强烈推荐这个网页: http://www.keithschwarz.com/darts-dice-coins/
里面详细的讨论了很多变种以及非常重要的alias method。其次,对于刚才我们的naive的做法,每次sample是O(n)的但是setWeight是O(1)的,一个更好的做法应该可以把整体的复杂度优化到O(logn) - 这个还要再细细的想一想。

评分

1

查看全部评分

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。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. visit 1point3acres.com for more.
不对吧..这个怎么保证概率啊...

两个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
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 05:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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