访谈：系统/ API设计

Question

这个问题曾在一家大型软件公司中问过。我想出了一个简单的解决方案，我想知道别人对解决方案的看法。

你应该设计一个系统的API和后端，可以 分配给住在城市的人的电话号码。电话号码 从111-111-1111开始，结束于999-999-9999。该API应该使 客户端（在市人）做到以下几点：

1. 当一个电话号码的客户端请求时，它的下发的可用号码其中之一。
2. 有些客户可能需要花哨的号码，所以他们可以特别要求一个号码被分配给他们。如果请求的号码是 可用，则系统将其分配给他们，否则系统 分配任何可用号码。

该系统不需要知道哪个号码被分配给哪个客户端 。同一个客户可能会连续发出请求，并为自己获得多个电话号码，但系统不会受到影响。在任何 时间点，系统只知道哪些电话号码被分配 以及哪些电话号码是免费的。

从111-111-1111到999-999-9999的数字大致对应于80亿个数字。假设记忆不是一个约束，我可以想到以下两种方法（几乎相似）。

1. 保持长度为8十亿的一个巨大的布尔阵列和具有next指针指向数组索引（next被初始化为零）。如果next指向的值不空闲，则转发next，直到找到空闲号码。当请求花哨的数字时，只需检查相应的索引位置是否空闲并返回该数字。这种方法的不足之处在于，当按照常规方式分配数字时，如果中间有一个庞大的数据块（比如说10亿个数字）被奇特分配分配，那么next指针必须移动10亿次。

2. 为了克服前面提到的困难，我们可以使用某种链接的散列表。我们维护一个双向链表（这取代了前面设计中的数组）和另一个与列表长度相同的数组，其中数组的每个元素都指向列表中的相应元素。因此，当在常规方法中分配数字时，我们在链表中标记一个指针，并在分配时标记节点（与之前的方法相同）。当分配花式数字时，我们可以直接在列表中找到对应于首先索引到数组中的特殊数字所对应的节点以及随后的指针。一旦识别出节点，就将前一个节点和下一个节点短路，这样我们就不必在进行常规分配时一个接一个地跳过使用的数字（这是前一种方法的问题）。

让我知道我是否在正确的轨道上。请告诉我我缺少的任何重要细节。

Answer 1

首先，你没有原型的API。例如，如果我必须设计这些API，我将发布2个API。

string acquireNextAvailableNumber(); 
string acquireRequestedNumber(string special); 

其次，您需要决定如何实施它。代码驱动还是数据驱动？

您可以为所有这些数字（它将消耗内存）维护哈希并快速查询数字的可用性。或

你可以维护单个列表来存储分布式号码（内存少）。因此，无论何时请求，您都会开始在该列表中搜索1到n个数字（增加时间复杂度）。如果有任何第一个（或请求的）号码不存在，那么您将其分配给客户端并将该条目添加到列表中。

由于有十亿个数字，您需要考虑时间和空间的权衡。

你也可以利用数据库。

Answer 2

你可以在这个问题的答案中做得更好。

首先你应该设计你的API。通过Icarus3推荐一个是完美的：

string acquireNextAvailableNumber(); 
boolean acquireRequestedNumber(string special); 

第二个返回true（并保留数）（如果可用），否则返回false。

该问题没有说明你如何分配电话号码，所以分配它们以适应自己。使第一个'下一个可用'请求返回“111-111-1111”，下一个“111-111-1112”等。这意味着你可以通过记住分配的最后一个来记录通过'next'分配的所有号码。 （你需要询问'111-111-1119'后面是“111-111-1120”还是111-111-1121“，但这就是你应该问的东西，无论如何，重要的是你可以计算出知道最后分配的数字是什么。）

你需要单独存储的特殊请求。散列表工作，但BST或简单的有序列表也是如此。这取决于你想要在空间和速度之间进行什么折衷，以及可能需要多少次特殊数字。我会在其余部分使用BST（按数字排序），原因是我会来。

那么，你如何编码？对于下一个分配的号码：

1. 查看最后分配的号码，然后查找下一个序号。
2. 检查该号码是否未被分配为特殊号码。您可以使用BST快速完成此操作，因为如果它在那里，它将成为BST中最低的条目。
3. 如果号码在'特殊号码'数据库中，请增加'分配号码'的值（包括该号码），并从特殊号码中删除该条目。然后重复这个过程，直到你得到一个不在特殊数字中的数字。

请注意，此过程可确保所有'特殊号码'低于'next'分配的最后一个'特殊号码'不出现在特殊号码数据库中。随着“分配的最后正常数量”增加，它将吸收分配的任何小于此数字的特殊数字，并将其从表格中删除。这确保了当我们询问下一个数字是否在特殊数字数据库中时，我们只需要查看最低的条目。

检查特殊号码很容易。如果它低于分配的最后'正常'号码，则它不可用。否则，你会检查它是否存在于BST中。如果没有，请将其添加到BST。

您可以通过在BST中存储不仅单个数字而是存储数字范围来优化此过程。如果分配的特殊数字很密集，那么它会减少树中的空间数量以及查找是否有人访问的数量。在测试过程中，如果'下一个'号码发现n的大小，那么你可以立即将n的最高正常值递增，而不必绕n次循环。