2

我正在阅读来自不同公司的面试问题，我遇到了这个问题：

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 范围不重叠。

有人对此有更好的解决方案吗？

4

2 回答 2

2

您可以将 IP 地址存储在 32 位上，因此只需将它们转换为整数，然后将这些对存储在密钥为 IP(IP, City)的任何平衡 BST或哈希表中。以这种方式查找复杂性将是对数或恒定的。

于 2013-04-14T13:13:29.903 回答
0

您可以为每个虚线部分创建一个树结构，叶节点将是城市

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-14T13:14:38.930 回答