Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Well I told that I will create a hashmap, with every cordinate and distance as key and count of eqidistance point as valus. then finally the key for the entry in Hash map with max count will be centre and distance for that hash map will be the radius of the circle. Then I was asked to code for the same.
Non optimum solution:
1) Consider any point and find the farthest point from this point.
2) Make this point as center and draw a circle with farthest point distance as radius.
Complexity: O(N)
Optimum soln:
1) Calculate Nc2: Distance between all pairs of points and find max distance.
2) Make one of these points as center and draw a circle with distance between two as radius.
Complexity: O(N^2)
What was your approach ?
My approach :
Time : O(n^3) .
- mkagenius April 11, 2012