## Amazon Interview Question for Development Support Engineers

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

let p = a/b, n = a+b, and m = logn

1. you need to toss coin m times, and generate binary number: x
2 if x <= n
if x < p
else
return tail
if x > n
repeat

This may waste many trials based on p. Not sure this is elegant solution.

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

@jack, great solution! though I had 3 questions:

1) Shouldn't it be p = a/n and 1-p = b/n, with n = a + b.

2) shouldn't it be "if x < a: return head " instead of "if x < p: return head", because a is an integer and p is presumably a rational number?

3) shouldn't it be "x < n" or "x <= n-1" instead of "x <= n", because x could potentially take on n values, i.e., 0, 1, 2, 3, ... n - 1, right?

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

Given in cormen solution's pdf...

While(1)
{
x = Biased_Toss();
y = Biased_Toss();
if(x!=y)
return x;
}

Pr { x=1 and y=0 } = P * (1-P)
Pr { x=0 and y=1 } = (1-P) * P

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

The solution proposed works great when we are running a computer program. But in the real world solution how does this work? In the question its not mentioned its a computer program.

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

Say Pr(H) and Pr(T) be the probability of getting head and tail from the biased coin.

then
we can say

``````toss coin twice
if it comes 'HT' then say its head ( Pr(HT) = Pr(H)*Pr(T) )
if it comes 'TH' then say its tail ( Pr(TH) = Pr(T)*Pr(H))

if it comes 'HH' or 'TT' then ignore the toss and repeat``````

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

Sorry i Didn't read the question Well ..

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

Say the value of this coin is 1. If the p we are looking for is 0.7 for winning. To make this coin unfair, we simply toss it 10 times and if we have 7 heads, we win. If not, we lose. I don't see any reason to write code for this.

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

if you toss 10 times ending up with 7 coins head up, the probability is not 0.7; you need to use binomial distribution to calculate the p.

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

We can designate 1 event(toss) = 2 flips of the coin. Now, we can assign random variable {X=head} if the 2 flips give us HT,TH,HH and {X=tail} if we have TT. With this arrangement we have Pr{X=head} > Pr{X=tail}. Thus we have a biased coin. Now, if needed a specific p value we may have to consider the equation 1 event(toss) = y flips of the coin.

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

Mold the coin to make it a dice.. so if winning probability is .1... make the dice with 10 faces and it should work.. coding doesn't always help..:)

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

Say p is 60 here. So if we select a random number between 1-100 and it is <= 60 then we return heads and if >=60 we return tail.

For getting a random number between 1-100 we see that 100 in binary = 1100100, which has 7 digits, so we toss the fair coin 7 times and make a binary number out of it. Depending on the number we return head or tail (as described above).

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

What if the number generated through the tossed coin is 1111111 (all heads 7 times)? How would you ensure that it is <=100 ?

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

Logan,

I don' think this solution works. The giving condition can just ensure the has equal condition for 0 or 1, but does not guaranttee equal distribution. So if we get random number range of 100, it can only guaranttee half time it is large than 50, half time it is less than 50.

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

You can do a %100 to get a number generated less than 100.

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

Toss twice, if "HH","HT","TH" consider it as H. If "TT" consider it T. now p(H) is 0.75 and p(T) is 0.25 :).

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

A simple way of approaching the problem would be to specify certain constraints. In this case, let us specify the number of tosses n per game.
For a given unbiased coin, if n=2, the possible tosses will be:
HH
HT
TH
TT
Pr(H)=Pr(T)=1/2.
So n=2 will not work. Lets choose n=3, we get:
HHH
HHT
HTH
HTT
THH
TTH
TTT
Pr(H)=11/21 Pr(T)=10/21. Here the coin is biased towards getting a Head than a Tail.

Hope this example helps.

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

U've missed THT

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.