## Facebook Interview Question

Software Engineer / DevelopersThe first two points selected on a circle do lie in a semicircle (name it as first). The third point could either be in this semicircle (the first) or the other one (name it as second). In case if the third point lies in first semicircle (50% probability) then it forms obtuse angled triangle. In case if the third point lies in the second semicircle (50% probability) then it forms acute angled triangle.

So far so good. If the third point is diametrically opposite to either first point or second point then it forms right angled triangle. The probability of this is almost neglible. Please correct me if I am wrong. My email id is kishore.jinka@gmail.com

You're very near to justice!

Lets assume discrete case when circle consists of 360 points.

All cases: 360 cases of falling first point, 359 for second and 358 cases for third = 360*359*358 - total cases of trianles.

Right-angled triangles (2 points must lay on diameter): 360 cases for the first point, 1 case for the second point and 360 for the third = 1*360*360.

Acute angled (two points must lay on one semicircle and third on the opposite): 360*359*179 (the same number for obtuse).

100/360 ~= 0,28% (lets include degenerate cases of triangles to point or line) - even not a half of percent for right angled

(360*359*179)*100/(360*359*358) = 17900/358 = 50% for acute or obtuse type.

And that's only for discrete case!!

For more exact estimation I think one should write a function based on combinatoric combinations and give it as argument some big number as power of discretezasion

In case of right triangle, the last point would have only 358 options available as all the points chosen to form a triangle should be distinct.

"In case where a circle consists of 360 points"

That is already wrong. A circle consists of infinite points and makes a big difference...

It is so much easier to explain.

1) Note that the problem is symmetric, so we can pick one anchor point for the angle in question.

2) Note that rectangular is impossible. This requires three points with absolute exact coordinates. The probability for that to happen is zero! You may come close but it will NEVER "be" rectangular... It is like asking for the probability for a random real number in [0,1] of R to be sqrt(2)... It just never happens.

3) There are three possible right angles, which are symmetric again, so we restrict even further by only allowing the legs of the anchor point to vary by 180 (-90 to +90) degrees each. This gives a unique family of triangles, which by rotational symmetry extends to the defined problem.

4) We can rotate the leg around the anchor point by the above defined degrees of freedom while maintaining the rectangle.

Thus it follows that <90 and >90 are equally likely... That's basically it.

the points are picked up at random so the outcome of each point is independent of one another .. as such it would not be correct to first pick two points and the decide if the the third point lies in one semi sphere or the other .. however, once all the three points have been picked, it is certain that the outcome would be either one of the two (ignoring the right hand triangle case) : either all three lie in the same semi-sphere or two lie in the same semi-sphere. We can compare this to a coin toss problem, where we independently toss three coins and see the outcome. In this case, the two semi-spheres depict H or T. and the total outcome space is TTT,HHH, THT, HTH, TTH, HTT, HHT, THH. We can now deduce that the probability of obtuse angle triangle (TTT, HHH) is 2/8 and prob of acute angle triangle (the other cases) is 6/8.

From what I understand you assume that each of your outcome has the same probability, which I don't think is true.

this solution is wrong. if you predefined H and T, then HTT or HHT can form a obtuse triangle if the three points are close to each other.

no no no no

right angle = 0

acute and obtuse are both 1/2

0>x>pi/2 & pi/2>x>pi.

The semi-circle is split in half on the unit circle into these two spaces ... 1/2 & 1/2. Assuming infinite distribution a right angle will always be 0.

right : 0+

acute : 0.25-

obtuse : 0.75-

Semicircle formed by first two points can cover min 50% to max 100% of the points on the circle based on their position on the circle. But never less than 50%. On an average 75%. Third point can be any point on the circle, it means third point will be on the semicircle for about 75% times.

Hi...I am not sure how people come up with 1/4 & 3/4 probabilities. Do this exercise on paper. Draw a circle. Select point1 at random. Select dummypoint1 which is diametrically opposite to point1. That means first join point1 and center of circle. Then extend this line from center to touch the other end of the circle. This would touch the circle at dummypoint1. Now you see two semi circles. Select point2 at random. It would lie in one of these two semi circles. Upto here there is no question of probability. Point two would lie in one of the two semi circles for sure (100%). Erase dummypoint1 and also the diameter draw to show it. Now draw a line joining point1 and point2. Draw a diameter parallel to this line joining point1 and point2. Now the circle is again divided into two semi circles. Select point3 at random. If it lies in the semi circle containing point1 and point2 then these three points would form an obtuse angle triangle. The probability of point3 being present in the same semi circle as point1 and point2 is 50%. If the point3 lies in the opposite semicircle then the three points would form an abtuse angle traingle. The probability of point3 being present in the opposite semicircle is 50%.

sorry...in case the third point lies in the opposite semicircle the three points would form acute angled triangle. sorry for the type mistake earlier.

You were wrong when you wrote, "If the point3 lies in the opposite semicircle then the three points would form an acute angle triangle." (Here, I have corrected the spelling mistakes). If you draw an example in which point1 and point2 are quite close together, it is easiest to see your mistake. Try it.

Specifically, if point3 is in the opposite semicircle, it might or might not form an acute triangle, depending (respectively) on whether it does or does not lie between the far corners of the inscribed rectangle that other writers have referred to.

First is obviously 0.

Second is 1-third.

So for the third: Take any 2 of the 3 points of the random triangle, and make the obvious rectangle you can make with those 2 and the other 2 points on the "other" side of the circle. Whether the triangle is acute or obtuse depends on which of the 4 arcs made by those 4 points lie. If the 4 points make a square, the likelihood is 1/2. For every "fat" rectangle there is a corresponding "skinny" rectangle, so the likelihood is 1 (i.e. for every rect that yields a probability p for acuteness, there is one that yields p for obtuseness).

Why first is obviously 0. I could draw many right angles inside a circle. And, how second is 1/3? Explanation would be appreciated.

First is 0, because the probability of uniformly picking any real number from any continuous interval (with more than 1 point) is 0. What is the point of picking 0.5 from [0,1], for example? It is 0.

For the second, I didn't mean 1/3. I meant the prob is 1 minus the result of question 3. Sorry for being unclear, I should have seen that coming.

And to elaborate on the first point, you said that there are infinitely many right angled triangles in the circle, which is exactly right. Just pick any random base for a triangle, now pick the third point. The third point can go to a continuem of infinitely many points, only 2 of which make a right triangle. 2/infinity=0

Lets assume radius=1, circumference=2*pi

Lets select first point randomly.

For second point, using symmetry, can fall onto a semicircle, at anywhere from 0 to pi distance from first point.

lets assume second point is at x distance, and its length is dx.

probability of point getting selected=dx/pi.

Now for if third points falls on the smaller side (length which is x) it will be acute angle triangle else obtuse.

acute angle probability = x/(2*pi).

acute angle probabilty at this point= dx * x/(2*pi*pi)

total acute angle probability can be calculate by integrating above from 0 to pi.

which will be = 1/4.

obtuse angle probability=1-1/4=3/4

Sorry, probability for acute will be higher, so above calculation is for obtuse angle.

Correct probabilities:

Right:0

Acute:3/4

Obtuse:1/4

Why the probability for right angled triangle is Zero. If u select two diametrical opposite points ..and the third point any where in the circle..the triangle formed will be Right Angled...

Let there be total n pixels or points.

If we assume that the width of each pixel is 'x' and x tends to 0, then:

n = 2.pi.r/x

So number of ways of making a Right Angled Triangle = 2/infinity = 0 (as explained earlier).

Now, we choose 2 points randomly.

Let us assume that the angle made by the 2 chosen points with the center = theta.

Therefore, Number of Pixels on Acute Side = (2.pi.r/x - pi.r.theta/180.x)

And number of Pixels on Obtuse side = (pi.r.theta/180.x)

And x tends to 0.

So, P(Acute) = Ways of choosing a pixel on acute side / Ways of choosing 3 pixels in the circle

As written earlier, total pixels = n = 2.pi.r/x

P(Acute) = lim x->0 C(n - pi.r.theta/180x, 1) / C(n , 3)

Where C is the 'combination' symbol in combinatorics (equivalent to writing nC3)

So replace n by 2pi.r/x, take out all the constants and apply L'hospital Rule.

We get the answer as 1/2.

Hence P(Obtuse) = 1-1/2 = 1/2.

This is a limit problem because of the trade off between n (total number of pixels) and x (size of each pixel) where n tends to infinity and x tends to 0.

Hope the solution is clear. If any doubts, mail on at[dot]whitemagic[at]gmail[dot]com

I think all of your understanding of problem is wrong.

The 3 points are randomly selected, so all 3 points can fall in same semi circle, when you add 3 points in one half of circle, it forms obtuse triangle.

There is no restriction that, once you select a point, second will be diametrically opposite.

Guys .... there are only 3 types of triangles differentiated based on angles .... acute , obtuse and right angled so ... the dnt confuse ua self wid semi circles or sme thg .... answer is 1/3 for all !!!!

The probability according to me is:

For right angled triangle: 2/359

For acute: 178/359

For obtuse: 179/359

Assuming there are 360 points on the circle at one degree away the chances of each of the above cases happenin are(neglecting r as it will be cancelled):

Right=360*358*2

Acute=360*358*178

Obtuse=360*358*179

The probability according to me is:

For right angled triangle: 2/359

For acute: 178/359

For obtuse: 179/359

Assuming there are 360 points on the circle at one degree away the chances of each of the above cases happenin are(neglecting r as it will be cancelled):

Right=360*358*2

Acute=360*358*178

Obtuse=360*358*179

Total no. of triangles possible : 360C3(i.e. (360*359*358)/6)

I think answers are:

For right angled triangle: 3/359(select a pair of pts.(end pts. of a diameter)in 180 ways and selecting the 3rd pt. in 358 ways. So, required probability is (180*358)/((360*359*358)/6) which is 3/359.

For acute: 178/359(select 1st pt. in 360 ways, 2nd in 358 and 3rd in 178(because pt opposite to 2nd pt. cannot be taken as well). Multiply all 3 and divide by 6(because ordering among pts. is not important))

For obtuse: 178/359(similar explanation as above)

It should not be 1/4 and 3/4. Should be 1/2,0,1/2. Consider the following solution :

Event A = Point A lies in the same semi circle as B and C.

Event B = Point B lies in the same semi circle as C.

P(Obtuse) = P(A) * P(B)

We are assuming that C can be randomly placed.

Now P(B) = 1 AND NOT 1/2, because no matter where we place B, it will always be inside a semicirle containing C. They may become end points of a diameter, otherwise they will always form a chord. Now A can be placed in either of the two semi circles leading to probability 1/2. Hence P(A) = 1/2 and P(Obtuse) = 1/2 resulting in P(Acute) = 1/2.

0 1/4 3/4

Denote the first two points A and B that make the longest edge of the triangle, the third one is C, and O is the center of the circle. Also let the circumstance of the circle to be 1, the shorter curve AB is x, where 0<x<=1/2.

First, the probability that edge AB are the diameter, where x=1/2 is 0, so the prob for right angle triangle is 0.

Second, to make an obtuse triangle, and given the assumption that AB is the longest edge, C can only lie on the shorter curve AB on the circle. Otherwise AB will not be the longest edge or ABC is not an obtuse triangle. This gives the possibilities of

2*int_{x=0}^{1/2} x = 1/4, where the factor of 2 is due to symmetry.

Third, to make an acute triangle, C can be only chosen under the condition that angle AOC < angle AOB, and angle BOC < angle AOB. Otherwise, AB will not be the longest edge. Translated to the curve lengths, given shorter curve AB = x, we have 1-2x < curve AC < x. So x should be greater than 1/3 and the length of possible C, given B, is

x - (1-2x) = 3x-1.

The total possibilities are

2*int_{x=1/3}^{1/2} 3x-1 = 1/12, where the factor of 2 is due to symmetry.

So the possibilities of obtuse and acute triangles are 1/4:1/12 = 3:1. So the probabilities for them are 3/4 and 1/4 respectively.

monte carlo is pretty handy for problem like this. here is a python implementation, and returns the same answer as many have posted: 0 for right triangle, 1/4 for acute, and 3/4 for obtuse.

```
import random, math
NumTrial = 10000
NumRight = 0
NumAcute = 0
NumObtuse = 0
xpos, ypos, dist, angle = [[0,0,0],[0,0,0],[0,0,0],[0,0,0]]
for i in range(NumTrial):
for j in range(3):
theta = 2*math.pi*random.random()
xpos[j] = math.sin(theta)
ypos[j] = math.cos(theta)
for j in range(3):
if j < 2:
dist[j] = math.pow((math.pow(xpos[j]-xpos[j+1],2)+math.pow(ypos[j]-ypos[j+1],2)), 0.5)
else:
dist[j] = math.pow((math.pow(xpos[j]-xpos[0],2)+math.pow(ypos[j]-ypos[0],2)), 0.5)
a,b,c = dist[0],dist[1],dist[2]
angle[0] = math.acos( (math.pow(a,2)+math.pow(b,2)-math.pow(c,2)) / (2*a*b) )*180.0/math.pi
a,b,c = dist[1],dist[2],dist[0]
angle[1] = math.acos( (math.pow(a,2)+math.pow(b,2)-math.pow(c,2)) / (2*a*b) )*180.0/math.pi
a,b,c = dist[2],dist[0],dist[1]
angle[2] = math.acos( (math.pow(a,2)+math.pow(b,2)-math.pow(c,2)) / (2*a*b) )*180.0/math.pi
if angle[0]==90 or angle[1]==90 or angle[2]==90:
NumRight += 1
elif angle[0]<90 and angle[1]<90 and angle[2]<90:
NumAcute += 1
else:
NumObtuse += 1
print 'Prob for right triangle is ', float(NumRight)/NumTrial
print 'Prob for acute triangle is ', float(NumAcute)/NumTrial
print 'Prob for obtuse triangle is', float(NumObtuse)/NumTrial
```

I worked it out to be 0 (right angled), at most 1/4 (acute) and at least 3/4 (obtuse);

let A,B,C be points on a circle R with radius 1, centered on the origin O

Without loss of generality, We choose A to be the point with the largest angle, and we place A at (1,0) : (note we can always do this because, we can always relabel the 3 points and rotate the 3 points on the circle, without changing the angles in the triangle)

since A, B & C are uniformly distributed, we can describe the points as angles (a,b,c) between the point, the origin and the positive x-axis, more over a,b,c is also uniformly distributed. now label the 3 points such that c<a<b.. rotate the circle such that A lies on (1,0) (note that you can do that because you can always relabel the points and rotate the circle without changing the angles in the triangle). Note that b is uniformly distibuted between 0 and pi , and c is uniformly distributed between -pi and 0

mark a line OB and mark B' on the opposite side of the triangle. Observe that the angle of B' is b - pi , also observe that if c > b-pi then the triangle is obtuse, and if c < b-pi the triangle is acute. rearranging we have b-c < pi ;

b-c gives us a triangular distribution between 0 and 2pi with the mode at 0. and integrating the pdf between 0 and pi to find the probability of an obtuse triangle gives us 3/4

Probabiliy that 3 points will be on the same semi circle is 1*1/2*1/2 . 1 initially because it doesn't matter which point you pick, after that the next to points are relative to the first point.

Probability that the second 2 points are on different semi circles is 1-probability that they are on the same semi circle.

Guys .... there are only 3 types of triangles differentiated based on angles .... acute , obtuse and right angled so ... the dnt confuse ua self wid semi circles or sme thg .... answer is 1/3 for all !!!!

0,1/4,3/4

- lowiq3 February 22, 2012randomly choose the first two points A and B, they determine a string (A,B)

C and D are the centralsymmetric points of A and B, in order to have an acute triangle, the third point has to sit somewhere on the shorter arc determined by C and D.

Use the law total probability and integration, we get the probability of getting acute triangle is 1/4.