Faceboook FB 臉書 面經 screening interview phone interview

第一题 遍历加reservoir sampling. 时间O(n), Space O(1)?

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

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

这是e4吗？

thank you for your sharing.

litJordan 发表于 2021-2-3 16:41
请问这里是不是typo？
“[1,2,3,4,5,5,5,5,6,6,6] randomly return 4,5,6, or 7(indices of 5)”
6 是max ...

you are right

第一题应该是最终使用reservoir sampling吧，跟踪当前最大值和他的count，如果有遇到更大的就更新， 重置count， 否则就生成随机数Rand.nextInt(count)看是不是0。

hackenkreuz 发表于 2021-2-15 02:10
第一题应该是最终使用reservoir sampling吧，跟踪当前最大值和他的count，如果有遇到更大的就更新， 重置co ...

写一个，reservoir sampling的确很简洁

1. int random_index_of_max_num(vector<int> &nums)
   
2. {
   
3.     int n = nums.size();
   
4.     int max_num = nums[0];
   
5.     int index = 0;
   
6.     int count = 1;
   
7. 
   
8.     for (int i = 1; i < n; i++) {
   
9.         if (nums[i] > max_num) {
   
10.             max_num = nums[i];
    
11.             index = i;
    
12.             count = 1;
    
13.         } else if (nums[i] == max_num) {
    
14.             int idx = rand() % ++count;
    
15.             if (idx == 0)
    
16.                 index = i;
    
17.         }   
    
18.     }   
    
19. 
    
20.     return index;
    
21. }
    
22. 
    
23. int main()
    
24. {
    
25.     vector<int> nums = {1, 9, 2, 3, 9, 8, 9};
    
26.     cout << random_index_of_max_num(nums) << endl;
    
27.     return 0;
    
28. }

复制代码

这么简单的一题都没表达清楚，后面解释也是乱一团。我是面官，肯定拒，招进来影响别人工作