Subscribe to:
Post Comments (Atom)
Cracking the Coding Interview: Fourth Edition (308 page e-book / PDF)
Delivered instantly as a PDF via email. For Software Engineers & SDETs
- 150 programming interview questions and answers
- 5 proven approaches to crack algorithm questions
- 10 mistakes candidates make, and how to avoid them.
- How to prepare for technical and behavioral questions without wasting your time!
Just $29.99 to Crack the Interview!
I think it should be 0.95/3
ReplyDeleteYou have to look at your probability of NOT seeing a car, which is .05 in 30 minutes. In order to break this down into 10 minute chunks, you need to figure out how you arrived at that probability, which would be x * x * x = .05, so x ^ 3 = .05.
ReplyDeleteI don't have a calculator, but the then you would have the third root of .05. Then you would subtract that from 1 and arrive at your 10 minute probability.
Agree with Chuck
ReplyDeleteI'm confused with chuck's answer. According to that, aren't we finding the probability of NOT seeing the car in 10 mins. rather than seeing it?
ReplyDeletePlease correct me If I'm wrong.
Chuck is right.
ReplyDeleteLet p is a probability to see a car in 10 minutes.
Then (1-p) is probability NOT to see a car in 10 minutes.
Then probability NOT to see a car in 30 minutes is (1-p)*(1-p)*(1-p).
(1-p)^3 == 0.05
So p = 1-0.05^(1/3)~ 0.63
I think John might be right. It seems to me that there is another way to look at this that provides a different answer.
ReplyDeleteSince you know the probability of seeing a car in 30 minutes is 0.95, then look at the probability of seeing a car in the first 10 minutes, or the second 10 minutes or the third ten minutes.
So then it is like a disjunctive probability: P( A or B or C ), i.e. P( 1st 10m or 2nd 10m or 3rd 10m ).
The formula for a disjunctive probability is
P(A or B or C) = P(A) + P(B) + P(C)
Since the default probability is constant, then, P(A) = P(B) = P(C) = x, so
3x=0.95
x = 0.95/3
Thanks for any comments
-Julie
Nevermind my last post, I think it is incorrect because the probability of seeing a car in the first second or third 10 minutes is not independent, so I used the wrong formula.
ReplyDeleteHere is another way to look at it. If you treat it like short circuit evaluation boolean logic. You can see a car in the first 10 minutes (A), or not see it in the first 10 minutes (not A) and see it in the second ten minutes (B), or not see it in the second ten minutes (not b) and see it in the third ten minutes (C). The formula for this looks like:
A or ((notA)and(B or ((notB)andC)))
since A=B=C, then it becomes
p + (1-p)*(p + (1-p)*p) = 0.95
which becomes
p^3 - 3p^2 + 3p = 0.95
If you somehow solve this, or graph it on a calculator you find that for p= 0.6 the answer is approximately 0.95.
Chuck's way is easier though.
notA and notB and notC = 0.05
which is
x*x*x = 0.05
0.05 ^ 1/3 = 0.4
1 - 0.4 = 0.6
well done Julie! Your final post is correct.
ReplyDeleteI disagree. I can prove mathematically strictly that it is impossible to calculate this probability without additional conditions. Knowing that density of probabiltiy is constant is not sufficient you should also know its value.
ReplyDeleteLet p is probability density. Then it can be shown that solutions is
F(t) = 1 - 0.05 * e ^ p(30 - t)
I can provide complete solution if anyone is interested.
since F(0) = 0
ReplyDeletep = - Ln(0.05) / 30
and the final solution:
F(t) = 1 - 0.05 ^ (t / 30)
F(10) = 0.6316
i don't think so, multiplication of probability will give the correct answer. If this answer is correct, then what is it for 40 minutes or more. Will u go on multiplying?
ReplyDeleteF(40) = 1 - 0.05 ^ (4 / 3) = 0,982
ReplyDeleteLim (t->inf) F(t) = 1;
Formula: F(t) = 1 - 0.05 * e ^ p(30 - t) was derived from the following reasoning:
Let p is constant probability density.
Then by probatility sum
F(t + d) = F(t) + p*d - F(t)*p * d
(F(t + d) - F(t)) / d = p*(1 - F(t)) - it is a simple differenital equasion.
F' = p * (1 - F)
The solution of this equasion (taking into account the boundary condition) is F(t) = 1 - 0.05 * e ^ p(30 - t)
Then substitute F(0) = 0 to find p
that is it!
Shouldnt probability of observing a car in 30 mins be more than that of probability of observing a car in 10 minutes? Common Sense thats all. If you keep increasing time span it will eventually hit 1.
ReplyDeleteIt should and it is. (read carefully)
ReplyDeleteF(0) = 0
F(1) = 0.095
F(10) = 0.6316
F(30) = 0.95
F(40) = 0,982
F(Inf.) = 1;
Andy, you're way overthinking this. The solutions above are correct. Look them over again and you'll realize there's no need to try and invent an (incorrect) function.
ReplyDeleteAnonymous.
ReplyDeleteI don't insist that proposed solutions were wrong. I also don't want to persuade you that my solution is correct. But I think that the following link will be interesting for you.
http://en.wikipedia.org/wiki/Exponential_distribution
I have some different view.
ReplyDeleteProbability of seeing a car in 30 mins is 0.95.
So a car can definitely be seen (i.e. probability 1) in 30/0.95 = 31.57894737 minutes.
So the probability (P) of seeing a car in 10 mins will be:
P = 10/31.57894737 = 0.316666667
No, car can defenetly be seen only in Infinity!
ReplyDeleteIts always the same - 0.95. In roulette; if the chance on hitting 29 in the 1st spin is 1 in 35 what is it on the 35th spin? I in 35. The spin before has nothing to do with the present spin or the spin after. if you divide by 3, the chances are always the same for 1st 10 mins, 2nd 10 mins and 3rd 10 mins.
ReplyDeleteI'm hammered right now - but does that make any sense?
Its always the same - 0.95. In roulette; if the chance on hitting 29 in the 1st spin is 1 in 35 what is it on the 35th spin? I in 35. The spin before has nothing to do with the present spin or the spin after. if you divide by 3, the chances are always the same for 1st 10 mins, 2nd 10 mins and 3rd 10 mins.
ReplyDeleteI'm hammered right now - but does that make any sense?
What I mean to say is that: (assuming constant default probability)
ReplyDeleteThe probability never changes. Since you don't know if it will happen in the 1st 10 mins or the 2nd 10 mins or the 3rd 10 mins the chances are always 0.95 - the 10 minutes before or after has nothing to do with it at all as they cant affect that particular block of 10 mins... :-S
ok - goodnight
Abhijeet is right. everyone else is wrongly assuming that the ten minute period is 1) part of the 30 min period 2) dependant on any other ten minute period that has passed or will pass.
ReplyDeleteThose who say the probability remains the same are partly right - the traffic will not increase or decrease according to what has already passed, but the probability IS dependant on time.
a car passes on average every 30/0.95 = 31.57894737 minutes.
this will not increase just because you've already sat there watching nothing. If the probability of seeing a car in ANY 10 minute period during the day is 63% as some are suggesting, that would mean a car would pass on average every 10/0.6316 = 15.83 minutes which is not right!!!
Hey people, your a bit trippin', xFlowers and 2nd Julia formula (and result) was correct since you cant divide time on 3 equal parts and calculate how many cars pass by in each part.
ReplyDeleteSorry for my bad english.
P.S: These google questions are wicked :)
n chunks and every chunk has same prob p
ReplyDelete( 1 minus the chance that it does not happens n times is the chance that it happens )
1 - ( 1 - p)^n = 0,95
or
(1-p) ^ n = 0,05 (1)
one third of the chunks
1 - (1-p) (n/3)
we substitute (1)
1 - (0,05) ^ (1/3)
or generally expressed in minutes:
F(t) = 1 -(0,05) ^ (t/30)
so , it is not always necessary to use differential equations :)
This is poisson's distribution example.
ReplyDeleteprobability of finding at least one car in 30 min. is 0.95
P(X>=1)=0.95 => P(X=0)=0.05=exp(-lambda)
as P(X=n)=exp(-lambda)*lambda^n/lambda!
=> lambda = ln(20) = mean of the distribution = x/30 => x=30*ln(20)
NAGAMOHAN.Y
naaga_yjntu@yahoo.com
as mean is the average number of cars, found on the high way, per minute and x is the average number of cars found, on the highway, in 30 minutes
answer=P(X>=1)=1-P(X=0)=1-exp(-x/10)=1-(1/(20^3))
answer = 1-(0.05^3)
This is poisson's distribution example.
ReplyDeleteprobability of finding at least one car in 30 min. is 0.95
P(X>=1)=0.95 => P(X=0)=0.05=exp(-lambda)
as P(X=n)=exp(-lambda)*lambda^n/lambda!
=> lambda = ln(20) = mean of the distribution = x/30 => x=30*ln(20)
as mean is the average number of cars, found on the high way, per minute and x is the average number of cars found, on the highway, in 30 minutes
answer=P(X>=1)=1-P(X=0)=1-exp(-x/10)=1-(1/(20^3))
answer = 1-(0.05^3)
this last comment is wrong.
ReplyDeleteif 30 minutes is 0,95 then it is never
1-(0,5)^3 > 0,95
so that is wrong, but what did you do wrong.
You can approach it with poisson:
You calculated lambda , the average of cars passing in half an hour...
so in 10 minutes the average of cars passing is lambda/3
p(n>1)=1-p(0)= 1-exp(-lambda/3)
= 1-exp(-ln20/3) = 1 -exp(-ln20)^(1/3) = 1 - exp(ln 1/20)^(1/3) = 1 -0,05^(1/3)
anonymous made a mistake.
ReplyDelete1-(0,5)^3 > 0,95
approaching with poisson is coorect but then you have to apply it correctly:
He calculated lambda as the average of cars passing in half an hour which is ln(20) but then then the average of cars passing in 10 minutes is ln(20)/3
which will lead to
1-(0,5)^(1/3)
indeed you can approach with poisson but then you have to keep in mind what you are doing.
ReplyDeleteCalculating lambda as ln(20) means the average of cars passing in half an hour.
this means then that the average of cars passing in 10 minutes is ln(20)/3 which leads to
p(0)=1-(0,05)^(1/3)
andy is right
ReplyDeletehe is genius
this subject is operation research ?
andy is right
ReplyDeletehe is genius
this subject is operation research ?
thank you...
ReplyDeleteit's just math :)
It's not clear to me what is meant by constant default probability....if, say theres a 3n long bar of chocolate and theres a constant default prob of 95 for finding a peanut in it... if you take away n long bar of that chocolate , u will still find prob of 95 to find a peanut. Is it analogous?
ReplyDeleteI will try to explain in non-maths terms :D
ReplyDeleteWhats the probability of seeing a heads in 2 tosses.
Answer:
It is .75 i.e. 3/4 (HH, HT, TH, TT).
SEE!! This doesn't mean the chance of seeing a head in 1 toss is .75/2
Whats the probability if coin is not fair and shows Heads 10% time only.
Answer:
First time toss. Chance of heads: .1
Second time toss. Chance of heads: .1
But second toss only adds value if we haven't already seen heads in first toss. Chance of first toss showing tails is 1-0.1 i.e. 0.9. So probability of seeing heads in 2 tosses is: .1 + .9 * .1 = .19
Same way chance of seeing car in 10 minutes is lets say x.
Chance of seeing car in 20 minutes is x + (1-x)*x.
Same way chance of seeing car in 30 minutes is:
Chance of seeing car in first 20 minutes + (chance of NOT seeing the car in first 20 minutes * chance of seeing the car in last 10 minutes)
i.e.
= x + (1-x)*x + (1 - (x + (1-x)*x))*x
gives 3x - 3x2 + x3 = 0.95
Andy's answer fits the solution perfectly. If we had calculated using the chance of NOT seeing the car and inverted it in the end, likely the equation would have been simpler. But I already did it this way :)
andies is the same a jo russel and others
ReplyDeletestating F(t)=1-0.05 e ^ (p(30-t)) with F(0)=0 leeds to p= ln 20 /30
for t=10 this leeds to
F(10)=1 -0.05 e ^ (20ln20/30)
=1-0.05 x 20 ^ (2/3) = 1 - 1/20 x 20 ^ (2^3)
= 1 - 20 ^ (-1/3)
= 1 - 0.05 ^ 1/3
F(t)=1-0.05 e ^ (p(30-t) with the condition F(0)=0
ReplyDeleteis the same as F(t)=1-0.05 ^ (t/30)
F(0)=0 leads to p= ln 20 /30
1-0.05 e ^ (ln(20)(30-t)/30) =
1 -0.05 x 20 ^ (1 -t/30)=1 - 1/20 * 20^(1-t/30) = 1 - 20 ^ (1-t/30 -1) = 1 - 20 ^ (-t/30) = 1 - 0.05 ^ (t/30)
so andy came to the same solution by solving a Differential equation, than other people did in another way.
This comment has been removed by a blog administrator.
ReplyDelete(2/3)*(0.95/3) is this the answer???
ReplyDeletei think lets relate time to distance (const speed 1km/min)so,
finding a car in 30 km is 0.95
if we fix 30km distance we can move 10km distance inside it
for a specific 30km and a specific 10 km in it. the probability of finding car is (0.95/3)=p
integrating the probability with distance gives
P= p*(20km/30km)
so the total probability is (2/3)*(0.95/3)