Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
9
of 9 vote

Let the given points which form a triangle are A,B,C and let the point be P if
Area(ABC) =Area(PAB)+Area(PBC)+Area(PAC) then the point P lie inside
the triangle , in this case P=(0,0).

- khunima April 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This will fail if P is located outside the triangle in some specific cases. Consider the triangle made of coordinates - (3,0)A ; (3,2)B ; and (0,2)C. Now, P(0,0) is outside the triangle ABC, but still the areas are a match, You need an extra check to see of the point P is inside the triangle; such as explained in the post below - about P being in the same side as one of A, B or C - when a line by other two points splits the plane

- Jay April 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, please disregard my post. I made a small mistake in calculation!!

- Jay April 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

For each point, test if the origin is on the line or on the same side as the current point when the plane is split by the line that the other two points make.

from collections import namedtuple

Point = namedtuple('Point', 'x y')
ORIGIN = Point(0, 0)

def contains_origin(points):
    for i in xrange(len(points)):
        p = points[i]
        rest = points[:i] + points[i + 1:]
        origin_position = above_or_below_or_on(ORIGIN, rest)
        if origin_position == 'on':
            return True
        elif origin_position != above_or_below_or_on(p, rest):
            return False
    return True

def above_or_below_or_on(point, rest):
    a = rest[0]
    b = rest[1]
    d = float(a.y - b.y) / (a.x - b.x) * (point.x - b.x) + b.y
    if point.y > d:
        return 'above'
    elif point.y < d:
        return 'below'
    else:
        return 'on'

if __name__ == '__main__':
    print(contains_origin([
        Point(1, 0),
        Point(0, 3),
        Point(-2, -1),
    ]))

- lemonedo April 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Seems the easiest way to do this would be to do some kind of radial sweep from the origin. Then moving from p1 to p2 and p3 you simply add up the angle between p1 and p2 then p2 and p3. If that angel is greater than 180 degrees then the origin must be in the triangle. If it equaled 180 then you must be on an edge. You would also immediately fail if you found 2 points on the same sweep line.

- Anonymous May 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Draw 3 lines PA, PB, PC, and add up the angles of APB, APC, BPC. If the value is 360, the orgin is inside the triangle.

- Clark Li May 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort the x-coordinates by considering all three points and get {x1, x2, x3} in sorted order.
Sort the y-coordinates by considering all three points and get {y1, y2, y3} in sorted order.
If for given point P(a, b), if (x1<= a <=x3) && (y1<=b<=y3), then the point lies within the triangle, else it lies outside

- shiva May 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Let the three points be
p1 = (x1, y1)
p2 = (x2, y2)
p3 = (x3, y3)

and the points are sorted in increasing order of x values, i.e. x1 <= x2 <= x3.

If the origin (0, 0) is inside the triangle then it must be the case that either

case 1:
x1 <= 0 <= x2

now use linear interpolation to obtain an equation y12(x), and y13(x). Where these are equations of line that pass through point P1 and P2, and P1 and P3, respectively.

Now check the following inequality:
y12(0) < 0 < y13(0)
or
y12(0) > 0 > y13(0)

the result is yes if either of the above is true, if not check case 2.

or case 2:
x2 <= 0 <= x3

now use linear interpolation to obtain an equation y23(x), and y13(x). Where these are equations of line that pass through point P2 and P3, and P1 and P3, respectively.

Now check the following inequality:
y13(0) < 0 < y23(0)
or
y13(0) > 0 > y23(0)


the result is the origin is inside the triangle if either of the above is true

- Anonymous June 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Let ABC be the triangle and P be any arbitrary point in 2D space.
The if P is inside the triangle ABC or not can be found by checking the signs of the following cross products:
AB X AP, BC X BP and CA X CP.
If the signs are same then it means the point is inside the triangle, o.w. it is outside the triangle.

For this question mark P as (0,0) and check for the signs of the above cross products.

- Anonymous September 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Let ABC be the triangle and P be any arbitrary point in 2D space.
The if P is inside the triangle ABC or not can be found by checking the signs of the following cross products:
AB X AP, BC X BP and CA X CP.
If the signs are same then it means the point is inside the triangle, o.w. it is outside the triangle.

For this question mark P as (0,0) and check for the signs of the above cross products.

- santosh sinha September 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

find xmax=max(x1,x2,x3),xmin=min(x1,x2,x3)
ymax=max(y1,y2,y3),ymin=min(y1,y2,y3)

find if 0 is in range(xmax,xmin),(ymax,ymin)

- mBk October 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The area calculating method is clever, but mathemtically more intensive.

basically, assume the points are p1, p2 and p3, and we need to check if t is inside the tri-angle. We need to check if t is on the same side of line p1p2 with p3, same side of p2p3 with p1 and same side of p1p3 with p2.

1. let p1=(x1, y1), p2=(x2, y2), p3=(x3, y3) and t(xt, yt)
2. let k12=(y2-y1)/(x2-x1), k23=(y3-y2)/(x3-x2), k13=(y3-y1)/(x3-x1)
3. if (yt-k12*xt)/(y3-k12*x3) > 0, (yt-k23*xt)/(y1-k23*x1) > 0 and (yt-k13*xt)/(y2-k13*x2) >0, we can conclude t is inside the tri-angle
4. in case any line segment is vertical to x axile (for example x1=x2), and k is undefined, check (xt-x1)/(x3-x1) instead

- Chuck April 16, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More