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
Answer

Interview Answer

4 Answers

11

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
0

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
0

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

Add Answers or Comments

To comment on this, Sign In or Sign Up.