Amazon Interview Question
Developer Program EngineersTeam: Love Film
Country: UK
Interview Type: Phone Interview
3. Multiply R by M to get file, then again multiply R by K to get the word from the file.
Let T be total words.
Formula = R*T/M(file number) + R*T%M (word number)
It should be calculated as simply as the following, given totalLines:
Random r = new Random();
double rGen = r.nextDouble();
int lineNum = (int) (Math.round(rGen * (totalLines - 1))) + 1;
return lineNum;
An integer can hold ~ 2^31 (2 billion line numbers), the double rGen can hold even more, so the million line numbers can be accessed using int for line number and double precision for random numbers.
or you could do like this
if number of lines is -x
create x/2 number of files so that each file has two words 0 represents the first and 1 represents the last
now the random number generated is multiplied the respective file(M) in which you have the desired word if that is equal to 0 then it represents the word 2*M
if not equal to 0 then it represents the word (2*M)+1
I think the file can't be loaded to memory at one place because of its size, so approaches goes like as follow.
- SRB December 23, 20121. Break the single file into multiple files(let it be M number of files) and each files have K words/lines.
2. Call random(), whch will generate num in between 0 & 1, let it be R.
3. Multiply R by M to get file, then again multiply R by K to get the word from the file.