P#15 Random Element Selection

All problems are from https://www.dailycodingproblem.com/

 

My Solution Codes : https://github.com/Kusin/DailyCoding

Kusin/DailyCoding

Daily Coding Problem #15 : Random Element Selection

 

The problem is that there are too many elements. So we have to pick an element without storing them.

 

If we know the size of Stream.

Let the stream size N

if we pick an integer k from 0 to N-1 in uniform probability, choose kth element from the stream. It will be equivalent as the original problem. So how do we do this? My method is this.

Choose a real number from [0,1). multiply N. then the number would be [0,N). Floor it. Then we get an integer 0 to N-1. 

If the stream's size is Undefined

(e.g.) input a number while it is not zero)

 

This would be the possibly purpose of the problem. Scanning only once.

If we know the length, we can allocate each element a bounded-unique-number, which is called 'index'. However, as we don't know the length, we need a new approach.

 

LOL! This is an amazing problem. Suppose we are scanning a array. From beginning to the end, we have to choose a random value from the beginning to current element without using the first approach.(selecting 0~N-1 integer). 

 

I searched solution in google and discovered an amazing approach.

Use the fact that probabilty of being min/max is uniform.

Let's think of an another array stored with random values. For each index, the probabilty of storing a Maximum value is Uniform.

Go back to the original stream. While scanning the elements of the stream, assign a random value to each elements. Then, if the assigned value is Maximum, update the answer( element to choose) to current element.

 

This is the algorithm! The approach is wonderful. 

 

Implementation