Faceboook FB 臉書 面經 screening interview phone interview

剛面完臉書的screening interview 跟大家分享一下

自我介紹完之後就直接開始coding了

----------------------------------------

第一題：Given an array of integers, return a random index of the maximum number in that array.

Follow up: Can you make it more efficient?

Answer: We can improve space complexity to constant
--

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

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

3. Return a random index of the previous one.

补充内容 (2021-2-4 09:56):
Typo again
1st example:
[4,3,2,1,5,5,5,5,6,6,6] randomly return 8,9, or 10(indices of 6)

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

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. }

复制代码

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

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

不是leetcode的题啊？第一题没看懂啊

谢谢楼主。不太明白第一题。是要return给定数组里任意的最大数的index吗？这个数组的最大数不止一个？

tkh08001 发表于 2021-2-3 12:13
第一题是不是可以存arrayList，存最大值的list，如果有比第一个index 更大的就new 一个新的，把新最大值ind ...

第二题sequence的意思应该是这些web pages 都需要连着出现，不能跳过中间的web pages。

第一题是力扣散舅罢的变形吗

tkh08001 发表于 2021-2-3 12:13
第一题是不是可以存arrayList，存最大值的list，如果有比第一个index 更大的就new 一个新的，把新最大值ind ...

要連續 我有typo

billyRandom 发表于 2021-2-3 13:43
谢谢楼主。不太明白第一题。是要return给定数组里任意的最大数的index吗？这个数组的最大数不止一个？

沒錯 最大數可能有好幾個 隨機return

cony0123 发表于 2021-2-3 14:30
沒錯 最大數可能有好幾個 隨機return

给出的数字是已排序的吗？

请问这里是不是typo？
“[1,2,3,4,5,5,5,5,6,6,6] randomly return 4,5,6, or 7(indices of 5)”
6 是max 所以应该random return 8,9,10 三个任意一个吧？