Return a uniformly random index of the maximum in a stream

Question

Values arrive one at a time and you may read them only once. You want the position of the maximum value, but several positions may tie for that maximum.

Return a uniformly random index among all positions holding the maximum value, in one pass with $O(1)$ memory. Always returning the first (or last) maximum would bias the choice.

Accepted Answer

This is reservoir sampling with k = 1 restricted to the current set of ties. Track the best value seen, the chosen index, and a counter of how many positions have tied for the best so far. On a strictly larger value, reset everything. On a value equal to the best, increment the tie counter and adopt the new index with probability 1/	ext{count}. Trace on [3, 1, 3, 3]. Index 0 sets best =3, count =1. Index 1 (value 1) is smaller, skip. Index 2 ties: count =2, adopt index 2 with probability 1/2. Index 3 ties: count =3, adopt index 3 with probability 1/3. Uniformity among the ties at positions p…

Return a uniformly random index of the maximum in a stream

Your answer

More Coding questions