數據結構市

我讀來自不同公司的面試問題，我就來了：數據結構市

You are given a fixed file. The format of each line is city name, ip address 
range. Construct a data structure and design algorithm to achieve efficient 
mapping from an ip address to city name.

的一種方式，我認爲會的工作，儘管在線性時間是一個簡單的鏈表，在那裏你有給定範圍的起始IP，並且在你擁有城市的節點和最後的IP範圍內。

因此，當尋找東西時，您遍歷列表並檢查開始和結束IP地址，以查看給定IP是否在任何範圍內。

這假設IP範圍不重疊。

有人對此有更好的解決方案嗎？

來源

2013-04-14 Sorin Cioban

您可以在32位存儲IP地址，因此只需將其轉換爲整數，然後將(IP, City)對存儲在任何balanced BST或hash table中，其中密鑰爲IP。以這種方式查找複雜度將是對數或常數。

來源

2013-04-14 13:13:29 IVlad

對於整數鍵，比基於比較的BST更有效的整數鍵映射，比如try和van Emde Boas樹。 – delnan

您可以創建一個樹形結構爲每個虛線部分和葉節點將是城市

Root 
| 
[0-13]  [14-255] 
|    | 
[0-255] [0-173], [174-255] 
|    |    | 
[0-255] [0-255]  [0-255] 
|    |    | 
[0-255] [0-255]  [0-255] 
|    |    | 
London Belfast  Berlin

等，然後在地圖上的地址到一個城市你只是走在樹，以便14.183.1.123將是柏林

來源

2013-04-14 13:14:38 iain

回答

相關問題