CareerCup

The Random.next()[1] function is implemented using a linear congruential pseudo random number generator[2]. This is a simple algorithm where you take the seed value and generate random numbers using the following formula:

X(0) = seed >> 2^48.
X(n+1) = (25214903917* X(n) + 11) (mod 2^48)


This gives us a random number generator with a uniform distribution between 0 and 1. If you need a guassian distribution, Random.nextGuassian() [3] implements it using the Marsaglia's polar method. [4]

Refer to Java doc for [1] and [3].
Refer to wikipedia for [2] and [4]

int randomNumber(int no)
{
return System.getCurrentTimeInMillis()%no;
}

I suppose what facebook guys wanted to hear is to design a (almost)nondeterministic source of randomness that makes the best generic use of what the machine or the OS would provide indirectly.

#OS scheduling provides us with such a mechanism:

Pseudo code:

Function randomBinary returns boolean
yield OS scheduler;
Get system processor cycles count or maybe RTC based nano level counter
Check if the counter is even or odd;
If odd
Return 1;
Else
Return 0;


Function Rand(int n ) returns integer
Declare new random number R = 0;
While (R < n)
Call randomBinary and modify the LSB of R
Shift R by 1
Return residual and random part of R


I think this will pass most of the statistics test.

# other solution would be linear congruent approach

int Rand_Num_Equal_Pro(const int n){
static int Flag[n];
int r, temp;
time_t t;
struct tm *t;
t= localtime(&t);
r= t->tm_sec+ t->tm_min*10+ t->tm_hour*100;

srand(r);
r= rand();
r= r%n;
temp= r+1;
if(Flag[r]){
while(Flag[temp]&& (temp%n)!= r) temp++;

if((temp%n)== r){
for(int i= 0; i<n; i++)
Flag[i]= 0;
return r;
}
else{
Flag[temp%n]= 1;
return temp%n;
}
}
else{
Flag[r]= 1;
return r;
}
}

check en.wikipedia.org/wiki/Mersenne_twister

check Mersenne twister on wikipedia

search Mersenne twister

1) Create a dyanamic memory of type char ie, size will be 1.
2) Store the value of the memory to a integer variable.
3) Take the mod of the interger variable for n
we will get a random function in the range 0-n1

int rand(int num){
char * a=(char *)malloc(sizeof(1));
int b= a;
b=b%num;
return b;
}

This comment has been deleted.

the problem seems similar to shuffling a deck of cards.
now what you would do is, generate a random number between 0 - n-1 and choose that index to mark the entry/value (i.e. arr[random_i] as dead by swapping it with the start index which also keeps moving with each new number being generated).

i.e. swap (arr[startIndex], arr[random_i]).

and you generate number between startIndex and n-1 and keep doing this n times. Then the array contains the numbers generated with equal probability.