title: Sample an index of a maximal number in an array, with a probability of 1/(number of maximal numbers)
body: <p>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.</p>
  
  <p>Examples:</p>
  
  <ul>
  <li>[-1 3 2 3 3], each of positions [1,3,4] have the probability 1/3 to be returned (the three 3s)</li>
  <li>[ 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).</li>
  </ul>
  
  <p>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.</p>
  
  <pre><code>int find_maxIndex(vector&lt;int&gt; a)
  {
       max = a[0];
       max_index = 0;
       count = 0;
  
       for(i = 1 to a.size())
       {
           if(max &lt; a[i])
           {
               max = a[i];
               count = 0;
           }
           if(max == a[i])
           {
                count++;
                if(rand &lt; 1/count) //rand = a random number in the range of [0,1]
                    max_index = i;
           }
        }
        return max_index;
  }
  </code></pre>
  
  <p>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 ?   </p>