## Microsoft Interview Question

**Country:**United States

Is the solution C(n,3)? Choosing any 3 lines from n (assuming that all the lines intersect every other line) should give the number of triangles.

Generate your nC3 triples of lines. For each triple, check whether any pair is ||. If so, skip this combination. Otherwise ++n_triangles.

1. For lines they're parall, they should only count as 1

2. If we have n lines, after eliminating the parallel lines, we get k lines

3. The triages are k-2.

1 -Find the slope of all the lines and sort them to identify parallel lines

2 -So if out of n we found k parallel lines then we are left with n-k lines which will intersect each other

3- No of triangles formed by these n-k lines is C(n-k, 3) which is say N

4- (I am not 100% sure about this step)Now out of those k lines if I pick a line so now my number of triangle should be 2*N so I think for each parallel line I add my number of triangles gets double. I checked this on some base cases and it seems working but not sure if this logic is full proof or not.

Adding to your ans .

suppose say p, q, r no of lines are llel and lest say p + q + r = k,

then num of triangles = (n-k) *(n-k - 1)C2 + (p - 1) * (n - k)C2 + (q - 1) (n-k)C2 + (r-1)(n-k)C2

= (n-k)c2 * (k - 2)

Desginate each line by a 2-tuple {startpt, endpt}

Sort by startpt.

Sort by end pt.

Do a O(n^2) forward pass of the startpt sorted set to find if pt i intersect with any of pts 0 <= j < i. If there are intersections save them in a set.

Do a O( n^2 ) reverse pass of the end pt sorted set to find if pt i intersect with any of pts i < j <= n-1. As before save any intersections in a set

Observation a triangle is possibly formed if set 1 has members like {1,2} while set 2 has members like {2,3}. So for element in set 1 do a scan of set 2 searching for these matches and then checking if they form a valid triangle.

O(n^2) , i think we can make the last step nlg n but creating sets 1 and 2 require n^2.

1. hash each line by slope and increment count for slope

2. max possible triangles = n C 3

3. for each slope having >1 count (i.e. > 1 lines with same slope) let x be number of lines with same slope. Then number of triangles which can't be formed because of parallelism of these x lines is equal to

(n-x) * (x C 2) + (x C 3)

4. Repeat process for all slopes and deduct exclusion count from n C 3

I think nc3 should be the answer when there are points in plane and not n lines. i can't think of scenario to create 4C3 (4) triangles with 4 lines.

1. let p1, p2,...pk be the parallel lines. for all parallel lines, we have to consider 1 line.

2. actual number of intersecting lines are

c = n-k (1 for p1, 1 for p2 and so on for pk)

3. triangles for c lines are c-2

4. now with each set of parallel lines, we can create the traingles, so final count is

(c -2 ) + (p1-1) + (p2-1) + ... + (pk-1)

please note that it ignores the smaller triangles as part of bigger triangles...

hope i'm clear

I think nC3 is the scenario for triangles for n points in plane and not lines. ex: i don't know how to create 4C3 triangles from 4 lines.

1. let p1, p2, ...pk be the set of parallel lines. for each set, we have to consider one line.

2. actual count of lines to be considered is:

c = c-k (1 for each pi where i = 1...k)

3. with c lines, traingles are c-2

4. now each set of parallel line, let pi be involved in formation for qi number of traingles,

final count = (c-2)+ q1(p1-1) + q2(p2-1) + qn(pn-1)

NOTE: this doesn't consider small traingles being part of bigger triangles

I think nC3 is the scenario for triangles for n points in plane and not lines. ex: i don't know how to create 4C3 triangles from 4 lines.

1. let p1, p2, ...pk be the set of parallel lines. for each set, we have to consider one line.

2. actual count of lines to be considered is:

c = c-k (1 for each pi where i = 1...k)

3. with c lines, traingles are c-2

4. now each set of parallel line, let pi be involved in formation for qi number of traingles,

final count = (c-2)+ q1(p1-1) + q2(p2-1) + qn(pn-1)

NOTE: this doesn't consider small traingles being part of bigger triangles

I think nC3 is the scenario for triangles for n points in plane and not lines. ex: i don't know how to create 4C3 triangles from 4 lines.

1. let p1, p2, ...pk be the set of parallel lines. for each set, we have to consider one line.

2. actual count of lines to be considered is:

c = c-k (1 for each pi where i = 1...k)

3. with c lines, traingles are c-2

4. now each set of parallel line, let pi be involved in formation for qi number of traingles,

final count = (c-2)+ q1(p1-1) + q2(p2-1) + qn(pn-1)

NOTE: This doesn't consider small traingles being part of bigger triangles

I think nC3 is the scenario for triangles for n points in plane and not lines. ex: i don't know how to create 4C3 triangles from 4 lines.

1. let p1, p2, ...pk be the set of parallel lines. for each set, we have to consider one line.

2. actual count of lines to be considered is:

c = c-k (1 for each pi where i = 1...k)

3. with c lines, traingles are c-2

4. now each set of parallel line, let pi be involved in formation for qi number of traingles,

final count = (c-2)+ q1(p1-1) + q2(p2-1) + qn(pn-1)

NOTE: This doesn't consider small traingles being part of bigger triangles

I think nC3 is the scenario for triangles for n points in plane and not lines. ex: i don't know how to create 4C3 triangles from 4 lines.

1. let p1, p2, ...pk be the set of parallel lines. for each set, we have to consider one line.

2. actual count of lines to be considered is:

c = c-k (1 for each pi where i = 1...k)

3. with c lines, traingles are c-2

4. now each set of parallel line, let pi be involved in formation for qi number of traingles,

final count = (c-2)+ q1(p1-1) + q2(p2-1) + qn(pn-1)

NOTE: This doesn't consider small traingles being part of bigger triangles

Here you go :)

Code is in C# .Net

public class Point

{

public double x;

public double y;

public Point(double _x, double _y)

{

x = _x;

y = _y;

}

}

class PointComparer : IEqualityComparer<Point>

{

public bool Equals(Point x, Point y)

{

return x.x == y.x && y.y == x.y;

}

public int GetHashCode(Point x)

{

return 0;

}

}

public static int TriCounter()

{

List<double[]> Lines;

double[] Line1 = new double[2] { 0, Math.PI / 2 };

double[] Line2 = new double[2] { 0, 0 };

double[] Line3 = new double[2] { 10 * Math.Sqrt(2) / 2, - Math.PI / 4 };

double[] Line4 = new double[2] { 5 * Math.Sqrt(2) / 2, - 3 * Math.PI / 4 };

Lines = new List<double[]>();

Lines.Add(Line1);

Lines.Add(Line2);

Lines.Add(Line3);

Lines.Add(Line4);

HashSet<Point> intersection = new HashSet<Point>();

for (int i = 0; i < Lines.Count; i++)

{

for (int j = 0; j < Lines.Count; j++)

{

if (j != i)

{

double r1 = Lines[i][0];

double r2 = Lines[j][0];

double theta1 = Lines[i][1];

double theta2 = Lines[j][1];

double yIntersection = ((r1 / Math.Cos(theta1)) - (r2 / Math.Cos(theta2))) / (Math.Tan(theta1) - Math.Tan(theta2));

double x1 = (r1 - yIntersection * Math.Sin(theta1)) / Math.Cos(theta1);

double x2 = (r2 - yIntersection * Math.Sin(theta2)) / Math.Cos(theta2);

if (Math.Abs(x1 - x2) < 0.5)

{

yIntersection *= 1000;

yIntersection = (int)(yIntersection);

x1 *= 1000;

x1 = (int)(x1);

yIntersection /= 1000;

x1 /= 1000;

if (Math.Abs(yIntersection) < 0.00001) yIntersection = 0;

if (Math.Abs(x1) < 0.00001) x1 = 0;

if (!intersection.Contains<Point>(new Point(x1, yIntersection), new PointComparer()))

intersection.Add(new Point(x1, yIntersection));

}

}

}

}

int triCounter = 0;

for (int i = 0; i < intersection.Count; i++)

{

for (int j = 0; j < intersection.Count; j++)

{

for (int k = 0; k < intersection.Count; k++)

{

if (i != j && j != k)

{

Point first = intersection.ElementAt<Point>(i);

Point second = intersection.ElementAt<Point>(j);

Point third = intersection.ElementAt<Point>(k);

if (isOnSameLine(Lines, new double[] { first.x, first.y }, new double[] { second.x, second.y }) &&

isOnSameLine(Lines, new double[] { first.x, first.y }, new double[] { third.x, third.y }) &&

isOnSameLine(Lines, new double[] { third.x, third.y }, new double[] { second.x, second.y }))

{

triCounter++;

}

}

}

}

}

return triCounter / 3;

}

public static bool isOnSameLine(List<double[]> Lines, double[] point1, double[] point2)

{

for (int i = 0; i < Lines.Count; i++)

{

double y1 = Lines[i][0] * point1[0] + Lines[i][1];

double y2 = Lines[i][0] * point2[0] + Lines[i][1];

if (y1 == point1[1] && y2 == point2[1])

{

return true;

}

}

return false;

}

Assuming no 2 lines are parallel we get t = C(n,3) triangles.

- CodeMyCode December 17, 2011Now find the slopes of all lines.

If k lines have same slope, we need to reject p triangles where p can be calculated.

p = C(k,3) + C(k,2)*(n-k)

Find the summation of p for all such subsets of same slope

Triangles = n - Sum(p)