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

xihaokai1 发表于 2016-8-18 22:36
Map 存object->node呀。

请问为什么需要一个Node，感觉直接 Map<Object, Weight>也可以直接实现了，同时注意维持一个totalweight 的global variable。

mgccl 发表于 2016-8-7 04:24
这面试官是UCSD的吗?
我被问到了同样的问题. 很快给了所有operation都是O(log n)的方法. 但是他觉得不够好 ...

那面试官也太mean了  这种log n 的解法， 统计博士都不一定知道。 你说很快给了所有log n的解法，你都实现了么， 还是就是描述一下？

maihuabu 发表于 2016-8-5 23:48
就是这个，书里可能讲的更详细些。

能说下 segment tree 怎么实现么。
每个Leaf node里村什么？ 每个node记录的辅助变量又是什么呢？

我想了几种情况 都没有很好的能够实现 random sample的。

hxtang 发表于 2016-8-5 22:01
尝试写了一个segment tree+unordered_map+queue的，发现其实每个函数比想像的短...

class weighted_re ...

你好。能不能解释下  每个Leaf node里存什么？ 整体的思路是什么？

segment tree 如何初始化？

Neil_Acton 发表于 2016-8-23 03:34
你好。能不能解释下  每个Leaf node里存什么？ 整体的思路是什么？

segment tree 如何初始化？

整体的思路就是搞一个weight数组，weight[k]不为0就表示index k已经allocate给某个object了，为0就表示index k还没有被allocate。另外维护index到object之间的两个方向的mapping，以及一个队列loc表示有哪些位置还没有被allocate。
所以要add就是从queue里面取一个index出来，把相应的weight设为要add的weight，更新index-object之间的mapping。update，remove之类的实现也挺trivial的就不说了。
random sample的做法是sample 一个[0, sum of weight]之间的数w，然后找weight数组prefix sum里第一个>=w的数。


这个问题的难点是random sample里找prefix sum的lower_bound，trivial的做法是线性的。为了让这个search比较快，所以我们把weights存在一棵线段树的leaf node里。非叶结点存它子结点的和。
比如weight数组长度为4，leaf node存的weights是w1, w2, w3, w4。
那么树的结构就是
                      (w1+w2+w3+w4)
                         /                   \
                  (w1+w2)          (w3+w4)
                  /        \              /       \
                 w1      w2         w3       w4
这样sample的时候可以用binary search找到w对应的node，比如你要搜w=w1+w2+w3，在根结点看到w1+w2，所以转向root->right，搜w3的lower_bound，这样就locate到第三个叶子结点。
add/delete/update的时候相应地改变leaf node和它到root路径上的nodes就可以了。

另外因为只要memory允许，可以一直加入object。为了解决这个问题所以树的大小要可以动态增加（就是把现在的树变成新树的root->left，root->left存一个全0的完全二叉树）。我的做法是类似于vector resize的做法。初始化的时候我假设树有4个node，之后每次所有nodes都被allocate出去时，我就把node的数量＊2，相应地loc里需要增加未被allocate的元素。这个操作实现是线性的，但是只有全部index都allocate完才被执行，所以amortized cost是O(1)

具体树的存法我用的是ZKW线段树，具体看下面这个slides（前35页就基本够了）。
http://wenku.baidu.com/view/0c1bbba40029bd64783e2cca.html
要是不嫌麻烦自己写一个二叉树也可以的。

Neil_Acton 发表于 2016-8-23 03:31
能说下 segment tree 怎么实现么。
每个Leaf node里村什么？ 每个node记录的辅助变量又是什么呢？

面试的话我会写treap，AVL和RB Tree都太繁琐了，时间不够。

hxtang 发表于 2016-8-23 04:52
整体的思路就是搞一个weight数组，weight[k]不为0就表示index k已经allocate给某个object了，为0就表示in ...

十分感谢！
你这个解释很好。
这就是一个segment tree， 每个node 存的是 某一段区间的sum， 对于Leaf， 自然这一段长度就是1， 也就是存本身的weight。
所以说 Leaf的个数等于一共insert了多少次
delete对树的影响和update是同理的， 当成update为0 即可。

jiaozhu200601 发表于 2016-8-22 03:24
请问为什么需要一个Node，感觉直接 Map也可以直接实现了，同时注意维持一个totalweight 的global variabl ...

因为方便remove呀。

我考了类似的题目。 给了order(n)的思路后。 面试官说不错 就直接实现了。然后也没有follow up要 log(n)solution   就说实现不错 就聊别的了

Fenwick tree居然还有人考，丧心病狂。。。