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

此题考查augmented data structure。你可以任选balanced binary search tree，每个node保存self和所有child nodes的weight的和，另外存一下所有node的和。getRandom每次生成随机数，然后再找相应的child node。这样实现所有operation皆是O(lgN)。

paca 发表于 2016-8-4 01:24
能讲讲这个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。

你可以看到在这些线段里找4其实可以用binary search， 所以之前我相信log(n)可以实现，第一感觉是用indexed binary tree可是我对这个数据结构不是很熟。。。不过直觉告诉我可以实现。tradeoff就是其他方法可能也得O(logn)了。

xihaokai1 发表于 2016-8-4 21:17
就是一个双向的链表，每个node存前一个node，后一个node, 还有weight。
你把每个weight想成一个线段,用 ...

这样只能靠binary indexed tree才能O(logN)，remove也会非常复杂，这题就是用augmented tree。

lz你这个数据结构有最大容量吗？还是可以一直insert的...

getRandom 难道不是linkedlist reservior sampling 问题么

跟这个类似吧
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)去寻找在哪个区间

hxtang 发表于 2016-8-5 06:42
lz你这个数据结构有最大容量吗？还是可以一直insert的...

这个题目面试官说的是流，我想应该是无限的，不应该是固定容量的。

blackrose 发表于 2016-8-5 06:59
getRandom 难道不是linkedlist reservior sampling 问题么

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

xihaokai1 发表于 2016-8-4 21:17
就是一个双向的链表，每个node存前一个node，后一个node, 还有weight。
你把每个weight想成一个线段,用 ...

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