回复: 50
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:

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

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
楼主最近参加了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。不能理解面试官要的是什么?

上一篇:这个月底indeed Tokyo onsite 有木有最近onsite求经验
下一篇:twitter面经
推荐
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大米 +5 收起 理由
atlas1017 + 5 没想到这个解法 厉害厉害!

查看全部评分

回复

使用道具 举报

推荐
hxtang 2016-8-5 22:01:53 | 只看该作者
全局:
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):
不知道为啥排版出来这么诡异...凑合着看吧...顺便求问这个论坛怎么贴代码...
回复

使用道具 举报

推荐
hxtang 2016-8-23 04:52:16 | 只看该作者
全局:
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
要是不嫌麻烦自己写一个二叉树也可以的。

回复

使用道具 举报

🔗
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可以这样来: ...

能讲讲这个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 | 只看该作者
全局:
感谢分享,留名关注下。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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