二sigma新鲜电面挂经

0 － 15 分钟
    自我介绍，实习经历，为什么要来这公司， BQ 最难的经历是什么
15 － 20 分钟
    挺奇怪的， 还没开始考技术贴面试官就让问他问题了
20 － 35 分钟
    和地里的一模一样
    什么是hash table（这个问的很细， 要知道怎么rem

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

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

的办法;(

去年和G面也挂在和这个差不多的题上，今年又挂在这题上。 认了。 求大米



补充内容 (2017-11-8 07:11):
大家可以想到怎么样更快吗

1. class Solution {
   
2. private:
   
3.     unordered_map<float, unordered_set<int>>  weightdict;
   
4.     unordered_map<int, float> keydict;
   
5. public:
   
6.     void set(int key, float weight) {
   
7.         if (keydict.find(key) != keydict.end()) {
   
8.             int oldw = keydict[key];
   
9.             weightdict[oldw].erase(key);
   
10.         }
    
11.         keydict[key] = weight;
    
12.         weightdict[weight].insert(key);
    
13.     }
    
14.     float next(float weight){
    
15.         auto s = weightdict[weight]
    
16.         int index = rand() % s.size();
    
17.         return *next(s.beding(), index);
    
18.     }
    
19. }

复制代码

没太明白这个next函数干嘛的 所以是没有参数的么 那么返回的是那个weight对应的随机key

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

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

用segment tree，set和next都是lgn

blitz512 发表于 2017-11-8 08:30
用segment tree，set和next都是lgn

可以给个具体的做法吗？要update的时候感觉所有的node都要update， 不然随机输出的数可能不会被interval里？

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

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

arthes 发表于 2017-11-8 15:35
但是update的时候如果更新了某一个已有元素的weight的话tree里存的sum不是会变么？这是不是还是要更新所 ...

只影响root到leaf这条path啊 所以是lgn

blitz512 发表于 2017-11-8 16:10
只影响root到leaf这条path啊 所以是lgn

你能解釋一下嗎？how to use segment tree for this?

想请教一下这个weighted random sampling with replacement, 是不是每次运行都会得出不一样的答案，还是每次运行都一样啊？