Nuro 店面面经

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

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

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

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

如果只是要求sample的复杂度为O(logn)的话用线段树是可以（不好意思这里的n是楼主的k）

1. class SamplingSegmentTree {
   
2. public:
   
3.     SamplingSegmentTree(const vector<int>& weights) {
   
4.         num_elements_ = weights.size();
   
5.         weight_nodes_.resize(4 * num_elements_);
   
6.         Construct(weights, 0, num_elements_ - 1, 0);
   
7.     }
   
8.    
   
9.     int Sample() {
   
10.         int target_weight = rand() % weight_nodes_[0];
    
11.         int selected = -1;
    
12.         Sample(0, num_elements_ - 1, 0, target_weight, selected);
    
13.         return selected;
    
14.     }
    
15.    
    
16. private:
    
17.     size_t num_elements_;
    
18.     vector<int> weight_nodes_;
    
19.    
    
20.     void Construct(const vector<int>& weights, int wl, int wr, int t) {
    
21.         if (wl > wr) return;
    
22.         if (wl == wr) {
    
23.             weight_nodes_[t] = weights[wl];
    
24.         } else {
    
25.             int tl = 2 * t + 1;
    
26.             int tr = 2 * t + 2;
    
27.             int wm = wl + (wr - wl) / 2;
    
28.             Construct(weights, wl, wm, tl);
    
29.             Construct(weights, wm + 1, wr, tr);
    
30.             weight_nodes_[t] = weight_nodes_[tl] + weight_nodes_[tr];
    
31.         }
    
32.     }
    
33.    
    
34.     void Sample(int wl, int wr, int t, int& target_weight, int& selected) {
    
35.         if (selected != -1) return;
    
36.         if (wl > wr) return;
    
37.         if (wl == wr) {
    
38.             target_weight -= weight_nodes_[t];
    
39.             if (target_weight < 0) {
    
40.                 selected = wl;
    
41.                 weight_nodes_[t] = 0;
    
42.             }
    
43.         } else {
    
44.             int tl = 2 * t + 1;
    
45.             int tr = 2 * t + 2;
    
46.             int wm = wl + (wr - wl) / 2;
    
47.             Sample(wl, wm, tl, target_weight, selected);
    
48.             Sample(wm + 1, wr, tr, target_weight, selected);
    
49.             weight_nodes_[t] = weight_nodes_[tl] + weight_nodes_[tr];
    
50.         }
    
51.     }
    
52. };
    
53. 
    
54. int main() {
    
55.     map<string, int> distribution;
    
56.     for (int i = 0; i < 100000; ++i) {
    
57.         SamplingSegmentTree sst({1,1,1,1,1});
    
58.         vector<int> sample;
    
59.         for (int j = 0; j < 3; ++j) {
    
60.             sample.push_back(sst.Sample());
    
61.         }
    
62.         sort(sample.begin(), sample.end());
    
63.         string key;
    
64.         for (int s: sample) key += to_string(s) + " ";
    
65.         ++distribution[key];
    
66.     }
    
67.     for (auto& entry : distribution) {
    
68.         cout << entry.first << ": " << entry.second << endl;
    
69.     }
    
70. }

复制代码

输出结果：

1. 0 1 2 : 10063
   
2. 0 1 3 : 10054
   
3. 0 1 4 : 10092
   
4. 0 2 3 : 9803
   
5. 0 2 4 : 10025
   
6. 0 3 4 : 10018
   
7. 1 2 3 : 9945
   
8. 1 2 4 : 9944
   
9. 1 3 4 : 9964
   
10. 2 3 4 : 10092

复制代码

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

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

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

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