一亩三分地论坛

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

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

求问Two Sigma店面一题如何解?

[复制链接] |试试Instant~ |关注本帖
paca 发表于 2016-8-3 12:00:10 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@TwoSigma - 内推 - 技术电面 |Other在职跳槽

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

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

x
楼主最近参加了Uber的电话面试,题目是:让设计一个数据结构,要求可以存储Object-Weight Pair,实现如下几个接口:1) Update;2) Insert;3) Remove;4) GetRandom. 第四个方法是实现的重点。这个GetRandom的方法是随机地返回一个Object,要求概率满足:此object的weight / 所有weight的和。 楼主想的是HashMap的Key存Object,Value存weight,这样可以轻松实现Update,Insert和remove的功能。至于GetRandom这个方法,楼主是用了一个辅助的Array,用来表明每个Object对应的区间,然后用随机数获得某个index,最后看看这个index在哪个区间,然后就返回该对象。但是缺点是:每每更新,插入或者remove掉某个object的时候,这个辅助的array都要重新计算,有没有更好的方法来解决此题?貌似面试官一直在提normalization 和Denormalization。不能理解面试官要的是什么?
maihuabu 发表于 2016-8-4 14:16:13 | 显示全部楼层
此题考查augmented data structure。你可以任选balanced binary search tree,每个node保存self和所有child nodes的weight的和,另外存一下所有node的和。getRandom每次生成随机数,然后再找相应的child node。这样实现所有operation皆是O(lgN)。

评分

1

查看全部评分

回复 支持 4 反对 0

使用道具 举报

xihaokai1 发表于 2016-8-3 14:06:26 | 显示全部楼层
我有个想法,是不是可以用HashMap存Object->DoubleLinkedList。 前三个都轻松实现。 GetRandom可以这样来:先从0到1随机一个数r(JAVA怎么实现?是random().nextDouble()?), 然后做denormalization: r = r*total_weight, 然后node从链表的头开始走, 每次都r= r-node.weight 直到r为负,那node.object就是我们要的那个object。 这个过程要O(n), 不知道怎么做O(1), 感觉O(logn)应该有希望。
回复 支持 反对

使用道具 举报

iamstone 发表于 2016-8-3 15:40:33 | 显示全部楼层
arraylist + hashmap就可以了
回复 支持 反对

使用道具 举报

zeyuanxy 发表于 2016-8-3 22:30:49 | 显示全部楼层
树状数组吧
回复 支持 反对

使用道具 举报

kevinsun 发表于 2016-8-4 00:09:03 | 显示全部楼层
感觉楼主面entry level这样就行感兴趣我觉得他考察的是 consistent hashing. demoralization 就是在不同类里面加上virtual node的信息这样就可以达到一个变了所有的其它类内容也变
回复 支持 反对

使用道具 举报

dydcfg 发表于 2016-8-4 01:03:48 | 显示全部楼层
HashMap+Queue+BIT可以做,HashMap<Object,int>存对象在BIT中的index.Queue用来回收被删除的idx,进行下次再分配.BIT用来做Random,可以用二分查找枚举目标idx.这样四种操作就都O(logN)了.
回复 支持 反对

使用道具 举报

 楼主| paca 发表于 2016-8-4 01:24:39 | 显示全部楼层
xihaokai1 发表于 2016-8-3 14:06
我有个想法,是不是可以用HashMap存Object->DoubleLinkedList。 前三个都轻松实现。 GetRandom可以这样来: ...

. from: 1point3acres.com/bbs 能讲讲这个DoubleLinkedList用来存什么吗?Weight应该就是一个Integer,能不能再细讲一下。
回复 支持 反对

使用道具 举报

Neil_Acton 发表于 2016-8-4 04:17:28 | 显示全部楼层
所以说这是uber还是2sigma
回复 支持 反对

使用道具 举报

 楼主| paca 发表于 2016-8-4 06:35:15 | 显示全部楼层
Neil_Acton 发表于 2016-8-4 04:17.鐣欏璁哄潧-涓浜-涓夊垎鍦
所以说这是uber还是2sigma

是Two Sigma
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-8-4 12:52:11 | 显示全部楼层
感谢分享,留名关注下。
回复 支持 反对

使用道具 举报

xihaokai1 发表于 2016-8-4 21:17:55 | 显示全部楼层
paca 发表于 2016-8-4 01:24.鏈枃鍘熷垱鑷1point3acres璁哄潧
能讲讲这个DoubleLinkedList用来存什么吗?Weight应该就是一个Integer,能不能再细讲一下。

就是一个双向的链表,每个node存前一个node,后一个node, 还有weight。
你把每个weight想成一个线段,用链表就相当于说每次加入新的weight或者更新/移除老的weight的时候所有的线段还是连续接在一起的,方便我们getrandom。

比如现在我们有个链表,里面的weight是1,5,2,3,9(总20, 概率分布可以想像成[0,1),[1,6),[6,8),[8,11),[11,20))。 我们从0-1产生个随机数,假设是0.2,那相当于1-20里面掷到了20*0.2=4, 也就是说在0-20的线段里落在了20*0.2=4这个点,那按我之前的算法,先4-1=3, 然后3-5=-2比0小了所以到第二个node就停了。的确,4是在[1,6)这个线段里,也就对应第二个node。. from: 1point3acres.com/bbs
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
你可以看到在这些线段里找4其实可以用binary search, 所以之前我相信log(n)可以实现,第一感觉是用indexed binary tree可是我对这个数据结构不是很熟。。。不过直觉告诉我可以实现。tradeoff就是其他方法可能也得O(logn)了。
回复 支持 反对

使用道具 举报

maihuabu 发表于 2016-8-5 06:21:06 | 显示全部楼层
xihaokai1 发表于 2016-8-4 21:17
就是一个双向的链表,每个node存前一个node,后一个node, 还有weight。
你把每个weight想成一个线段,用 ...

这样只能靠binary indexed tree才能O(logN),remove也会非常复杂,这题就是用augmented tree。
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-8-5 06:42:52 | 显示全部楼层
lz你这个数据结构有最大容量吗?还是可以一直insert的...
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-8-5 06:59:56 | 显示全部楼层
getRandom 难道不是linkedlist reservior sampling 问题么
回复 支持 反对

使用道具 举报

haoshenxiong 发表于 2016-8-5 13:39:28 | 显示全部楼层
跟这个类似吧
http://stackoverflow.com/questions/5682218/data-structure-insert-remove-contains-get-random-element-all-at-o1

remove的时候把数组末尾的object和要remove的object对调,insert的时候直接插入队尾,update总的weight和,只有getRandom的时候需要O(n)去寻找在哪个区间
回复 支持 反对

使用道具 举报

 楼主| paca 发表于 2016-8-5 13:57:06 | 显示全部楼层
hxtang 发表于 2016-8-5 06:42
lz你这个数据结构有最大容量吗?还是可以一直insert的...
. visit 1point3acres.com for more.
这个题目面试官说的是流,我想应该是无限的,不应该是固定容量的。
回复 支持 反对

使用道具 举报

 楼主| paca 发表于 2016-8-5 13:59:11 | 显示全部楼层
blackrose 发表于 2016-8-5 06:59
getRandom 难道不是linkedlist reservior sampling 问题么

可能我理解Reservior Sampling理解的不深。如果weight 都是1, 就是没有weight的话,对于流来说,随机产生应该是用这个方法。能说说如果有weight的话,如何应用?
回复 支持 反对

使用道具 举报

 楼主| paca 发表于 2016-8-5 14:01:50 | 显示全部楼层
xihaokai1 发表于 2016-8-4 21:17.1point3acres缃
就是一个双向的链表,每个node存前一个node,后一个node, 还有weight。.1point3acres缃
你把每个weight想成一个线段,用 ...

谢谢你的解释,我想概率那块我当时也是这么跟面试官说的,就是看区间。但是你用DDL貌似比我的那个HashMap好点。我估计面试官想要的是O(logn)
回复 支持 反对

使用道具 举报

 楼主| paca 发表于 2016-8-5 14:04:35 | 显示全部楼层
maihuabu 发表于 2016-8-4 14:16
此题考查augmented data structure。你可以任选balanced binary search tree,每个node保存self和所有child ...

. Waral 鍗氬鏈夋洿澶氭枃绔,赶紧去学一下你说的这个Augment Data Structure。 麻烦你看一下下面这个链接里的内容是不是你说的那个考点?http://ocw.mit.edu/courses/elect ... val-trees/lec11.pdf
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 19:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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