10

我的手机里有联系人。可以说我的联系人是

Ram

Hello

Hi

Feat

Eat

At

当我输入字母时'A'，我应该让所有匹配的联系人说"Ram, Feat, Eat, At"。

现在我再打一个字母T。现在我的总字符串"AT"现在是我的程序应该重用之前搜索的结果"A"。现在它应该返回我"Feat, Eat, At"

为此设计和开发程序。

这是三星移动开发的面试问题

我尝试用Trie data structures. 无法获得重用已搜索字符串结果的良好解决方案。我还尝试了使用字典数据结构的解决方案，解决方案与Trie.

问题是如何重新使用先前搜索的字符串的搜索结果来搜索每个键入的字母的联系人？应该使用什么数据结构和算法来有效地解决问题。

我不是要程序。所以编程语言对我来说无关紧要。

状态机似乎是一个很好的解决方案。有人有建议吗？

解决方案应该足够快，可用于百万联系人。

4

3 回答 3

16

这取决于您要搜索的项目数量。如果它是一个相对较小的列表，您可以string.contains检查所有内容。因此，当用户键入“A”时，您将搜索整个列表：

for each contact in contacts
    if contact.Name.Contains("A")
        Add contact to results

然后用户输入“T”，你依次搜索之前返回的结果：

for each contact in results
    if contact.Name.Contains("AT")
        Add contact to new search results

如果联系人列表很大，事情会变得更有趣，但是对于您通常在手机中拥有的联系人数量（一千个会很多！），这将非常有效。

如果面试官说“使用之前搜索的结果进行新搜索”，那么我怀疑这就是他正在寻找的答案。创建一个新的后缀树比顺序搜索前一个结果集需要更长的时间。

您可以通过将子字符串的位置与联系人一起存储来稍微优化这一点，以便下次您要做的就是检查下一个字符是否符合预期，但这样做会使算法有点复杂（您必须将第一次搜索视为特殊情况，并且您必须明确检查字符串长度等），并且在前几个字符之后不太可能提供太多好处，因为要搜索的列表的大小会非常小. 带有检查的纯顺序搜索contains将非常快。用户不会注意到您通过该优化节省的几微秒。

编辑问题后更新

如果您想对一百万个联系人执行此操作，顺序搜索可能不是一开始的最佳方式。虽然我还是会试一试。“对一百万个联系人来说足够快”引发了“足够快”究竟意味着什么的问题。搜索一百万个联系人以查找单个字母的存在需要多长时间？用户愿意等待多久？还请记住，在用户采取另一项操作之前，您只需显示一页联系人。而且您几乎可以肯定地在用户按下第二个键之前做到这一点。特别是如果您有一个后台线程进行搜索，而前台线程处理输入并将匹配字符串的第一页写入显示器。

无论如何，您可以通过创建二元索引来加速初始搜索。也就是说，对于每个二元组（两个字符的序列），构建一个包含该二元组的名称列表。您还需要为每个字符创建一个字符串列表。因此，鉴于您的姓名列表，您将拥有：

r - ram
a - ram, feat, eat, a
m - ram
h - hello, hi
...
ra - ram
am - ram
...
at - feat, eat, at
...
etc.

我想你应该已经明白了。

该二元索引存储在字典或哈希映射中。英语中只有 325 个可能的二元组，当然还有 26 个字母，所以你的字典最多有 351 个条目。

因此，您几乎可以立即查找 1 个字符和 2 个字符的名称。这对你有什么帮助？

对古腾堡计划文本的分析表明，英语中最常见的二元组仅出现 3.8% 的时间。我意识到名称不会完全共享该分布，但这是一个相当不错的粗略数字。因此，在键入前两个字符后，您可能会使用不到列表中总名称的 5%。一百万的百分之五是五万。只需 50,000 个名称，您就可以开始使用我最初描述的顺序搜索算法。

这种新结构的成本并不算太差，尽管它足够昂贵，无论如何我肯定会先尝试简单的顺序搜索。在最坏的情况下，这将花费您额外的 200 万次对名称的引用。如果您构建 2 级树而不是字典，则可以将其减少到一百万个额外的引用。查找和显示单字符搜索结果将花费稍长的时间，但不足以让用户注意到。

这种结构也很容易更新。要添加名称，只需遍历字符串并输入适当的字符和二元组。要删除名称，请通过提取二元组的名称，并从二元组索引中的相应列表中删除该名称。

于 2013-07-17T15:17:52.760 回答
7

查找“广义后缀树”，例如https://en.wikipedia.org/wiki/Generalized_suffix_tree。对于固定的字母大小，该数据结构给出了渐近最优的解决方案，以在 O(z + m) 时间内找到一组字符串中长度为 m 的子字符串的所有 z 匹配。因此，您获得的好处与您将搜索限制为前一个前缀的匹配项一样。此外，该结构具有最佳的 O(n) 空间和构建时间，其中 n 是所有联系人的总长度。我相信你可以修改结构，以便在 O(k + m) 时间内找到包含子字符串的 k 个字符串，但一般来说，每个联系人可能不应该有太多匹配项，所以这可能甚至没有必要。

于 2013-07-17T15:40:54.283 回答
1

我想做的是，跟踪so far matched字符串。假设在第一步中，我们识别出其中包含“A”的字符串，并跟踪“A”的位置。然后在下一步中，我们只遍历这些字符串，而不是完整地搜索它们，我们只检查出现“T”作为“A”的下一个字符，我们在上一步中跟踪，依此类推。

于 2013-07-17T15:25:16.230 回答