CareerCup

I was asked this question:

Imagine you want to build a standalone app. This app let's user see the N nearest ATMs within the range. You can assume that the app will show ATMs within some range(like 1km * 1km square). You have baked-in the offline map of the city in the app itself - which means the app already know the locations of all the ATMs in the city. Assume that ATMs and your location to be 2d cordinates(x, y). Also you have stored the location of all the ATMs in the app itself. You need to find the best and most efficient way to find the nearest ATMs within the range.

You don't have to give the logic to find the distance between two points. You need to tell how can you filter out soo many ATMs within the city for a given range. You can assume that the region for which you want to show the location of the ATMs be a square/rectangle. The app knows your location everytime.

So basically the problem is - how will you store those ATMs coordinates in the app so that the app at any point can filter out N ATMs for you if they lie inside the region.

My solution was to have sorted x coordinates and sorted y coordinates pre computed. Now in the sorted x coordinates, Find all the x coordinates that lie within the range of the region's x coordinates for which you want to find the ATMs. Repeat the same for y coordinates. Now find the intersection of both the result. This will give you the result. But interviewer wanted more optimized approach. Any idea how to do better?