Amazon Interview Question: Given a set of points (x,y) a... | Glassdoor

## Interview Question

Software Development Engineer Intern Interview

# Given a set of points (x,y) and an integer "n", return n

number of points which are close to the origin
Tags:
technical, algorithm

12

Step 1: Design a class called point which has three parameters
int x
int y
int distance

Step 2: For all the points given, find the distance between them and origin

Step 3: Store the values in a binary tree

Step 4: Heap sort

and print the first n values from the binary tree

Interview Candidate on Mar 17, 2014
1

An alternate solution would be to check for points at each radius going outward, starting from the origin. This would be more efficient in a scenario where there are millions of points, and highly clustered data (star maps for example).

janac on Feb 19, 2015
1

Adding all elements first is a terrible method because if n is very large the sort will take a long time. You can store the first n integers in a max heap. Then in O(1) time check if each of the remaining elements is less than the max value in the heap. If it is, insert it in the heap, removing the max value. If it isn't move on.

Anonymous on Feb 8, 2017
0

Also, if you havent sorted the points, how are you supposed to check in outward radius?

Anonymous on Feb 8, 2017
0

define points as a list of points of the form [n points of the form [x,y]]
First pass:
- initial state: points[]
- action: to translate the points into the Euclidian Distance between the point and the origin.
-output: translatePoints = [n values of (Euclidian_Distance, [x,y])]

Second pass, sort translatePoints by the Euclidian_Distance values from lowest to highest.

Third pass, get the top 5 from the list of points.

Anonymous on Jun 10, 2017