During an interview I was asked given the following: A real estate application that lists all houses that are currently on the market (i.e., for sale) within a given distance (say for example the user wants to find all houses within 20 miles), how would you design your application (both data structure and alogirithm) to build this type of service?
Any ideas? How would you implement it? I told him I didn't know becaue I've never done any geo-related stuff before.
Tell me more
×
Programmers Stack Exchange is a question and answer site for
professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
|
|
|||
|
|
|
They are probably after an answer mentioning spatial indexing, most likely by selecting a database that provides spatial indexing out of the box, but you might also get a few points by mentioning it can be implemented in the application itself if needed e.g. by implementing an R-Tree (might be handy if the DB selection is fixed for other reasons? but also demonstrates you know how spatial databases work). Spatial indexing will allow you to rapidly get a subset of locations that fit inside a search box, you can refine this further by calculating actual distance (if necessary, the rectangle alone may be good enough of course) for each one to give a true search circle/ellipse Given that distances are likely 20M or less you are probably OK assuming a flat earth to calculate distance though you will start to see noticeable errors toward the 20M end, if much larger ranges are needed accurately you would also need to start looking at better distance models for the globe e.g. Haversine distance there are also of course a myriad other details that could be discussed e.g. UI design, DB schema which could be whole topics in their own right |
|||||||||||
|
|
Whenever you are faced with a question like this and you simply do not have expertise in the problem domain it's good to do a couple things. First acknowledge that you don't have specific expertise in this problem domain. Second, explain how you would go about solving the problem.
Third, Always reduce problems like this down to their basic components. You know that locations on a map are 2-dimensionally distributed. You know that if you are given arbitrary x,y coordinates the distance to each coordinate from another coordinate is calculated by forming a triangle and solving for the unknown length. You hopefully also know that if you are asked to find all coordinates within a bounding box, you can do this simply by calculating the extents of the box you want to find and using simple greater than, less than logic along both axis. Last, I have never hired a developer that seemed to give up on questions. If I ask a question and the person says "I don't know" and doesn't even attempt to think through it verbally it gives me the impression they won't contribute to brainstorming sessions - which is critical at organizations that are writing software. |
|||||
|
|
This is probably obvious, but for many applications the poor man's slow solution may be fine. Have a table in a relational database that stores latitude and longitude. Query for all locations that have a latitude within 20 miles and a longitude within 20 miles. This gives you a bounding rectangle the size of the smallest bounding rectangle that contains the radius you really want to search (and ignores curvature of the earth as well). Then you take the set that's returned (by a query using indexes), and filter it down using an accurate calculation of distance. So, not efficient performance, but very efficient in time to develop. For many applications that might be a better choice. |
||||
|
|
|
Likely the easiest way is to use a quadtree to store the locations of your houses, assuming distributed in a 2D landscape. Searching should be fairly straightforward. If you're using a GIS-enabled RDBMS to store your stuff, then you really need not worry about that. See this question for some info on performance of the lead players. |
|||
|
|
