面经总结
http://massivealgorithms.blogspot.com/2015/12/algorithm-interview-misc-part-2.html
面经总结（偏向Facebook)
https://shawnlincoding.wordpress.com/category/%E9%9D%A2%E7%BB%8F/
面经
http://yuanhsh.iteye.com/category/330853
博客分类： Technical InterviewsMathFacebook
给你一个array，返回array里面最大数字的index，但是必须是最大数字里面随机的一个index。比如[2,1,2,1,5,4,5,5]必须返回[4,6,7]中的随机的一个数字，要求O(1)space。
出现过很多次的FB的题，naive的做法是先扫一遍，找出最大值和最大值的个数。然后从头再扫一遍即可。
用Reservoir Sampling思路做，one pass就可以了。
代码：
Cpp代码 收藏代码
int random_max(const vector<int>& nums) {
int ret = 0, count = 0, max = INT\_MIN;
for\(int i = 0; i < nums.size\(\); ++i\) {
if\(nums\[i\] > max\) {
max = nums\[i\];
count = 1;
ret = i;
} else if\(nums\[i\] == max\) {
if \(\(rand\(\) % ++count\) == 0\) ret = i;
}
}
return ret;
}
From: http://www.fgdsb.com/2015/01/15/random-maximum/
这里有更多关于Reservior Sampling的面试题：