Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Here is the solution to find lines are parallel, perpendicular or Intersecting lines
Example 1:
line1: points (–1, –2) and (1, 2)
line2: points (–2, 0) and (0, 4)
Answer => "Lines are Parallel!!"
Example 2:
line1: points (0, –4) and (–1, –7)
line2: points (3, 0) and (–3, 2)
Answer => "Lines are Perpendicular!!"
Example 3:
line1: points (–4, 2) and (0, 3)
line2: points (–3, –2) and (3, 2)
Answer => "Lines Intersects!!"
static void Main( string[] args)
{
decimal m1 = FindSlope(0, -4, -1, -7);
decimal m2 = FindSlope(3, 0, -3, 2);
if (m1 == m2)
Console.WriteLine( "Lines are Parallel!!" );
else if ((1 / m1) == (-m2))
Console.WriteLine( "Lines are Perpendicular!!" );
else
Console.WriteLine( "Lines Intersects!!" );
Console.ReadKey();
}
static decimal FindSlope( decimal x1, decimal y1, decimal x2, decimal y2)
{
return ((y2 - y1) / (x2 - x1));
}
My answer suggestion :
Equations of two lines:
A1x + B1y = C1
A2x + B2y = C2
To find the point at which the two lines intersect, we simply need to solve the two equations for the two unknowns, x and y.
double det = A1*B2 - A2*B1
if(det == 0){
//Lines are parallel
}else{
double x = (B2*C1 - B1*C2)/det
double y = (A1*C2 - A2*C1)/det
}
@BVarghese
I am unable to ascertain the correctness of your procedure, but if you are interested, you can take a look at Section 33.1 of CLRS (tberg.dk/books/Introduction_to_algorithms_3rd_edition.pdf), which has a nice topic on line intersection of line segments. It's a bit elaborate, so difficult to discuss it here.
But interviewer was asking about the equation for the line and solve with that. I was trying to tell a similar idea like in the normal line segment problem like @Apostle is pointing to.
If the question really asks for intersection of lines (as line extends to infinity both ways), then we just have to compare their slope. If slope is equal they will never intersect aka parallel otherwise they will overlap at some point.
But, I think question would be for intersection of line segment (both endpoints of line segment are fixed).
considering lines, not line segment we can have 3 cases for a given pair of lines
y=m1*x+c1
y=m2*x+c2
case1) lines do not intersect if both the lines are parallel to each other that is
m1=m2 and c1 != c2
case2)lines are collinear when m1=m2 and c1= c2 in this case there will be more than one point where line intersects(all the points on the line infinite)
case3) for all other case there will be exact one intersection point
xs=(c1-c2)/(m2-m1) and ys=m1*xs+c1 where (xs,ys) is intersection point..
Compare slope. If it's the same they are parallel.
- Noobie July 29, 2013