找到最近的交付中心到一個給定的地區代碼

Question

這是一個公司在面試過程中被問到的。假設有一個界面可以查找您所在地區最近的交付中心。您只需輸入您的郵政編碼和PIN碼即可返回最近的配送中心。數據結構和算法會做什麼？就像，你打破了你的手機，想要去服務中心。您前往公司網站並輸入您的郵政編碼以查找最近的維修中心。它是如何做到的？

我提出了一個圖+ hashmap解決方案，我將返回給定節點的鄰居節點，地址將存儲在hashmap wrt zipcode中，但這不夠好，因爲面試官一直在使用地理屬性說，你沒有得到兩個中心之間的距離，所以你怎麼知道哪個是最近的，如果要求最近的三個中心。那時我無法提出任何解決方案。他還一次又一次地問我需要什麼數據來解決這個問題。知道這可能是什麼方法，因爲它已經困擾了我好幾天，真的很有幫助。謝謝

Answer 1

大多數算法都處理單點 - 只是取一個郵編區域的中心點就足夠了。

對於一個最近的鄰居，Voronoi diagram似乎是要走的路。

它將空間分隔成區域，以便給定任何查詢點，我們知道哪個點最接近。

從Wikipedia摘自：

甲kd-tree也是一種選擇：

第k d樹是一個二叉樹，其中每個節點是一個k維點。每個非葉節點都可以被認爲是隱式地生成一個分裂超平面，該空間將空間分成兩部分，稱爲半空間。該超平面左側的點由該節點的左側子樹表示，超平面的點右側由右側子樹表示。超平面方向的選擇方式如下：樹中的每個節點都與其中一個k維關聯，超平面與該維的軸垂直。因此，例如，如果對於特定分割選擇「x」軸，具有比該節點更小的「x」值的子樹中的所有點將出現在左子樹中，並且具有更大「x」值的所有點將是在正確的子樹中。在這種情況下，超平面將由該點的x值設置，其法線將爲單位x軸。

找到k個最近鄰居要困難得多。有一個k nearest neighbours algorithm，但這是一個分類算法，所以我不確定它在這裏有幫助。

一種選擇是創建該區域的網格。然後，給定一個點，我們知道它在哪個單元格中，我們可以簡單地查詢該單元格及其鄰居，直到找到所需數量的鄰居。

一個只是要小心這裏，作爲下一個最近的點，其實是可以在另一個單元格，如：

-------------- 
    |  B| 
A | X  | 
    |   | 
    |   | 
-------------- 

鑑於X點，最近點是A，而B會如果我們被退回只需查看同一個單元格。我們還需要在之後查看所有鄰居單元，我們已經找到了k個點。

Answer 2

您需要整個道路網絡，這是一個包含所有節點之間距離的稀疏矩陣。您還需要有包含服務中心的節點列表。有了這個，我認爲A *算法應該確定給定位置和每個服務中心之間的距離，然後在距離中至少選擇三個。我確信有更高效的算法，但我相信面試官應該專注於解決問題的方式，而不是要求實現細節，如數據結構。我是否需要在現實生活中解決這個問題，我會先做文學研究。 面對這樣的面試官時，我不確定什麼策略是最好的，他是否會接受這樣的回答。在深入細節之前強調並提供解決方案的概述可能會更好。 雖然沒有遺憾。從體驗中受益並繼續前進。你不知道上帝爲你儲備了什麼賞金。