## Google Interview Question for Software Engineers

• 5

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

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
-1

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

Comment hidden because of low score. Click to expand.
4

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

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

c#.

``````bool rand_bit() {
bool x = rand_bit_p();
int counter = 0;
while ( true ) {
if( x != rand_bit_p() ) { break; }
counter++;
}
return (counter & 1) == 1;
}``````

Comment hidden because of low score. Click to expand.
0

suppose rand_bit_p returns 1 with probability 0.99999999

Comment hidden because of low score. Click to expand.
0

right

Comment hidden because of low score. Click to expand.
0

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=1 & a=0), second toss was 1 so return a. This has probability p*p.
2. Fist toss was 0 (a=0 & a=1), second toss was 0 so return a. 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.

Comment hidden because of low score. Click to expand.
0

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

}

Comment hidden because of low score. Click to expand.
0

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

}``````

Comment hidden because of low score. Click to expand.
0

So, I improved the solution, see the edited version above.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

zr.roman,

You could just do:

bool rand_bit() {
int counter = 0;
while ( true ) {
if( TRUE != rand_bit_p() ) { break; }
counter++;
}
return (counter %2);
}

Thanks.

Comment hidden because of low score. Click to expand.
0

zr.roman,

You could just do:

``````bool rand_bit() {
int counter = 0;
while ( true ) {
if( TRUE != rand_bit_p() ) { break; }
counter++;
}
return (counter %2);
}

Thanks.``````

Comment hidden because of low score. Click to expand.
0

It might seem to work if

``p``

is close to

``0``

or

``1``

, but clearly doesn't work if

``p``

equals to

``0.5``

.

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

}``````

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

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

}

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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

``````bool arr  = {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.

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

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.

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

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

Comment hidden because of low score. Click to expand.
0

see the same solution above

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Comment hidden because of low score. Click to expand.
0

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

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;

}``````

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

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.

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