7

我们需要维护 mobileNumber 及其在内存中的位置。挑战在于我们有超过 500 万用户，存储每个用户的位置就像 500 万条记录的哈希图。为了解决这个问题，我们必须在范围上工作

我们得到了一系列电话号码，例如

  • range1 start="9899123446" end="9912345678" location="a"

  • range2 start="9912345679" end="9999999999" location="b"

一个号码只能属于一个位置。

我们需要一个数据结构来将这些范围存储在内存中。

它必须支持两个功能

  1. findLocation(Integer number) 它应该返回数字所属的位置名称
  2. 更改位置（整数，字符串范围）。它将号码的位置从旧位置更改为新位置

这完全是在内存设计中。

我打算使用每个节点包含的树结构（ startofrange ， endofrange ，location）。我将保持节点排序。我还没有完成任何事情。主要问题是 - 当第二个改变位置的函数被称为 9899123448 位置到 b

range1 节点应拆分为 3 个节点 1st node (9899123446,9899123447,a) 2nd node (9899123448,9899123448,b)3rd node (9899123449,9912345678,a)。

请提出合适的方法提前谢谢

4

2 回答 2

9

通常，您可以使用专门的数据结构来存储范围并实现查询，例如间隔树。

但是，由于电话号码范围不重叠，您可以将范围存储在仅按 [begin]排序的基于标准树的数据结构中（二叉搜索树、AVL 树、红黑树、B 树都可以）。

对于 findLocation(number)，使用相应的树搜索算法找到第一个 [begin] 值小于该数字的元素，检查其 [end] 值并验证该数字是否在该范围内。如果找到匹配，则返回位置，否则数字不在任何范围内。

对于 changeLocation() 操作：

  1. 找到包含数字的旧节点
  2. 如果在步骤 1 中找到现有节点，请将其删除并插入新节点
  3. 如果没有找到现有节点，则插入一个新节点并尝试将其与相邻节点合并。

我假设您使用相同的操作来简单地添加新节点。

更实际的是，您可以将所有条目存储在数据库中，在 [begin] 上建立索引。

于 2013-09-22T20:57:47.817 回答
3

首先range= [ begin; end; location]

使用两种结构：

  • range存储sbegin的 排序数组
  • 通过s访问ends 和locations 的哈希表begin

应用以下算法：

  1. 使用二分查找查找“最接近的”值 obbegin
  2. 使用哈希表查找end和location查找begin
于 2013-09-22T20:31:35.830 回答