Random Maximum | tech::interview

Random Maximum | tech::interview
给你一个array，返回array里面最大数字的index，但是必须是最大数字里面随机的一个index。比如[2,1,2,1,5,4,5,5]必须返回[4,6,7]中的随机的一个数字，要求O(1)space。

出现过很多次的FB的题，naive的做法是先扫一遍，找出最大值和最大值的个数。然后从头再扫一遍即可。

用Reservoir Sampling思路做，one pass就可以了。

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;

}
http://yuanhsh.iteye.com/blog/2178324

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

http://www.geeksforgeeks.org/reservoir-sampling/

Read full article from Random Maximum | tech::interview