采访：系统/API设计

Question

采访：系统/API设计

12

这个问题是在一家大型软件公司中提出的。我想出了一个简单的解决方案，并想知道其他人对这个解决方案的感受。

你需要设计一个API和后端系统，用于为城市居民分配电话号码。电话号码将从111-111-1111开始，到999-999-9999结束。API应使客户（城市中的人）能够执行以下操作：

当客户请求电话号码时，给他们分配其中一个可用的号码。

有些客户可能想要特殊号码，因此他们可以明确要求分配给他们一个号码。如果所请求的号码可用，则将其分配给客户，否则系统将分配任何可用号码。

系统不必知道分配给哪个客户哪个号码。同一客户可能会连续发出请求并为自己获得多个电话号码，但系统不介意。在任何时候，系统只知道哪些电话号码已经被分配，哪些电话号码是空闲的。

从111-111-1111到999-999-9999的号码大约对应于80亿个数字。假设内存不是限制因素，我可以想到以下两种方法（它们几乎相似）。

维护一个巨大的长度为80亿的布尔数组，并具有指向数组索引位置的next指针（next初始化为零）。如果next指向的值不是空闲的，则将next前进，直到找到一个空闲的数字。当请求特殊号码时，只需检查相应的索引位置是否为空闲，并返回号码。这种方法的缺点是，在按常规方式分配号码时，如果在中间有巨大的块（例如10亿个）的号码是通过特殊分配分配的，则必须移动1亿次next指针。

- NPE

3个回答

1

首先，您没有原型化您的API。例如，如果我要设计这些API，我会发布2个API。

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

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

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

您可以维护单个列表仅存储分布式数字（占用更少的内存）。因此，每当请求到来时，您都要在该列表中搜索1到n个数字（增加时间复杂度）。如果没有第一个（或请求的）数字，则将其分配给客户端并将该条目添加到列表中。

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

您还可以利用数据库的优势。

- Icarus3

0

为了增强之前的答案，任何二叉搜索树可能都不够好，因为插入或删除操作可能会使其失衡。平衡二叉搜索树，例如红黑树，应该是一个不错的选择。因此，可以在开始时创建和填充一棵红黑树来表示可用数字，每次分配都应该从中移除一个元素。

init(from, to) - 可以在 O(n) 的时间内完成，直接实现则需要 O(n log n) 的时间。但这是服务器启动时的一次性初始化。
acquireNextAvailableNumber() - 应该删除最小的元素，时间复杂度为 O(1)。
acquireRequestedNumber(special) - 应该进行搜索并在找到元素时删除它，保证时间复杂度为 O(log n)。

在 Java 中，可以使用 TreeSet<String> 或 TreeSet<Integer>，因为它是使用红黑树实现的。

下一个问题可能是多个请求处理线程将访问您的 API，因此由于 Java 的 TreeSet 不是线程安全的，您应该在初始化时像这样包装它：

TreeSet numbers = init(...);
SortedSet availableNumbers = Collections.synchronizedSortedSet(numbers);

- Gena L

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- DJClayworth · Accepted Answer

你可以在回答这个问题时做得更好。

首先，你应该设计你的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（按数字排序），原因稍后再说。

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

查看最后一个分配的号码，并找到下一个序列。
检查该号码是否已被分配为特殊号码。您可以使用 BST 快速完成此操作，因为如果存在，则它将是 BST 中的最低条目。
如果该号码在“特殊数字”数据库中，则增加“已分配数字”的值（以包括该号码），并从特殊数字中移除该条目。然后重复此过程，直到获得未出现在特殊数字中的号码。

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

检查特殊号码很容易。如果它低于最后一次“正常”分配的号码，则不可用。否则，您可以检查它是否存在于 BST 中。如果不存在，则将其添加到 BST 中。

您可以通过在 BST 中存储数字范围而不仅是单个数字来优化此过程。如果分配的特殊数字密集，则它将减少树中的空间和查找其中一个的访问次数。在测试中查找“下一个”号码是否发现大小为n的范围时，您可以立即将最高正常号码增加n，而不必循环n次。