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.
Add a comment
|
4 Answers
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
-
At 20 miles, the errors due to a flat earth model will be negligible. Anyway, when a user wants to see a list of houses within 20 miles of his office, he doesn't care if a house that is 20 miles and 10 yards away is included in the results. Jun 6, 2012 at 19:13
-
1indeed, and if a few false positives aren't important then you may as well skip the actual distance calculation altogether and just return the MBR– jk.Jun 6, 2012 at 20:40
-
One thing I am curious about: given the vast number of homes for sale, do companies (such as Zillo maybe?) store it all in a db and just keep selecting from it? I imagine that'd be a huge performance hit and it'd be much faster to store it all in memory with a graph representation - maybe matrix or adjacency list and use distance algorithms to find nearest homes. What do you think? Jun 7, 2012 at 5:39
-
@paulsmith I don't know, but I strongly suspect it is in a spatial DB, a spatial DB will probably use a graph representation internally anyway (most likely an R-Tree as discussed, but there are other options) the key is being able to select only the items in a minimum bounding rectangle in the first place– jk.Jun 7, 2012 at 11:09
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.
Although I don't have specific experience when working with geographical search I am confident there are well documented algorithms and existing technologies to solve the problem. I would explore these to gain knowledge of common solutions that are available to me and make a choice about implementation based on the requirements of the project.
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.
-
-
@Ben, I definitely agree with all the things you mentioned, however because the interviewer explicityly said before the session began that it is okay to say you do not know, I just followed his instructions and told him upfront that I didn't know :) Jun 7, 2012 at 5:37
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.
