system-design - 采访: System/API design

Question

大型软件公司之一问了这个问题。我想出了一个简单的解决方案，我想知道其他人对该解决方案有何看法。

You are supposed to design an API and a backend for a system that can allot phone numbers to people living in a city. The phone numbers will start from 111-111-1111 and end at 999-999-9999. The API should enable the clients (people in the city) to do the following:

1. When a client requests for a phone number, it allots one of the available numbers to them.
2. Some clients may want fancy numbers, so they can specifically ask for a number to be alloted to them. If the requested number is available then the system allots it to them, otherwise the system allots any available number.

The system need not have to know which number is alloted to which client. The same client may make successive requests and get multiple phone numbers for himself, but the system is not bothered. At any point of time, the system only knows which phone numbers are alloted and which phone numbers are free.

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

维护一个庞大的 bool 数组，长度为80亿，并具有一个指向数组索引的next指针(next初始化为零)。如果next所指向的值不是空闲的，则转发next直到找到一个空闲的数字。当要求输入奇特的数字时，只需检查相应的索引位置是否可用，然后返回该数字即可。这种方法的缺点是，当以常规方式分配数字时，如果中间有大量块(例如10亿个)通过花式分配分配的数字，则next指针必须移动10亿次。

为了克服previos设计中提到的困难，我们可以使用某种链接的哈希表。我们维护一个双向链表(它替换了先前设计中的数组)和另一个长度与列表相同的数组，其中数组的每个元素都指向列表中的对应元素。因此，当以常规方法分配数字时，我们在链接列表中前进一个指针，并在分配时将节点标记为和(与先前方法相同)。在分配奇特编号时，我们可以通过首先索引数组并跟随指针来直接在列表中找到与所请求的特殊编号相对应的节点。确定节点后，将前一个节点和下一个节点短路，以便在进行常规分配时不必一一跳过使用的数字(这是前一种方法的问题)。

让我知道我是否走对了。请向我提供我所缺少的任何重要细节。

Answer 1

您可以在此问题的答案中做得更好。

首先，您应该设计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(按数字排序)。

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

查看最后分配的编号，并依次查找下一个。

检查该号码是否尚未分配为特殊号码。您可以使用BST很快完成此操作，因为如果有的话，它将是BST中最低的条目。

如果该号码位于“特殊号码”数据库中，请增加“已分配号码”的值(以包括该号码)，然后从特殊号码中删除该条目。然后重复此过程，直到您得到一个不在特殊数字中的数字。

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

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

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