数据结构市

我读来自不同公司的面试问题，我就来了：数据结构市

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

回答

相关问题