Google Interview Question
Software EngineersCountry: United States
Karthik think before you speak ! look at the code and the answer to your question will become clear. Hello, there is a while loop there, the code will repeat until we get p1 != p2 !!!!!
The condition is handled by the while loop. It has to infinitely loop until the 2 values are unequal. These 2 results are the only 2 that have equal probabilities of occurring.
{{
Flip1 Flip2 Probability
Heads Heads p*p
Heads Tails p * (1-p)
Tails Heads (1-p) * p
Tails Tails (1-p) * (1-p)
}}
If the coin is REALLY unfair, then p could be 0.99. p*p is huge, (1-p) * (1-p) is small, but (1-p) * p and p * (p-1) will always have the same probability.
That being said, if you have an incredibly skewed coin, this function could run for a long time.
The sum of the probabilities( p1(returns1) + p2 (returns 2)) should be 1.
but as per your logic above , it seems to be p(1-p) + p(1-p). It mean that the solution above does not returns true and false with priority p(1-p). But the question is , is it really 1/2??
Solution is incorrect. It will not return 1 and 0 with equal probablity.
Your logic is like this, when both generated bits are different (01 or 10) then return first bit (0 or 1 respectively). But think like this what if P(1) = 0.9 and P(0)=0.1 in this case probability of first bit is 1 will higher than probability of first bit is 0. it means you will return 1 bit with higher probability than 0.
c#.
Edited after comments received.
bool rand_bit() {
bool x = rand_bit_p();
int counter = 0;
while ( true ) {
if( x != rand_bit_p() ) { break; }
counter++;
}
return (counter & 1) == 1;
}
zr.roman I have a doubt about your approach. Can you please correct me ?
Lets say that probability of returning 1 is p. So according to your logic, you can get 0 as the output in these two cases:
1. First toss was 1 (a[0]=1 & a[1]=0), second toss was 1 so return a[1]. This has probability p*p.
2. Fist toss was 0 (a[0]=0 & a[1]=1), second toss was 0 so return a[0]. This has probability (1-p)*(1-p).
So P(0) = 1 -2p + p*p;
Similarly the output of your function will be 1, with the probability of p*(1-p) + p*(1-p).
P(1) = 2*(1-p)*p
Since P(0) != P(1), this is not a fair toss.
Please correct me if I am wrong.
The concept that I applied is similar i.e., you toss once and store value in var a. You toss again, flip the value and store in b. Now you check if a + b == 1. If they are then you toss again. If not, then if a+b ==0, you return 0 else you return 1.
The probability would be equal for both cases :: p*(1-p) == (1-p) * p.
Code below:
/*
* @author shivam.maharshi
*/
public class MakeFairCoinFromUnfairCoin {
public static int fairCoinToss() {
int a = unfairCoinToss();
int b = flipUnfairToss();
while (a + b == 1) {
a = unfairCoinToss();
b = flipUnfairToss();
}
// Probability of 0,0 is 0.24. Probability of 1,1 is 0.24.
return a + b == 0 ? 0 : 1;
}
private static int flipUnfairToss() {
return unfairCoinToss() == 0 ? 1 : 0;
}
// Returns 0 with 60% probability.
private static int unfairCoinToss() {
return Math.random() < 0.6F ? 0 : 1;
}
public static void main(String[] args) {
System.out.println(fairCoinToss());
}
}
Java Code:
/*
* @author shivam.maharshi
*/
public class MakeFairCoinFromUnfairCoin {
public static int fairCoinToss() {
int a = unfairCoinToss();
int b = flipUnfairToss();
while (a + b == 1) {
a = unfairCoinToss();
b = flipUnfairToss();
}
// Probability of 0,0 is 0.24. Probability of 1,1 is 0.24.
return a + b == 0 ? 0 : 1;
}
private static int flipUnfairToss() {
return unfairCoinToss() == 0 ? 1 : 0;
}
// Returns 0 with 60% probability.
private static int unfairCoinToss() {
return Math.random() < 0.6F ? 0 : 1;
}
public static void main(String[] args) {
System.out.println(fairCoinToss());
}
}
@Shivam Maharshi, thank you for your comprehensive comments! you are right.
So, I improved the solution, see the edited version above.
improved solution ? the first solution was wrong, second solution is different, and probably wrong too. Dont put bad answers here
Hi guys,
I did the math on zr.roman's code above, and if you compute the geometric series, you do not arrive at P[X=false]=P[X=true]=0.5 for X the random variable rand_bit(). Therefore, this is not the right solution.
Example:
P[X=false] = sum_{i=0}^{/infty} p*(1-p)^{2i+1} + sum_{i=0}^{/infty} (1-p)*p^{2i+1}
But this sum is sadly not 1/2. Can someone maybe check the math as well, and let me know if they come to a different conclusion?
hello, @kelly, sorry, but your math is quite unclear.
The idea of my solution is the following: when you start from 0 and begin increment by 1, you pass through a series of numbers where even and odd numbers alternate each other with equal interval, i.e. one by one.
So, imagine you started incrementing and the finish will happen in a random period of time.
So, the question is: what is the probability that the final value will be either even or odd?
The answer is obvious: the probability is 1/2.
Because of 2 reasons:
1) in the series of numbers there are no types except of "even" and "odd".
2) even and odd numbers alternate each other, i.e. no one even number stands near another even number, and no one odd number stand near another odd number.
So, this is actually the proof of correctness of my solution: the final probability is 1/2.
zr.roman,
Why do you have to start with "bool x = rand_bit_p();"?
You could just do:
bool rand_bit() {
int counter = 0;
while ( true ) {
if( TRUE != rand_bit_p() ) { break; }
counter++;
}
return (counter %2);
}
Thanks.
zr.roman,
Why do you have to start with "bool x = rand_bit_p();"?
You could just do:
bool rand_bit() {
int counter = 0;
while ( true ) {
if( TRUE != rand_bit_p() ) { break; }
counter++;
}
return (counter %2);
}
Thanks.
Java Code
/*
* @author shivam.maharshi
*/
public class MakeFairCoinFromUnfairCoin {
public static int fairCoinToss() {
int a = unfairCoinToss();
int b = flipUnfairToss();
while (a + b == 1) {
a = unfairCoinToss();
b = flipUnfairToss();
}
// Probability of 0,0 is 0.24. Probability of 1,1 is 0.24.
return a + b == 0 ? 0 : 1;
}
private static int flipUnfairToss() {
return unfairCoinToss() == 0 ? 1 : 0;
}
// Returns 0 with 60% probability.
private static int unfairCoinToss() {
return Math.random() < 0.6F ? 0 : 1;
}
public static void main(String[] args) {
System.out.println(fairCoinToss());
}
}
bool rand_bit()
{
while(1)
{
bool a = rand_bit_p();
bool b = rand_bit_p();
if (a != b) // P( a = true and b=false) = P( a=false and b=true) = p * (1-p) assuming independence===> 1/2 for both true and false.
return a;
}
}
For complexity, it is the expectation in a Bernouli trial=O(1/(2p(1-p))).
boolean rand_bit()
{
int a = 0;
for(int i = 0;i<y;i++)
{
a+=rand_bit_p();
}
return (a/(2*x)==0?false:true);
}
c#.
bool rand_bit() {
int N = Int32.MaxValue; // to cover the case when p is as close to 1 as possible
int res = 0;
for ( int i = 0; i < N; i++ ) {
res += rand_bit_p() ? 1 : 0;
}
return (res & 1) == 1;
}
it for sure won't be 50% /50% . What about p = 0.00001. Most of the time you would get 0 as a result
bool arr [10] = {false};
for (int i = 0; i < 10; i++)
arr[i] = rand_bit_p();
// evaluate arr array, if there are more then 10p true, return true
// less then 10p true, return false, if exactly 10p true, run the for
// loop again.
If we have a coin toss with 2/3 probs of heads and 1/3 probs of tails, we should coss toins thrice and if result is full heads, we halt with heads, if result is 1 head, we halt with tail, else we again toss thrice. This was the base logic I used for this solution. Haven't really calculated probabilities.
bool my_function()
{
bool val1 = rand_bit_p();
bool val2 = rand_bit_p();
if (val1 == false && val2 == true)
return false;
if (val1 == true && val2 == false)
return truel
return my_function()
}
This function will get val1=true with p and val2=false as 1-p so that combo with p(1-p)
and val1 = false and val2=true with 1-p(p). Else try again. So now we get that combo with equal probability.
c#.
bool rand_bit() {
bool x = rand_bit_p();
bool y = x;
int counter = 0;
while ( x == y ) {
y = rand_bit_p();
counter++;
}
return (counter & 1) == 1;
}
#include <stdio.h>
bool unfair(){
static int n;
return ++n % 5 == 0; // 20% true
}
bool fair(){
static int n;
return ++n%2? unfair(): !unfair(); // Ha!
}
int main(int argc, char** argv){
int c1=0, c2=0;
for (int i = 0; i < 100; i++){
c1 += unfair();
c2 += fair();
}
printf ("c1, c2: %d, %d\n", c1, c2); // 20%, 50%
}
#include <stdio.h>
bool unfair(){
static int n;
return ++n % 5 == 0; // 20% true
}
bool fair(){
static int n;
return ++n%2? unfair(): !unfair();
}
int main(int argc, char** argv){
int c1=0, c2=0;
for (int i = 0; i < 100; i++){
c1 += unfair();
c2 += fair();
}
printf ("c1, c2: %d, %d\n", c1, c2); // 20%, 50%
}
The idea is simple: toss 2 coins, until you get different results. Then the probability of (true, false) = the probability of (false, true). Even more, it is easy to compute that
P(first coin is heads | both coins are different) = 1 / 2.
Having this understanding, the code is obvious:
bool rand_bit() {
bool coin1, coin2;
do {
coin1 = rand_bit_p();
coin2 = rand_bit_p();
} while (coin1 == coin2);
return coin1;
}
Let X=1 for true and X=0 for false
E(X)=1*p + 0 *(1-p) = p.
To get it equally true or false E(X) should be 0.5 and therefore p should be 0.5. There is a solution only if rand_bit_t has equal probability. In the question he says " implement a fair given unfair.." another way to say impossible...
Can we just toss the unfair coin once, then toss our own 50% fair coin to determine if we take the value or the opposite?
Eg. Unfair coin is True 75%, False 25% of the time.
By tossing another 50% coin to determine whether or not we negate the original value, the Expected probabilities are..
T = .75(.5) + .25(.5) = .5
F = .25(.5) + .75(.5) = .5
bool rand_bit() {
return rand() % 2 ? rand_bit_p() : !rand_bit_p();
}
Why not simply use XOR?
return rand_bit_p() ^ rand_bit_p();
Probability should be equal:
t ^ f = t
f ^ t = t
t ^ t = f
f ^ f = f
Just think outside the box:
Boolean rand_bit(){
int trueCounter = 0; // count num of trues
for (int i = 0; i < 1000000; ++i)
if (rand_bit_p())
trueCounter++;
// get prob of getting true
int prob = (trueCounter)/1000000;
// ck if that's even or odd. ( Equally likely)
int rand = prob*100;
return rand%2 == 0;
}
draw it out as a square divided into 4 parts
- Dr A.D.M. January 25, 2016upper part is when P1 is true and lower half is when P1 is false
left part is when p2 is true and right when p2 is false