Flipkart Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Just iterate through your location hash and for each coordinate check whether the coordinates follow the following formula
Consider my position to be (x,y)
Let the point under consideration be (x1,y1)
A given point will lie within or on a circle of radius r with center (x,y) iff
(x1 - x)^2 + (y1-y)^2 <= r^2
You can find the bounding rectangle for your position.
Check for lat and long that lie within the the bounding rectangle
for lat, long within the bounding rectangle check euclidean distance.
one Solution i think for this is:
1) Create a graph with [lat,long] as vertices and edges. Edge weight can be calculated as the distance between two vertices.
2) to find famous locations for a given [lat,long], take all edges whose weight is less than r (as given in question) and edge source/destination is a given[lat,long]
Time complexity will be O(N-1) where N = number of edges.
Pros: Search time will be less for any given [lat,long] as we stored the graph.
Cons: adding/removing new [lat,long] will take more time.
geohash the lat long, if the precision counts go for the entire range or else just index the first 8 bytes of lat/long, do a bird eye with radius expansion using geohash algorithm and you have the locations latlong, distance from the centre (provided latlong), take the latlong geohashes in the range, match against the indexed latlong geohash and you should have the places.. i guess.
- sanjay singh December 11, 2014