You have one billion numbers, implement getRandom() which returns a random number from them

Question

Possible Duplicate:
Algorithm to select a single, random combination of values?

This is an interview question i've seen online.

You have one billion numbers, implement getRandom() which returns a random number from them.

Constaints: 1. No duplicate returning value. 2. getRandom() will at most be invoked 100 million times. Then optimize for space.

How is this solution, and what are some better ones?:

Shuffle the array of numbers. Keep a counter starting at 0. Everytime the user calls getRandom, return the value at counter index. Increment the counter.

Randomizing an array in order to retrieve 1/10 of its elements is very inefficient. — Adam Liss, Mar 07 '12 at 03:50
That will generate numbers from only 1/10 of the set, which isn't really random. — Adam Liss, Mar 07 '12 at 03:56
do you have already some randomization primitive or do you have to do it from scratch — UmNyobe, Mar 07 '12 at 08:34
Please clarify if the numbers are sequential (within the set, but out of order), or if any of the numbers can have duplicates. — Seph, Mar 07 '12 at 09:06

score -1 · Answer 1 · answered Mar 07 '12 at 08:35

-1

Lets assume that you have a random function that returns 1 or 0 with equal probability. You can call this function 32 times to get a random number between 0 to 2^(32)-1. You can call this function 64 times to get a random number between 0 to 2^(64)-1.

answered Mar 07 '12 at 08:35

Avi Cohen

3,102
2
25
26

You have one billion numbers, implement getRandom() which returns a random number from them

1 Answers1