Google Interview Question for Software Engineers


Country: United States




Comment hidden because of low score. Click to expand.
13
of 13 vote

while(true)
{
	p1 = rand_bit_p();
	p2 = rand_bit_p();

	if(p1 && (!p2)) return true;   // prob = p * (1-p)
	if((!p1) && p2) return false; // prob = (1-p) * p
}

draw it out as a square divided into 4 parts
upper 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

- Dr A.D.M. January 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
-1
of 7 votes

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 !!!!!

- gen-x-s January 27, 2016 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 votes

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.

- Professor Frink January 27, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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??

- coolhaitechie February 01, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- jigs February 04, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The solution is correct. 0 and 1 would be returned with equal probability, not with that of p(1-p).

- SK February 15, 2016 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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 January 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

suppose rand_bit_p returns 1 with probability 0.99999999

- emb January 24, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

right

- zr.roman January 24, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Shivam Maharshi January 25, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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());
}

}

- Shivam Maharshi January 25, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 January 25, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Shivam Maharshi, thank you for your comprehensive comments! you are right.
So, I improved the solution, see the edited version above.

- zr.roman January 25, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

improved solution ? the first solution was wrong, second solution is different, and probably wrong too. Dont put bad answers here

- gen-x-s January 26, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Kelly February 03, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 February 04, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- SK February 15, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- SK February 15, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It might seem to work if

p

is close to

0

or

1

, but clearly doesn't work if

p

equals to

0.5

.

- Yola July 02, 2019 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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 January 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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))).

- Farhat Latrach July 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

boolean rand_bit()
{
int a = 0;
for(int i = 0;i<y;i++)
{
a+=rand_bit_p();
}

return (a/(2*x)==0?false:true);

}

- Akash Mahajan January 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The probability to receive true and then false equals the probability to receive false and then true regardless of the value of p.

bool rand_bit() {
        bool x,y;
	while (true) {
		x = rand_bit_p();
                y = rand_bit_p();
		if (x && !y) return true;
                if (!x && y) return false;
	}
}

- haim.s January 25, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        }

- zr.roman January 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it for sure won't be 50% /50% . What about p = 0.00001. Most of the time you would get 0 as a result

- Mont January 24, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

quite reasonable observation.
Below I provide a better solution with 50/50 probability for sure.

- zr.roman January 25, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- furkan ipek January 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The probability to receive true and then false equals the probability to receive false and then true regardless of the value of p.

bool rand_bit() {
        bool x,y;
	while (true) {
		x = rand_bit_p();
                y = rand_bit_p();
		if (x && !y) return true;
                if (!x && y) return false;
	}
}

- haim.s January 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Sutapa January 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool biasedCoin() {
	float prob = float((rand() % 10)) / 10.0;
	return prob < 0.2;
}

bool unbiasedCoin() {
	bool coin1 = true, coin2 = true;
	while (coin1 == coin2) {
		coin1 = biasedCoin();
		coin2 = biasedCoin();
	}
	return coin1;
}

- AryaPhilip January 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        }

- zr.roman January 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

see the same solution above

- zr.roman January 25, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool test () {
    bool first = rand_bit_p();
    bool second = rand_bit_p();
    return (first && !second) || (!first && second);
}

- Anonymous January 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean randBit(int p) {

        boolean first, second;

        while (true) {
            first = randBitBiased(p);
            second = randBitBiased(p);

            if (first && !second) {
                return true;
            }

            if (!first && second) {
                return false;
            }
        }
    }

- m@}{ January 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean randBit(int p) {

        boolean first, second;

        while (true) {
            first = randBitBiased(p);
            second = randBitBiased(p);

            if (first && !second) {
                return true;
            }

            if (!first && second) {
                return false;
            }
        }
    }

- m@}{ January 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if two tosses of the coin get the same result then the coin is unfair so we start again. If not then we return the first or second tossed value.

def rand_bit():
	p1 = rand_bit_p()
        p2 = rand_bit_p()
	if p1 == p2:
		return rand_bit()
	else
		return p1

- aka January 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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%
}

- Anonymous February 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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%
}

- Mabooka February 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- vborees February 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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...

- farhat latrach March 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}

- UnsoundOfMind April 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

// probability of even or odd is always 50%. hence using that trait.
boolean rand_bit() {
	int number = rand_bit_p() * 100;
        if(number%2 == 0) {
		return true;
	} 
	return false;
}

- Anonymous January 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Why not simply call rand_bit_p twice and XOR the result?

return rand_bit_p() ^ rand_bit_p();

probability for both t and f is equal (p*p + (1-p)*(1-p))
t ^ f = t
f ^ t = t
t ^ t = f
f ^ f = f

- helios February 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Helios February 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Helios1234 February 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Helios1234 February 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well, because
P(0) = (1-p)^2 + p^2
P(1) = 2*p*(1-p)

- Alex February 17, 2016 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;


}

- shah February 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int random()
{
static int coin = rand_bit_p();
coin ^= rand_bit_p(); // flip coin with probability p.
return coin;
}

- Charles February 22, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More