森鲜的脸家店面

刚刚面完一分钟来发帖，面试的是一位非常和善的白人大爷，眼神很犀利，看得出来是有水平的。


题目：

1. 设计一个数据结构，两个method： 1.insert 2.popRandom。随机弹出的概率是平均的。
    例子： insert(3) insert(3) insert(5) insert(8), popRandom-> (3: 50%, 5: 25%

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

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

一遍过 + bugfree + optimal，大爷回答并不是。只有那种显而易见的bug + 乱七八糟的算法 + 特别不optimal 才是red flag。希望大家不要太有压力，面试加油：）。

follow up 1， c++的话用一个unordered_map和一个数组存unordered_map的iterator，这样insert和popRandom都可以O(1)

1. //original
   
2. vector<int> nums;
   
3. 
   
4. void insert(int num)
   
5. {
   
6.     nums.push_back(num);
   
7. }
   
8. 
   
9. void popRandom()
   
10. {
    
11.     int n = nums.size();
    
12. 
    
13.     int i = rand() % n;
    
14.     nums[i] = nums.back();
    
15.     nums.pop_back();
    
16. }
    
17. 
    
18. //follow up 1
    
19. #define It unordered_map<int, int>::iterator
    
20. unordered_map<int, int> maps; //{num, freq}
    
21. vector<It> it_array;
    
22. 
    
23. void insert_followup_1(int num)
    
24. {
    
25.     It it = maps.find(num);
    
26. 
    
27.     if (it == maps.end()) {
    
28.         maps[num] = 1;
    
29.         it = maps.find(num);
    
30.         it_array.push_back(it);
    
31.     } else {
    
32.         it->second++;
    
33.     }   
    
34. }
    
35. 
    
36. void popRandom_followup_1()
    
37. {
    
38.     int n = maps.size();
    
39.     int i = rand() % n;
    
40. 
    
41.     It it = it_array[i];
    
42.     if (--it->second == 0) {
    
43.         maps.erase(it);
    
44.         it_array[i] = it_array.back();
    
45.         it_array.pop_back();
    
46.     }   
    
47. }

复制代码

您好！
本帖隐藏的内容需要积分高于 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

前两问是array+map？不是很懂ranged tree怎么用。。。

shabishabi 发表于 2021-2-25 11:30
前两问是array+map？不是很懂ranged tree怎么用。。。

对，array+map。我没刷到这个题，一会儿去看看先。

zifanzzz 发表于 2021-2-25 12:42
对，array+map。我没刷到这个题，一会儿去看看先。

请问为什么是array？pop完了之后再shift么？

glad2mu 发表于 2021-2-25 13:46
请问为什么是array？pop完了之后再shift么？

pop完把最后一个塞到空位里。

zifanzzz 发表于 2021-2-25 13:49
pop完把最后一个塞到空位里。

哦明白了。谢谢解答！zszszs

第三个follow up 好像是莉蔻舞而把。楼主知道用ranged binary tree怎么做吗？

多谢分享

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

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