Pinterest Interview Question
Software Engineer InternsCountry: United States
Interview Type: In-Person
Your method is same as calculating the distance between centre and the point and checking if it is < R
First calculate the distance between all the places with the centre i.e given longitude and lattitude.
Now whichever is equal to and less that the radius are the places needed
Precompute a grids from a fairly coarse to fairly fine resolution. When a search is made, choose the appropriate grid (based on the radius of the circle), and for the cell(s) that are inside the circle select the cells in subgrids which are part of the circle.
So for example, you might have the outer-most grid having cells which are 100x100km. If a search is made which goes across two of these cells, select both and then select the subgrids of size 50x50km, then the subgrids of 10x10km inside those until you get to the finest resolution. If the finest-resolution cell is completely inside the circle then select all places, else for those cells calculate all distances to the center (but there shouldn't be too many calculations since there will be relatively few fine-grained cells on the boundary, and relatively few places in each of those, as long as the grain is fine enough).
Here is the method that I thought :
- CodePredator May 01, 2013Maintain a sorted array of long//lat of all places, sorted first by longitude and second by latitude.
If we have to find all places from point (a,b) with in a radius of r.
1) find all the places within the longitude range a+r and a-r and latitude range b+r and b-r (Use Binary search on sorted array to find this range of places).
2) Now for these points use the expression (x-a)^2+(y-b)^2 -r^2 to decide whether they lie inside or outside the given radius.
a) if (x-a)^2+(y-b)^2 -r^2 > 0 it lies outside the given radius
b) if (x-a)^2+(y-b)^2 -r^2 < 0 it lies inside the given radius