## Amazon Interview Question for Software Engineer / Developers

• 3

Country: United States

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

LOL :) You really made this board fully of joy! I like your answer very much. Anyway I will give my way to approve the result.

The possiblity to have only 1 child is 0.5   (1 boy, and 0 girl);
The possiblity to have only 2 children is 0.5^2 (1 boy, and 1 girl);
...
The possiblity to have only i children is 0.5^i (1 boy, and i-1 girl);

So the number of boys expected is P = 0.5 + 0.5^2 + .. + 0.5^i + ...
So the number of girls expected is Q = 0.5^2 + .. + (i-1)*0.5^i + ...

It's easy to find out that
Q*2 - Q = P
P*2 - P = 1

So P = Q = 1

This implies that each pair of parents will have just 2 children in
average, one boy and one girl.

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

Hi Westlake, can you pls explain why probability of having only 2 children, 1 boy and 1 girl is 0.5^2. It should be 0.5 not 0.25

In general the probability formula for having k successes in n tries is
(n!/(n-k)! * k!) * p^k * q^(n-k)

Here
k = success (Getting a boy)
n = number of tries (in 2 children case, number of tries are 2)
p = Probability of success in 1 trial (Probability of getting a boy and a girl is 0.5 each)
q = 1-p = Probability of failure in 1 trial (probability of failure, that is getting a girl child is 0.5)

So for p(2,1) = (2! / 1! * 1!) * 0.5 ^1 * 0.5^1 = 0.5

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

The couple have 2 children when they first had a girl and then a boy.

The change for a girl is 0.5 and the chance for a boy is 0.5. The chance for this combination is 0.5*0.5 = 0.25.

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

How did you come up with this:

It's easy to find out that
Q*2 - Q = P
P*2 - P = 1

???
I think

Q*2 - Q = Q
P*2 - P = P
2 * 2 - 2 = 2 != 1

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

This problem can be solved by using Negative Binomial distribution NB(r,p), where the r is the number of success(boys), in this case: r=1. Let X be the number of girls. You would need to calculate the expected value of girls: E(X)= pr/(1-p)=(1/2)/(1/2)=1 for NB distribution. So the ratio is E(X)/E(# of boys) = 1/1=1.
This question can be extended: say the probability of having a boy is not 1/2, say 51/100, and # of boys each family want is 3. Now this ratio should be E(X)/r = p/(1-p) = 49/51. So the # of boys won't affect the ratio, while the probability of having a boy will.

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

In your consideration you missed the case when there are consecutive girls.

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

I believe the answer is - there is eventually no one left. Eventually, you have all boys (whats left of them) and the next generation cannot proceed. This is because as each generation passes, you will have the possibility of having less girls than boys. When that happens, the next set of parents will less than the previous set. The boys who did not get married will die and not replace themselves for the next generation. On an infinite cycle, its inevitable that the boys will reduce. The girls could have been more than the boys in any given generation, but that is inconsequential becuase the excess girls cannot marry. Therefore, the number of boys can never increase.

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

While this is a nice observation, it is the answer to a different question, and perhaps based on a different model.

You are asked to quantify the ratio of girls / boys not what happens to the whole population. What if there are no couples and the villagers are self-cloning aliens?

Regardless, based on your model, at any generation "t", we have E[boys] = E[girls]. This expected value could be vanishing-ly small, assuming a marriage model, or excessively large if we assume a self-cloning model.

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

I think it's one, because even you have more boys than girls, but one boy can only married to one girl. So this make the ratio to 1 in infinite years. The boys who don't have wife will die without children.

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

Huh?

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

Idiotic. Why do you think monogamy is a rule?

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

While NOT mathematically what people where are expecting .. for that see the standard answer on summing together a infinite series which translates to ratio 1.. I agree with you. The answer looks valid to me. May be people are angry because the could not think beyond maths.

In the mathematical answer as well, there would be time when the ratio would be skewed from perfect 1. And so it would be in case of this answer as well.

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

Sorry, this is a bogus answer. There was no assumption of single spouse marriage or mortality. Just because the final result is (probably) right does not mean the argument is right too.

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

Expected number of children N = 1/2 + 2/2^2 + 3/2^3 + ...

2N = 1 + 2/2 + 3/2^2 + 4/2^3 + ...

N = 1 + 1/2 + 1/2^2 + ... = 2.

Thus we would expect the ratio of 1.

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

Explain?

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

I think...

Expectation = sum over x * (probability of x)

1 child = 1 * 1/2
2 child = 2 * 1/2 * 1/2
3 child = 3 * 1/2 * 1/2 * 1/2
...
and so on.

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

Of course, that does not mean expected ratio of girls/boy is 1.

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

our typical indian family... boy.. SOLUTION!

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

Assuming having a village with 64 families.

After they all have their babies, the village will have 32 baby boys and 32 baby girls. The number of boys = number of girls. Now, 32 families who had boys will stop having babies.

Of the remaining 32 families... 16 will have boys and 16 will have girls. The "total" number of baby boys = total number of baby girls = 32+16=48

Now, we have 16 families still going at it... of these, 8 boys and 8 girls will come out. Total number of boys = total number of girls = 32+16+8 = 56

Now, 8 couples will produce 4 boys and 4 girls. We have 60 boys and 60 girls total.

Next, 4 couples will have 2 boys and 2 girls. 62 boys and 62 girls

2 couples left... 63 boys and 63 girls

And finally we have only 1 couple left... Ignoring this pop couple who have had 8 babies in a row... As counter-intuitive as it looks, we can see that the ratio of baby boys/baby girls remains constant.

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

for the people that are too concerned about the "infinite years"...

there will come a time, when the sun will turn into a black hole... in billions of billions of billions.... years... but definitely that will happen before "infinite years".

there will be no boys and no girls. the ratio of girls to boys will be undefined (divide by zero)

I think the intent of the interviewer was not to ask about "infinite years", but wanted the interviewee to take a limit as n goes to infinity in the expected value of the two numbers.

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

The ratio is 1. Think about it this way.
Given "N", "N / 2" of families will have a single boy. The other "N / 2" will have a girl as a first child.
Now let's assume the second "N / 2" give their first-born (girl) to the first "N / 2" family. So we have "N / 2" families with 1 boy and 1 girl, and "N / 2" families where they keep trying until they get a boy. By recursion, you find that the ratio has to be one.

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

I like this answer the most! Thanks!

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

You're welcome! I have to admit though I first solved this the hard way by finding expectations.

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

The expected number of boys is 1, since they keep making babies until getting a boy :)

The expected number of children is C = 1/2 + 2/2^2 + 3/2^3 + ... + k/2^k + ...

With some tricks we can find that C = 2.

Thus in average each family have 2 children, 1 boy, 1 girl!

Tricks:

C 	= 1/2 + 2/2^2 + 3/2^3 + ... + k/2^k + ...
2C 	= 1 + 2/2 + 3/2^2 + ... + k/2^(k-1) + ...
= 1 + (1/2+1/2) + (2/2^2 + 1/2^2) +...+ {(k-1)/2^(k-1) + 1/2^(k-1)} +...
= {(1 + 1/2 + 1/2^2 +...+ 1/2^(k-1) +...}  +  1/2 + 2/2^2 +...+ (k-1)/2^(k-1) +...
= 2 + C
=> C = 2

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

I have a different thought. If we consider the fact that human has limited life span, eventually someone will die. In infinite time, don't u think there will be no one left because there there will be less and less girl to match a man?

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

I was mistaken. Actually i believe it is 1 too.

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

Probability of having a boy=Probability of having a girl = 1/2

if a family has n children one among them is boy n-1 girls and1 boy

probability of having n children = 1/(2^n)
because n-1 fails(n-1 girl children) * 1 pass(a boy)=1/(2^n-1)*1/2

now the expected number of children in each family is
E[x]=Summation {number of children*probability of having them}

E[x]=1/2 + 2/2^2 + 3/2^3 + ... + k/2^k + ...

this means we can expect 2 children in each family but we know that each family has at least 1 boy that's why they stopped(except infinity case). that is 1 boy and 1girl so ratio is 1.

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

"...they keep doing child..."

What the? That's disgusting!

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

The question asks what will be the population of the village after infinite years. This question has definitely incomplete data. The answer depends on probability for each generation that a given couple will have boy or a girl.

Lets say that for 1st generation (adam and eve) the probability of having boy is 0.25. Which means adam and eve will have to procreate 4 times and 4th child will be a boy. Population after 1st generation will be 4. Now population for 2nd generation also depends on probability of having a boy which can be any number. Hence to predict population for a given generation, we need probability distribution for random variable for the event having a boy which is not given.

If we assume uniform distribution of .25, then the infinite series will not converge and hence the answer is infinity.

The series can converge only if PDF can be such that infinite series can converge.

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

Probability of having girls kid will be increasing generation by generation.... and for time before infinity time all girls will remain and there will not be any more generation.

Only the 'infinite time' mentioned in qus made me to think in this way else there is no certainty

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

Doesn't look like my approach is in here!

Since couples stop producing at 1 boy, then we have these possibilities.

B
GB
GGB
G...GB

Now let's look at the possibilities that these each happen:

B   (1/2)
GB (1/4)
GGB (1/8)
G...GB (1/(2^n) )

And the contribution to the ratio of boys in each of these:

B   (1/2) (1)
GB (1/4) (1/2)
GGB (1/8) (1/3)
G...GB (1/(2^n) ) (1/n)

So we get an infinite series here:

\sum_i (1/(2^i) ) (1/i)

My series is shabby, but you can add the first few terms (1/2) and (1/8) and see that it is converging to 2/3.

Thus, over the long term and with a large enough population, 2/3 of the town will be boys and 1/3 of the town will be girls.

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

{{ E(Girl) = 1/2 + E(Girl) --> E(Girl) = 1 }}
{{ E(Boy) = 1/2 + E(Boy) --> E(Boy) = 1 }}

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

The answer is indeed half. Many of the solutions give nice formulas to prove this, but there's a much simpler answer: it's half no matter what stopping conditions are chosen, because of the simple fact that each child born has a 50% chance of being a boy.

Don't believe it's that simple? Consider a random bit string (this is from random.org):

1001101001001100111010110011000111110000

What's the expected fraction of zeros? Half. Now introduce breaks after each one (boy born):

1 0011 01 001 0011 00111 01 011 0011 00011111 0000

Each string is a family that waited til their first boy. *Now* what's the expected fraction of zeros?

It didn't change.

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

probability will be =1/2

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

every male wil have exactly ONE male child,

number of girls may be 0,1,2,3,4,5......till a male child is born.

hence girls go on continuously increasing ,
but boys remain the same .
hence girls / boys >>>>>>large.

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

probability of having:

1 child = 1/2
2 children = 1/2*1/2
3 children = 1/2*1/2
...
n children = 1/(2^n)

Math expectation of having girls:

1 * 1/2 + 2 * 1/2*1/2 + 3*1/2*1/2*1/2 ... + n * (1/(2^n))

Math expectation of having boy:

1/2 + 1/4 + 1/8 + ... + 1/(2^n) = 1

which means that ratio girls/boy = sum(i=1;i<=n;) i/(2^(i+1)) which is infintiy

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.