Sample an index of a maximal number in an array, with a probability of 1/(number of maximal numbers)
algorithm
Solution
Your algorithm works fine, and you can prove it via induction.
That is, assuming it works for any array of size `N`, prove it works for any array of size `N+1`.
So, given an array of size `N+1`, think of it as a sub-array of size `N` followed a new element at the end. By assumption, your algorithm uniformly selects one of the max elements of the sub-array... And then it behaves as follows:
If the new element is larger than the max of the sub-array, return that element. This is obviously correct.
If the new element is less than the max of the sub-array, return the result of the algorithm on the sub-array. Also obviously correct.
The only slightly tricky part is when the new element equals the max element of the sub-array. In this case, let the number of max elements in the sub-array be `k`. Then, by hypothesis, your algorithm selected one of them with probability `1/k`. By keeping that same element with probability `k/(k+1)`, you make the overall probability of selecting that same element equal `1/k` * `k /(k+1)` == `1/(k+1)`, as desired. You also select the last element with the same probability, so we are done.
To complete the inductive proof, just verify the algorithm works on an array of size 1. Also, for quality of implementation purposes, fix it not to crash on arrays of size zero :-)
[Update]
Incidentally, this algorithm and its proof are closely related to the Fisher-Yates shuffle (which I always thought was "Knuth's card-shuffling algorithm", but Wikipedia says I am behind the times).
Problem
This is one of the recent interview question that I faced. Program to return the index of the maximum number in the array [ To Note : the array may or may not contain multiple copies of maximum number ] such that each index ( which contains the maximum numbers ) have the probability of 1/no of max numbers to be returned. Examples: - [-1 3 2 3 3], each of positions [1,3,4] have the probability 1/3 to be returned (the three 3s) - [ 2 4 6 6 3 1 6 6 ], each of [2,3,6,7] have the probability of 1/4 to be returned (corresponding to the position of the 6s). First, I gave O(n) time and O(n) space algorithm where I collect the set of max-indexes and then return a random number from the set. But he asked for a O(n) time and O(1) complexity program and then I came up with this. ``` int find_maxIndex(vector<int> a) { max = a[0]; max_index = 0; count = 0; for(i = 1 to a.size()) { if(max < a[i]) { max = a[i]; count = 0; } if(max == a[i]) { count++; if(rand < 1/count) //rand = a random number in the range of [0,1] max_index = i; } } return max_index; } ``` I gave him this solution. But my doubt is if this procedure would select one of the indexes of max numbers with equal probability. Hope I am clear.Is there any other method to do this ?