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.

Question

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.

Arpan · Accepted Answer

import java.util.BitSet;
import java.util.Random;

public class BitSetOperation
{

    public static void doStuff(){
        BitSet s = new BitSet();
        int billion = 100000000;
        for (int l=0; l

Interview Candidate · Answer

The optimization for space meant: there's not enough space for holding 1 billion integers

Sigiloso · Answer

A bloomfilter would do the job i think.

Sigiloso · Answer

Suppose we hold the whole billion as an array of size=billion
int arr[BILLION];
int size = BILLION-1;
int getRandom(){
int index = rand(0,size);
swap(&Arr[index],&Arr[size]);
size--;
return Arr[size+1];
}
I don't use any additional space... so don't understand the second question

Tripadvisor

Pergunta de entrevista da empresa Tripadvisor

Respostas da entrevista

Empresas seguidas

Buscas de vagas