GOOGLE Interview Question || A Probability Puzzle || Hard Logic Puzzle
ฝัง
- เผยแพร่เมื่อ 19 มิ.ย. 2024
- GOOGLE technical interview puzzle : This puzzle is asked in the software or technical porgramming Google interviews. This video explains the questions or requirements and two different answers.
It's a hard logic riddle.
This interview puzzle has a mind blowing GOOGLE twist inside, so watch the complete video as you will see a smarter approach to solve this puzzle.
This Google interview question has got an intelligent answer that only a few people know.
PUZZLE :
A stick is broken at two random points. What is the probability the three pieces can form a triangle ?
Difficulty level : Hard
The points are randomly chosen independent of each other.
So it's possible that when you cut them at two random points, the pieces can form a triangle, but it's also possible they cannot not form a triangle.
So you've to find the probability that they form a triangle.
In this video, I will first explain a natural solution using the graph method.
And then I will explain a brilliant solution that can surprise even the interviewer, as very few people know about this solution.
Chapters:
00:00 Introduction
00:04 Google interview puzzle
01:03 Graph method solution
08:10 Out of the box answer
Google is known for asking tricky puzzles and hard riddles in the interviews. They check the optimization skills of a candidate with his approach of solving a puzzle. If a candidate has good optimization skills then it will benefit the organization in writing optimized programming code that eventually improves the response time of software applications and websites.
So if you are preparing for google interview questions for software engineer then you can watch all google puzzles on my channel.
Share puzzle and riddles : logicreloaded@gmail.com
Give a try to these challenging puzzles and riddles:
GOOGLE Interview Question || Puzzle : 12 Men On An Island || Hard Logic Puzzle
• GOOGLE Interview Quest...
Seemingly IMPOSSIBLE Fox Puzzle || Fox in a Hole || Asked in Google Interview
• Seemingly IMPOSSIBLE F...
Difficult Puzzle || 25 Horses Race || Asked in Google and Microsoft Interviews
• Difficult Puzzle || 25...
3 Children Ages Puzzle || Can you solve this mind blowing puzzle ?
• 3 Children Ages Puzzle...
Torch and 8 Batteries Puzzle || Think outside the box
• Torch and 8 Batteries ...
Ant & Honey Puzzle || Increase your logical thinking
• Ant & Honey Puzzle || ...
5 Pirates PUZZLE (Version 2) | 100 Gold Coins 5 Pirates
• 5 Pirates PUZZLE (Vers...
Building & Rope PUZZLE || Think outside the box
• Building & Rope PUZZLE...
Google Interview Puzzle | Poisonous Milk Bottle | Simple yet Tricky
• Google Interview Puzzl...
Gold Chain Puzzle || Beautiful Logic Puzzle || 149 links
• Gold Chain Puzzle || B...
Is it possible to catch the Thief ? || Quick and Tricky Puzzle
• Is it possible to catc...
Google Interview Riddle - 3 Friends Bike and Walk || Logic and Math Puzzle
• Google Interview Riddl...
GOOGLE Tricky Interview Riddle - 31 Dominoes on a Chessboard | Tricky Google question
• GOOGLE Interview Riddl...
![เก่งแต่ลับหลัง (FINSTA) - ส้ม มารี (Zom Marie) Ft. Punch 4EVE [Official Teaser]](http://i.ytimg.com/vi/Fvt0Wz1hfGY/mqdefault.jpg)
Depending on the wording of the question exactly, a better "out of the box" answer is 100% as it does not state that you need to lay the pieces end to end. Simply content 2 pieces end to end and then slide the third along one piece to guarantee a triangle at some point.
It becomes the "Some months have 30 days, some have 31, how many have 28?" line of logic in that you are not expressly constraining the end points.
Amazing approach
This was exactly my line of thought!
Awesome Solution! 2nd one was Mind Blowing!🔥
I think the reason is not enough to explain that the two situations are exactly the same in the Outside-of-the-box solution. Because we have to say about 'density' when we calculate the probability by calculating area. Although there is no problem, there are only a few explanations. if the length of h1 is fixed, the length of h2 and h3 can be anything between 0 and H-h1. If the length of h2 and h3 change, both illustrations' corresponding points will also change. In both illustrations, we can observe the possible locations of the corresponding point get bigger when the length of h1 gets smaller. It leads to the fact that the two situations have the same density.
The idea is very fresh and good to me. thanks
That was awesome!
It would be amazing if you start a series of solving puzzles from books like "Puzzles to Puzzle You" by Shakuntala Devi or any other similar books.
Would honestly love consistency on this channel.
Thanks Abhay, noted and highly appreciated your suggestion and will be more active now on :)
Adding 2 points to different halves a line which are no more than half the length apart is what this problem boils down to. First point is 100 % becsuse it can be anywhere 2nd point has to be in the other half so thats 50% then for second point to be within half length of first is also 50% so.prob is 1x 1/2x 1/2
Yes, Bro, I feel after watching this the neuron circuits inside my brain (if any) has become a lot orderly.👍👍👍
:D
Man, this is brilliant. Maths has great magic power.
Beautifully explained.
Quite an advanced problem. Loved the solutions. More subscribers to you 👍
Really tough riddle.
Thank you Sir.
Mind blowing 🙏🏻
I started studying the problem by assuming several points, equally spread along, where i can break the stick and determining number of cases the sticks can form a triangle. I started from 4 and went on to 6 and 8 points. Odd number doesnt work due to the fact that one point is in the middle and there is a lot of bordering cases (sum of two short lenghts is equal to the longest one).
I noticed that number of cases that can form a triangle (T) depends on the number of points (n). For case with n=4 (4 for half of stick, so 8 in total). For point 1 - 1 case. For point 2 - 2 options. For 3 - 3 opt. For 4 - 4 opt. I assumed it goes on. Total number of T is double of the sum (1+2+3+4) of these options. So for any number of points,it is double of sum of aritmetic row
T = 2*(n/2)*(n+1) = n*(n+1)
And number of all variants of the lenghts
V = V(2,2n) = 2n!/(2n! - 2)
For high number of n the probability yields to 0,25.
It was amazing!!
Both are mind blowing solution.
Easy proof by complement: Let x and y be the two cut positions of a with length 1. Assume a triangle can NOT be made. Then one side must be longer than half the stick, that is 1/2.
1. case: First side too long. x > 1/2, y > 1/2. Probability 1/2 * 1/2 = 1/4.
2. case: Third side too long. x < 1/2, y < 1/2. Probability 1/2 * 1/2 = 1/4.
3. case: Middle side too long, that is either
3a) x-y > 1/2, or 3b) y-x > 1/2.
3a) x > 1/2 and y < x - 1/2. Here x is random between 1/2 and 1, such that on average we have y < 3/4 - 1/2 = 1/4. Probability 1/2 * 1/4 = 1/8.
3b) x < 1/2 and y > x + 1/2. Here x is random between 0 and 1/2, such that on average we have y > 1/4 + 1/2 = 3/4. Probability 1/2 * 1/4 = 1/8.
In total the probability a triangle can NOT be made is 1/4 + 1/4 +1/8 +1/8 = 3/4, such that the probability a triangle CAN be made is 1/4.
Try to make more such videos consistently. This video was amazing 👍
wow! good job (second solution), so easy yet so efficient.
I learn so many things from your videos, very well explained and the animation used was superb sir 🙌👏👏
Thanks Darshan for the appreciation :)
Excellent! Very interesting.
nice. love the proof too
I just thought of how to place 2 points on a line. So since any side should be less than half of L, the point has to lie within one-half of the line, the probability of that is 1/2. Next, the other point should be placed such that the sum of the two pieces formed due to the two points should sum up to more than the 3rd side. The other point has to lie in the other half of the line, it cannot be on the same half as the 1st point was. The probability of it lying in the other half is 1/2. Therefore, the probability of forming a triangle becomes 1/2 * 1/2 = 1/4
I loved it 😁
Also, it was very well explained. Very clearly explained. 👏👏👏 Thank you 😇
Thank you sir for the appreciation :)
@@LOGICALLYYOURS Thank you, sir, for the great work that you did! 🙂
They didn’t ask me this in my interview 😂
Most Satisfying Solution of a tough Puzzle.
I don't usually hit the Like Button after watching, but this video Deserved getting it.👌👌👌
Thanks a lot Surya, that truly gave me an inspiration :)
Nice! I have a slight alternative solution by integrating conditional probabilities as that seems the easiest but it's good to know a couple basic methods, too
Really awesome solution!
a+b>c
a+b+c = 1
so c < 1/2 for all triangles, 1 can be substituted by any value
probability of c
Great work 🔥🔥 after a long time.....
Will be more active :)
@@LOGICALLYYOURS 😀😀
For the second solution it is not clear that "the cuts can be anywhere on the rod, with equal probability" => "the corresponding point in the equilateral triangle can be anywhere on its surface, with equal probability". If you don't show this, the proof is not sound.
I have a solution in my mind. To form a triangle, sum of any two sides must be greater than the third. Consider we cut the pieces from left to right. So the first cut must be at the left of middle point(To satisfy the condition). For this probability of cutting at the left of middle point is 1/2. Then we are left with a piece having the middle point. Now the condition for the second cut is that it must not be on the left of the middle point to satisfy the condition. For this second cut the probability to cut at the right of the point is 1/2. Overall probability is 1/4. Is this approach correct? If this is not correct, then point the place I am wrong? Expecting your response!!
Actually, To form a triangle sum of any two sides must be greater than the third.
@@shresthaasish sorry. Typing mistake. I will correct it.
Dhinesh, the approach is not correct bro… Reason: The probability of making the second cut at a specific point solely depends on your first cut. To verify your approach, just consider a Stick with only 11 breakpoints(BP). Solve from left side. If you make first cut at first BP, then the next cut can be only at 6th BP to form a triangle. In this case, to form a triangle, your first cut had the probability 1/11.. and second cut had the probability 1/10. Combined probability: 1/110 (simply multiply them). Now consider the next case where the first cut was made on the second BP (probability: 1/11). Second cut can be made on 6th and 7th BP to form a triangle.. so probability for this second cut (2/9). Combined probability : 2/99.
So, if you do it for all BPs, and add them up, you get a number close to 0.25 (not exactly.. but closer). If you consider 100 Breakpoints, you’ll get further closer to 0.25. If you consider infinite points, you’ll end up at 0.25 exactly.
Please let me know if this helped… or I’ll try to explain further.
@@LOGICALLYYOURS Thank you so much for your explanation bro. I am clear with it
Hi, I solved this in a similar way, a prerequisite of the solution is that a triangle can be made if and only if no piece may be 50% or more of the total length, hence if both cuts lie on the same side of the mid point a triangle cannot be made, as the length of the other side of the line will be 50% or more of the total. If 2 cuts are made randomly, they will both fall on the same side of the mid point in 0.5 of cases, hence this 0.5 proportion of cases do not lead to a solution. Setting this aside for now, the other 0.5 proportion of cases to consider is that both cuts lie on separate sides of the mid point, and whether the middle segment is greater than 50% of the total. In this case, if the point on the left is chosen randomly, if the distance between the furthest left edge and the cut on the left is the same or less than the distance between the mid point and the cut on the right, the middle line segment will be 50% or more of the length of the total line. The probability that this will occur is arbitrary, as both cuts could fall at any distance from the furthest edge of their respective sides with equal likelihood, hence if the two cuts are made on separate sides, the probability of the middle segment being 50% or more of the total is 0.5. This leaves the following probability sum, probability that at least one segment is more than 50% of the total= 0.5 (if both cuts fall on the same side) + 0.5*0.5 (if the cuts fall on separate sides) = 0.5 + 0.25 = 0.75. Finally, the probability that a triangle can be made = 1- the probability that at least one line segment is more than half of the total = 1 - 0.75 = 0.25
Why have we considered equilateral triangle? It can be any type of triangle. Wont the assumptions change it that case (forming equal triangles 1/4)? Am I missing something here.
U considered all bases to be equal and cancelled them off.. but that's the case in equilateral triangle only right
loved it
My reasoning was as follows:
The two cuts will be on the same side of the stick half the time, and on different sides half the time.
If they're on the same side, the parts can't form a triangle, because one piece will have half the stick plus a bit more.
If they're on different sides, the parts will form a triangle if (and only if) the middle part of the stick is less than half the total length.
The probability of this ranges smoothly from 0 (if the first cut is right on the outer edge) to 1 (if the first cut is right in the middle)---that is, an average of .5.
So the chance of being able to form a triangle is .5 (chance of the cuts being on opposite sides) x .5 (chance of the middle part being less than half the total length) = .25.
good puzzles
I'm a bit late on this, but I think your solution is wrong. In the problem, it is stated that the 2 points at which the stick is broken are random and independent of each other. However your whole reasoing is based on sticks lengths x and y being equaly distributed. I think however that this is not the case. However x and y depend on the points 1 and 2 in a more complicate way. Already the order of the points can change, and the length of y depends on both points. In essence, if you call p1 and p2 the coordinates of both points, than you would have x=min(p1,p2) and y=|p1-p2|
However these values are not really suitable for calculation. This is however not very practical for calculation. So you have to reason on p1 and p2 and this yields completely different calculations.
Hello Ammar,
Just wondering can we do it by this method too?
1)
--------------------------------------------------------------
This is our line.
2)-----------------------------------------|-----------------
Place the first cut anywhere after the middle point {as if we make the other cut anywhere (with only 1 exemption case that is covered latter) before the first cut,we are sure that a triangle is going to be formed}
This makes the probability of consideration of the point : ½ on the line.
2)You can place the second cut anywhere in the line now.
*CASE -1: Place it anywhere before the first cut but make sure that it's in a way such that the first two piece doesn't extend l/2 length each*
---------------|--------------------------|-----------------
The number of possible combinations will furthermore decreases the probability of the total event by ½.
*Case-2: Place the second after the first cut*
-----------------------------------------|---------|--------
In this case the triangle is not going to be formed as one side would be greater than l/2.
*So the total probability becomes ½ × ½ = 1/4*
This solution is simpler and faster, no need from any fancy "out of the box" approaches 👍👍
You're too awesome
There is one more technique
You add one break point between 1 and 2 in your figure say point 3. So you have 4 pieces. So you can slide that point 3 between 1 and 2 to make a quadrilateral but as this point hits 1 or 2 it makes a triangle it converges into a triangle. So the disappeared side was 1 out of 4 ie 1/4.
You can consider the fourth side as the closing error required for a quadrilateral.
I mean closing error for a triangle would be the same as the extra side to form the quadrilateral.
This is an absouloutely complicated, there are easier solutions. Do the first cut.. If we suppose its not exactly at half, its going to be closer than half to one point of the line.Lets say the length of the shortest distance to an end is x.
____ . ___________
|x
So if the second n ends up in the highlighted space(equal signs)
_____ . _____|======______
X half x
Then each part will be less than half. Thhe end of the equal signs are x far from the half. That means the probability to end on an equal sign is x/length. And each value of x have the same probability of happening and has to be less than half. Work it out and you get 1/4.
It’s not as simple as you might think. The first cut (except at the exact centre) is going to happen with 100% certainty. Imagine the first cut was very close to the left end. Then the remaining stick on the right side would need to have a second cut. Where all can you make the second cut to form a triangle? Well, it absolutely depends on the length of the left most piece. Try changing the length of the left most piece (by shifting the first cut slowly to right) then observe the second cut could not be easily generalised to ensure it forms a triangle.
You may record a video of your written solution with several cases, upload it on TH-cam and share the link with me (logicreloaded@gmail.com).
It might help me understand your perspective.
I really appreciate your efforts in making the comments section valuable.
Kelsey Houston-Edwards has already done this in her, now sadly defunct, Infinite Series channel:
th-cam.com/video/udxwP26gTwA/w-d-xo.html
Hey, thanks for sharing the link. She didn’t use the Viviani’s theorem though (using the altitude as the stick), rather she used the base as the stick. But it was good to know there is one approach :) thanks again !
@@LOGICALLYYOURS
Indeed, she used a different approach. Personally, I prefer hers because that required only a simple geometrical fact and thus eaiser to understand.
Vivani's theorem is a theorem built up on simpler geometrical facts (well, because you still need to prove it based on simpler facts).
Great one . But in second explanation are we only considering equilateral triangle and not others.
Wait bro…. That equilateral is not what we get with the stick. The triangle just shows a graph to represent areas.
@@LOGICALLYYOURS Thanks Ammar let me revisit the solution and once again great video with great explanation and we missed you.
50% ( my guess ) or something close to it
But the 2nd method is only for equilateral triangle???
To form a triangle it should be l1+l2>l3 and after breaking the stick three case arises l1+l2>l3, l1+l2
wtf how dumb are you
Do the interviewers give pen-paper? Asking genuinely
Yes they do. In fact you can ask for sufficient time. They won’t expect the complete solution till the end. Your approach would satisfy them as they know working out on the full solution takes time. I personally have faced some challenging puzzles during my interviews. They check the approach (which is what we call an Aptitude)
You interchanged x axis and y axis euations
U r genius man... My mind is blown ...Best YT channel..😱😱😱😱
Your comment made my day Ashish :)
One step method : Break stick in two parts. One part will be greater than another.
Chance of this is 1/2.. Now select any larger part and break again into two parts. Chance of selecting larger part is again 1/2.
Hence we will always form a triangle when we select larger part and break it into two.
Total probability = 1/2 *1/2 = 1/4.
Chance of getting one part greater than another when randomly broken is 1/3.
3rd chance is getting both the parts as equal 😁
Hemant… if you break a stick randomly, then the chance of getting two unequal pieces is close to 100% ( you’re considering only 50%). Imagine the stick has 11 breakpoints, to get unequal pieces your first cut can be at any of these breakpoints except 6th. So the probability of getting unequal pieces is 10/11…. which is closer to 100%. Now consider infinite breakpoints and you get the probability almost 100%.
@@LOGICALLYYOURS I am saying one part greater than another is 50%. For unequal it is indeed 100% minus one case when both are equal.
@logicallyyours, @hemantpandey123 - I’m pretty sure is 0.5 or 50% probability to make a triangle, 1st point is 100% to create 1 side greater than L/2, the 2nd point (chosen independently has a 50% chance of being located on same side of centre as point 1 and failing to result in a triangle by the 3 lengths, so 50% chance point 2 is on opposite side of centre than point 1 means 50% probability.
I still get 50%, probability of point 1 & point 2 being on same side of centre is akin to flipping heads then heads, however flipping tails then tails would also be same result and fail to result in triangle, You want to flip heads then tails, or tails then heads, there are 4 possible outcomes, 2 of which create triangle, a few marginally near zero probability scenarios of having a point land at zero or L (1 side becomes 0 length), or 1 point at exactly L/2, So marginally less than 50% - the probability math in video supposes you are choosing 3 lengths with equal probability of existence, and I’m pretty sure is the wrong dimension of the problem as you are choosing 2 points independently on a line…. Not 3 lengths on the stick (which is the result of choosing 2 points, creating result 1 dimension higher, but the probability rests with the points not the lines)…?
Definitely 50%, here’s the logic: Pick Point 1 at random - probability of it being on the stick is 100%, probability of it being at the ends or at exact middle is nearly zero. So it must be on either side A, or Side B. Now forget where that point is for a moment, because the 2nd point is picked ‘independently’, what is the probability that the 2nd point point is on 1 of the 2 sides, same as Point 1, nearly 100%, and probability of being at either end or exact middle is nearly 0%. So it exists as either a point on side A or B, just like the first point. So the probability of the points being located as AB or BA is 50% (opposite sides, and makes 3 lengths capable of forming a triangle), the only other 2 possibilities is they are located as BB or AA which, which is the other 50%, resulting in 1 side being greater than L/2, and does not form a triangle. So answer is probability approaches 50% due to very small near zero chance of either point landing in the 3 null locations (0, L/2, or L exactly).
I have one more way to sloved this ques can you give your instra then I can the solution through photo
A right angle ?
I have another easy solution for this
lets consider the length of the stick L = 9 in min possible case the lengths of possible sticks would be 2,3,4 according to the rules to form a triangle then the probability for those would be
possible ways of arranging 2,3,4 / P(2).P(3).P(4) = 6/4*3*2 = 1/4 😜
I solve this by out of the box at first glance m i a genius or something 😂😂
This problem is actually far, far easier than the video suggests:
If any piece is greater than 50%, there will not be a triangle.
If cut #1 and cut #2 are both more than 50% from the same original end, there will not be a triangle.
Cut one will achieve that half the time, as will cut two. Multiply the independent probabilities to get the answer of 1/4.
No because that is not the only condition the distance between cuts must also not be more than 50% length which you dont account for.
First cut will result nearly 100% in having 1 piece of length greater than L/2, its probability of cut 2 (chosen independently of 1) being on the opposite half as point 1, which is 50%) so answer is 50%
And if you ask real people to break real sticks, answer actually will be close to 100%. Because most people will first break the stick and then break the longer of 2 parts. No way points are going to be equally distributed, so if you want a full answer, it's 25%, but that's a horrible model if you try to solve a real problem.
Realizing no piece must be longer than 0.5L is half the challenge. Then,
Say point A lies at 0L. The probability B lies at exactly 0.5L approaches 0.
Say point A lies at 0.5L. The probability B lies between 0.5L and 1L approaches 0.5.
Realise this probability is a linear distribution for all points of A, and average.
simple solution
lets divide the line in three part :
possible cases of division
part 1 part2 part3
case1 :-
You don’t divide line in 3, you cut 2 times, so you chose 2 points on a line, the result is 3 lengths probability is based on point selection and is 50%
Unfortunately, you didn't prove that the area ratio is, in fact, the probability of selection. Shouldn't you state how you derived or used that with references? Better yet, you should have done a Monte Carlo Simulation that approaches this "statement" of probability and area ratio. In fact, just how are you suggesting that you play this 'game"?
The probability is 100%.
Why are u so inactive?
I apologise… I won’t give any excuse, rather I’ll prove the consistency now onward :)
Answer: There is zero probability of that happening.
Counter: Why do you think so ?
Answer: you never said if gravity is present and if it is what is the resultant acceleration and vector direction. Is it in 2d,3d, 4d or 11d ?
Counter: Are you stupid? It's obviously from top to bottom...
Answer: Less stupid than you since you missed to define that in your question.