这个问题是在一家大型软件公司中提出的.我想出了一个简单的解决方案,我想知道其他人对解决方案的看法.
您应该为系统设计API和后端,以便为居住在城市中的人分配电话号码.电话号码将从111-111-1111开始,到999-999-9999结束.API应该使客户(城市中的人)能够执行以下操作:
- 当客户请求电话号码时,它会向其分配一个可用号码.
- 有些客户可能需要花哨的数字,所以他们可以专门要求分配一个数字.如果请求的号码可用,则系统将其分配给它们,否则系统将分配任何可用的号码.
系统无需知道哪个号码分配给哪个客户端.同一个客户可以连续发出请求并为自己获取多个电话号码,但系统不会受到打扰.在任何时候,系统只知道分配了哪些电话号码以及哪些电话号码是免费的.
从111-111-1111到999-999-9999的数字大致相当于80亿个数字.假设内存不是约束,我可以想到以下两种方法(几乎相似).
维护一个长度为80亿的巨大布尔数组,并有一个next指向数组索引的指针(next初始化为零).如果指向的值next不是空闲的,则转发next直到找到空闲数字.当请求花哨的数字时,只需检查相应的索引位置是否空闲并返回该数字.这种方法的缺点是,当以常规方式分配数字时,如果中间有一个巨大的块(比如10亿个)由花式分配分配,那么next指针必须移动10亿次.
为了克服previos设计中提到的困难,我们可以使用某种链接的hashmap.我们维护一个双向链表(这取代了前一个设计中的数组)和另一个与列表长度相同的数组,其中数组的每个元素指向列表中的相应元素.因此,当在常规方法中分配数字时,我们在链表中推进指针并在分配时标记节点(与前一个方法相同).在分配花哨数字时,我们可以直接在列表中找到与首先索引到数组所需的特殊数字相对应的节点,然后是指针.一旦识别出节点,就会使前一个节点和下一个节点短路,这样我们就不必在进行常规分配时逐个跳过使用过的数字(这是前一种方法的问题).
让我知道我是否走在正确的轨道上.请告诉我任何我遗漏的重要细节.
对于这个问题,你可以在anser中做得更好.
首先,你应该设计你的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(按编号排序),原因我会来.
那么,你如何编码呢？对于下一个分配的号码:
请注意,此过程可确保低于"next"分配的最后一个"特殊数字"不会出现在特殊数字数据库中.随着"最后分配的正常数量"的增加,它会吸收任何小于该值的特殊数字,将其从表中删除.这就是确保当我们询问序列中的下一个数字是否在特殊数字数据库中时,我们只需要查看最低的条目.
检查特殊号码很容易.如果它低于分配的最后一个"正常"号码,则它不可用.否则,您要检查它是否存在于BST中.如果没有,则将其添加到BST.
您可以通过在BST中存储不仅仅是单个数字,而是存储数字范围来优化此过程.如果分配的特殊数字是密集的,那么它会减少树中的空间量以及在那里找到的访问次数.在测试过程中,如果'下一个'号码发现大小为n的数据,那么你可以立即将最高正常数增加n,而不必绕圈数n次.
小智 1
首先，您没有对 API 进行原型设计。例如，如果我必须设计这些 API，我将发布 2 个 API。
string acquireNextAvailableNumber();
string acquireRequestedNumber(string special);
其次，您需要决定如何实施它。代码驱动还是数据驱动？
您可以维护所有这些号码的哈希（会消耗内存）并快速查询该号码的可用性。或者
您可以维护单个列表来仅存储分布式数字（更少的内存）。因此，每当请求到来时，您就开始在该列表中搜索 1 到 n 个数字（增加时间复杂度）。如果任何第一个（或请求的）号码不存在，那么您将其分配给客户端并将该条目添加到列表中。
由于数字有数十亿，您需要考虑空间和时间之间的权衡。
您还可以利用数据库。