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;

}

Read full article from Random Maximum | tech::interview