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

楼主最近参加了Uber的电话面试，题目是：让设计一个数据结构，要求可以存储Object-Weight Pair，实现如下几个接口：1） Update；2） Insert；3） Remove；4） GetRandom. 第四个方法是实

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

算，有没有更好的方法来解决此题？貌似面试官一直在提normalization 和Denormalization。不能理解面试官要的是什么？

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

paca 发表于 2016-8-5 13:57
这个题目面试官说的是流，我想应该是无限的，不应该是固定容量的。

尝试写了一个segment tree+unordered_map+queue的，发现其实每个函数比想像的短...

class weighted_reservior {
public:
    weighted_reservior() : M(4), tree(M*2, 0) {
        for (int k = 1; k < M; ++k) loc.push(k); //free spot from 1 to M-1
    }


       
    void add(const string &str, int w) {
        if (loc.empty()) resize();
        int i = loc.front();
        loc.pop();
        update_leaf(i, w);
        idx_to_obj[i] = str;
        obj_to_idx[str] = i;
    }


       
    void update(const string &str, int w) {
        int i = obj_to_idx[str];
        update_leaf(i, w-tree[M+i]);
    }


       
    void remove(const string &str) {
        int i = obj_to_idx[str];
        loc.push(i);
        update_leaf(i, -tree[M+i]);
        idx_to_obj.erase(i);
        obj_to_idx.erase(str);
    }

    string get_random() {
        int key = (rand())%tree[1];
        int i = sum_search(key+1);
        return idx_to_obj[i];
    }

private:
    void resize() {
        tree.resize(M*4, 0);
        for (int base = M; base; base >>= 1) //move current nodes to new locations
            rotate(tree.begin()+base, tree.begin()+base*2, tree.begin()+base*3);
        tree[1]=tree[2]; //new root
        for (int k = M; k < M*2; ++k) loc.push(k);
        M<<=1;
    }


       
    int sum_search(int w) {
         int i = 1;
         do {
             i <<= 1;
             if (w > tree[i]) w -= tree[i++];
         } while (i < M);
         return i-M;
     }

    void update_leaf(int i, int diff) {
        for (int key = M+i; key > 0; key >>= 1) tree[key] += diff;
    }

private:
    int M; //smallest power of 2 greater or equal than nums.size()+2
     vector<int> tree;  //tree stored in array, size is M*2
    queue<int> loc;  //free spots
    unordered_map<int, string> idx_to_obj;
    unordered_map<string, int> obj_to_idx;
};







补充内容 (2016-8-5 22:02):
不知道为啥排版出来这么诡异...凑合着看吧...顺便求问这个论坛怎么贴代码...

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
要是不嫌麻烦自己写一个二叉树也可以的。

我有个想法，是不是可以用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)应该有希望。

arraylist ＋ hashmap就可以了

树状数组吧

感觉楼主面entry level这样就行感兴趣我觉得他考察的是 consistent hashing. demoralization 就是在不同类里面加上virtual node的信息这样就可以达到一个变了所有的其它类内容也变

HashMap+Queue+BIT可以做,HashMap<Object,int>存对象在BIT中的index.Queue用来回收被删除的idx,进行下次再分配.BIT用来做Random,可以用二分查找枚举目标idx.这样四种操作就都O(logN)了.

xihaokai1 发表于 2016-8-3 14:06
我有个想法，是不是可以用HashMap存Object->DoubleLinkedList。 前三个都轻松实现。 GetRandom可以这样来： ...

能讲讲这个DoubleLinkedList用来存什么吗？Weight应该就是一个Integer，能不能再细讲一下。

所以说这是uber还是2sigma

Neil_Acton 发表于 2016-8-4 04:17
所以说这是uber还是2sigma

是Two Sigma

感谢分享，留名关注下。