Practo Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
public static int tossDice(){
int bit1 = toss();
int bit2 = toss();
int bit3 = toss();
if(bit1==0&&bit2 == 0&&bit3==0){
return 1;
}else if(bit1 == 0&&bit2 == 0&&bit3==1){
return 2;
}else if(bit1 == 0&&bit2 == 1&&bit3==0){
return 3;
}
else if(bit1 == 0&&bit2 == 1&&bit3==1){
return 4;
}else if(bit1 == 1&&bit2 == 0&&bit3==0){
return 5;
}else if(bit1 == 1&&bit2 == 0&&bit3==1){
return 6;
}else{
return tossDice();
}
};
public static int tossDice(){
int bit1 = toss();
int bit2 = toss();
int bit3 = toss();
if( bit1 == 0 && bit2 == 0 && bit3 == 1 ){
return 1;
}else if ( bit1 == 0 && bit2 == 1 && bit3 == 0){
return 2;
}else if( bit1 == 0 && bit2 == 1 && bit3 == 1){
return 3;
}
else if( bit1 == 1 && bit2 == 0 && bit3 == 0 ){
return 4;
}else if( bit1 == 1 && bit2 == 0 && bit3 == 1){
return 5;
}else if( bit1 == 1 && bit2 == 1 && bit3 == 0){
return 6;
}else{
return tossDice();
}
};
public static int tossDice(){
int bit1 = toss();
int bit2 = toss();
int bit3 = toss();
if(bit1 == 0&&bit2 == 0&&bit3==1){
return 1;
}else if(bit1 == 0&&bit2 == 1&&bit3==0){
return 2;
}
else if(bit1 == 0&&bit2 == 1&&bit3==1){
return 3;
}else if(bit1 == 1&&bit2 == 0&&bit3==0){
return 4;
}else if(bit1 == 1&&bit2 == 0&&bit3==1){
return 5;
}else if(bit1==1&&bit2 == 1&&bit3==0){
return 6;
}else
return tossDice();
}
};
Toss coin 3 times (6 can be represented by 3 bits). If coin is heads set bit to 1, if coin is tails set bit to 0. If you get three heads in a row or three tails in a row [111 (7) or 000 (0)], start over. Otherwise convert the 3 bits into an integer (it will be between 1 and 6) and return that.
I propose the following solution: (i) in general, for a random generator 0 - N-1, you toss the coin n = ceil(log2(N)) times and concatenate the result. The result can be viewed as a random binary number. Hence you have a random generator between 0 and M= (2^n-1) (ii) Now the problem remains that it could be that N<M. In this case generate a random number x and if it is out of range, throw it away, and generate the new one until you get the right one.
A sample code is shown below:
public int randomDice() {
return random(6)+1;
}
// random generator 0 - N-1
public int random(int N) {
if (N <=1) return 0;
int n = Math.ceil(Math.log2(N));
int x;
while(true) {
x = 0;
for (int k=0; k<n; k++)
x += Math.pow(2, k)*(toss()?1:0);
if (x < N) break;
}
return x;
}
The idea: if we toss the coin 3 times, we can generate 8 values. If we remove 2 of them we only have 6 values.
Pseudo code:
int toss () {} //return 0 or 1
int generateRandomValue ()
{
int sum = 0;
while (!(sum <= 6 && sum >= 1)) {
for (int i = 0; i < 3; i++) {
sum += toss () * math.pow (2, i)
}
}
}
You can see full Python code at:
http://www.codeskulptor.org/#user39_nrdKC6WYMt_1.py
do this toss() func 3 times
- Bharat Kumar Arya January 16, 2015let XXX is result where X = H, T
ignore case of where all X are H or all are T
now the sequence will be
HHH = 1/8
HHT = 1/8
HTH = 1/8
HTT = 1/8
THH = 1/8
THT = 1/8
TTH = 1/8
TTT = 1/8
all with probability 1/8 now if HHH or TTT comes toss again for 3 times until different event occurs.
take H as 0 and T = 1
so the sequence will be
001= 1
010 = 2
011 = 3
100 = 4
101 = 5
110 = 6
all with equal probability (though we are skipping operations sometimes still)