12

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

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

  1. 当客户请求电话号码时，它会为他们分配一个可用号码。
  2. 有些客户可能想要花哨的数字，所以他们可以专门要求分配给他们的数字。如果请求的号码可用，则系统将其分配给他们，否则系统分配任何可用的号码。

系统不必知道哪个号码分配给哪个客户。同一个客户端可能会发出连续的请求并为自己获得多个电话号码，但系统不会受到打扰。在任何时候，系统只知道分配了哪些电话号码，哪些电话号码是免费的。

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

  1. 维护一个长度为 80 亿的巨大布尔数组，并有一个next指向数组索引的指针（next初始化为零）。如果指向的值next不是空闲的，则转发next直到找到空闲的数字。当请求花哨的数字时，只需检查相应的索引位置是否空闲并返回数字即可。这种方法的缺点是，当以常规方式分配数字时，如果中间有一大块（比如 10 亿个）数字是通过花式分配分配的，那么next指针必须移动 10 亿次。

  2. 为了克服之前设计中提到的困难，我们可以使用某种链接的 hashmap。我们维护一个双向链表（这取代了之前设计中的数组）和另一个与列表长度相同的数组，其中数组的每个元素都指向列表中的相应元素。因此，在常规方法中分配数字时，我们在链表中推进一个指针，并将节点标记为分配时（与前面的方法相同）。在分配花式数字时，我们可以直接在列表中找到与请求的特殊数字相对应的节点，首先索引到数组中，然后跟随指针。一旦节点被识别，

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

4

3 回答 3

11

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

首先你应该设计你的 API。Icarus3 推荐的一款非常好：

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

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

该问题没有具体说明您如何分配电话号码，因此请根据自己的需要进行分配。使第一个“下一个可用”请求返回“111-111-1111”，下一个“111-111-1112”等。这意味着您只需记住最后一个分配的号码，就可以记录通过“下一个”分配的所有号码。（您需要询问“111-111-1119”后面是“111-111-1120”还是“111-111-1121”，但无论如何你都应该问这种事情。无论如何，重要的是你可以知道最后分配的数字是多少。）

特殊要求，您需要单独存储。哈希表有效，但 BST 或简单的有序列表也有效。这取决于您想要在空间和速度之间进行何种权衡，以及可能请求特殊数字的频率。我将在剩下的部分中使用 BST（按数字排序），原因我会谈到。

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

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

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

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

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

于 2014-01-14T16:01:36.097 回答
1

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

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

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

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

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

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

您还可以利用数据库。

于 2012-12-27T21:49:35.543 回答
0

为了增强以前的答案，任何 BST 都可能不够好，因为插入或删除会使其不平衡。一个平衡的 BST，例如红黑树，应该是一个不错的选择。因此，可以创建一棵红黑树并在开头填充以表示可用数字，并且每次分配都应从中删除一个元素。

  • init(from, to)- 可以在 O(n) 时间内完成，一个简单的实现将是 O(n log n)。但这是您服务器启动时的一次性初始化
  • acquireNextAvailableNumber()- 应该删除最小元素，时间成本 O(1)
  • acquireRequestedNumber(special)- 如果找到，应该进行搜索并删除元素，保证时间成本 O(log n)

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

下一个问题可能是多个请求处理线程会访问您的 API，因此由于 Java 的 TreeSet 不是线程安全的，因此您应该在初始化时将其包装起来，如下所示：

TreeSet numbers = init(...);
SortedSet availableNumbers = Collections.synchronizedSortedSet(numbers);
于 2019-11-26T20:54:32.520 回答