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

maihuabu 发表于 2016-8-4 14:16
此题考查augmented data structure。你可以任选balanced binary search tree，每个node保存self和所有child ...

赶紧去学一下你说的这个Augment Data Structure。 麻烦你看一下下面这个链接里的内容是不是你说的那个考点？http://ocw.mit.edu/courses/elect ... val-trees/lec11.pdf

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):
不知道为啥排版出来这么诡异...凑合着看吧...顺便求问这个论坛怎么贴代码...

paca 发表于 2016-8-5 14:04
赶紧去学一下你说的这个Augment Data Structure。 麻烦你看一下下面这个链接里的内容是不是你说的那个考 ...

就是这个，书里可能讲的更详细些。

这面试官是UCSD的吗?
我被问到了同样的问题. 很快给了所有operation都是O(log n)的方法. 但是他觉得不够好.

后来发现有O(1) expectation的方法.(要用real RAM)  https://people.mpi-inf.mpg.de/~mehlhorn/ftp/DiscreteRandomVariates.pdf

谢谢分享

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

很好的想法，但是想请问一下，按照你这种应该就不用HashMap了是吧

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

感谢提供，但是还想请问，既然已经使用了doubly linkedlist来存储object及其对应的weight，hashMap还有必要吗，是不是只需要在这个doubly linkedlist操作就ok了；
  如果还需要hashMap，那在linkedlist里面每个node除了保存weight还有存什么其他东西？

jiaozhu200601 发表于 2016-8-15 01:54
感谢提供，但是还想请问，既然已经使用了doubly linkedlist来存储object及其对应的weight，hashMap还有必 ...

Map 存object->node呀。

蓄水池抽样解决getramdom.. 肯定可行但是复杂度就是O（n）。 BIT我有点看不懂。。我也快面two sigma了

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

reservoir 可以直接处理remove操作吗？