Häuser in einem Umkreis finden

Während eines Interviews wurde ich wie folgt gefragt: Eine Immobilienanwendung, die alle Häuser auflistet, die derzeit auf dem Markt sind (dh zum Verkauf stehen), innerhalb einer bestimmten Entfernung (zum Beispiel, wenn der Benutzer alle Häuser innerhalb von 20 Meilen finden möchte), Wie würden Sie Ihre Anwendung (sowohl Datenstruktur als auch Alogirithmus) entwerfen, um diese Art von Service zu erstellen?

Irgendwelche Ideen? Wie würden Sie es implementieren? Ich sagte ihm, ich wüsste es nicht, weil ich noch nie geo-bezogene Sachen gemacht habe.

Sie befinden sich wahrscheinlich nach einer Antwort, in der die räumliche Indizierung erwähnt wird , höchstwahrscheinlich durch Auswahl einer Datenbank, die sofort eine räumliche Indizierung bietet. Sie können jedoch auch einige Punkte erhalten, wenn Sie erwähnen, dass sie bei Bedarf in der Anwendung selbst implementiert werden kann, z. B. durch Implementierung eines R. -Baum (kann nützlich sein, wenn die DB-Auswahl aus anderen Gründen festgelegt ist? Zeigt aber auch, dass Sie wissen, wie räumliche Datenbanken funktionieren). Durch die räumliche Indizierung können Sie schnell eine Teilmenge von Positionen abrufen, die in ein Suchfeld passen. Sie können dies weiter verfeinern, indem Sie die tatsächliche Entfernung berechnen (falls erforderlich, kann das Rechteck allein natürlich gut genug sein), damit jede einzelne eine echte Suche ergibt Kreis / Ellipse

Angesichts der Tatsache, dass Entfernungen wahrscheinlich 20 m oder weniger betragen, ist es wahrscheinlich in Ordnung, eine flache Erde anzunehmen, um die Entfernung zu berechnen, obwohl Sie gegen 20 m merkliche Fehler bemerken. Wenn viel größere Entfernungen genau benötigt werden, müssten Sie auch nach besseren Entfernungsmodellen suchen für den Globus zB Haversine Distanz

Es gibt natürlich auch eine Vielzahl anderer Details, die besprochen werden könnten, z. B. UI-Design, DB-Schema, die ganze Themen für sich sein könnten

Immer wenn Sie mit einer solchen Frage konfrontiert sind und einfach kein Fachwissen in der Problemdomäne haben, ist es gut, ein paar Dinge zu tun.

Zunächst erkennen an, dass Sie nicht spezifisches Know - how in diesem Problembereich verfügen.

Zweitens , erklären , wie Sie über die Lösung des Problems gehen würde.

Obwohl ich keine besonderen Erfahrungen mit der geografischen Suche habe, bin ich zuversichtlich, dass es gut dokumentierte Algorithmen und vorhandene Technologien gibt, um das Problem zu lösen. Ich würde diese untersuchen, um Kenntnisse über gängige Lösungen zu erlangen, die mir zur Verfügung stehen, und anhand der Anforderungen des Projekts eine Entscheidung über die Implementierung treffen.

Drittens : Reduzieren Sie solche Probleme immer auf ihre Grundkomponenten. Sie wissen, dass Standorte auf einer Karte zweidimensional verteilt sind. Sie wissen, dass, wenn Sie beliebige x-, y-Koordinaten erhalten, der Abstand zu jeder Koordinate von einer anderen Koordinate berechnet wird, indem Sie ein Dreieck bilden und nach der unbekannten Länge suchen. Sie wissen hoffentlich auch, dass Sie, wenn Sie aufgefordert werden, alle Koordinaten innerhalb eines Begrenzungsrahmens zu finden, dies einfach tun können, indem Sie die Ausmaße des zu suchenden Felds berechnen und einfach größer als, kleiner als die Logik entlang beider Achsen verwenden.

Zuletzt habe ich noch nie einen Entwickler eingestellt, der Fragen offenbar aufgegeben hat . Wenn ich eine Frage stelle und die Person "Ich weiß nicht" sagt und nicht einmal versucht, sie mündlich zu durchdenken, entsteht der Eindruck, dass sie nicht zu Brainstorming-Sitzungen beiträgt - was bei Organisationen, die Software schreiben, von entscheidender Bedeutung ist .

Dies ist wahrscheinlich offensichtlich, aber für viele Anwendungen kann die langsame Lösung des armen Mannes in Ordnung sein.

Haben Sie eine Tabelle in einer relationalen Datenbank, in der Breiten- und Längengrade gespeichert sind. Abfrage für alle Standorte mit einem Breitengrad innerhalb von 20 Meilen und einem Längengrad innerhalb von 20 Meilen. Auf diese Weise erhalten Sie ein Begrenzungsrechteck in der Größe des kleinsten Begrenzungsrechtecks, das den Radius enthält, nach dem Sie wirklich suchen möchten (und der auch die Erdkrümmung ignoriert).

Anschließend nehmen Sie den zurückgegebenen Satz (durch eine Abfrage unter Verwendung von Indizes) und filtern ihn mithilfe einer genauen Entfernungsberechnung nach unten.

Also keine effiziente Leistung, aber sehr effizient in der Zeit, um sich zu entwickeln. Für viele Anwendungen ist dies möglicherweise die bessere Wahl.

Am einfachsten ist es wahrscheinlich, einen Quadtree zu verwenden, um die Standorte Ihrer Häuser zu speichern, sofern diese in einer 2D-Landschaft verteilt sind. Die Suche sollte ziemlich einfach sein.

Wenn Sie ein GIS-fähiges RDBMS zum Speichern Ihrer Daten verwenden, müssen Sie sich darüber keine Gedanken machen. In dieser Frage finden Sie einige Informationen zur Leistung der Hauptakteure.