use*_*036 10 algorithm search trie
我的联系人存储在手机中.让我们说我的联系人
Ram
Hello
Hi
Feat
Eat
At
当我输入信件时,'A'我应该得到所有匹配的联系人说"Ram, Feat, Eat, At".
现在我再打一个字母T.现在我的总字符串"AT"现在我的程序应该重用以前搜索的结果"A".现在它应该归还给我"Feat, Eat, At"
为此设计和开发一个程序.
这是三星移动开发的面试问题
我试着解决Trie data structures.无法获得重复使用已搜索字符串结果的良好解决方案.我也尝试过用字典数据结构的解决方案,解决方案也有同样的缺点Trie.
问题是我如何搜索键入的每个字母的联系人重新使用先前搜索的字符串的搜索结果？应该使用什么数据结构和算法来有效地解决问题.
我不是要求节目.所以编程语言对我来说并不重要.
状态机似乎是一个很好的解决方案.有没有人有建议？
对于百万联系人来说,解决方案应足够快
Jim*_*hel 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个字符的名字.这对你有什么帮助？
对Gutenberg项目文本的分析表明,英语中最常见的二元语言只占3.8%的时间.我意识到名字不会完全分享那个分布,但这是一个非常好的粗略数字.因此,在键入前两个字符后,您可能只使用列表中总名称的不到5%.百万分之五是50,000.只有50,000个名称,您可以开始使用我最初描述的顺序搜索算法.
这个新结构的成本并不算太差,虽然它足够昂贵,但我当然首先尝试简单的顺序搜索.在最坏的情况下,这将花费你额外的200万个名字参考.如果您构建一个2级trie而不是字典,则可以将其减少到一百万个额外引用.查找和显示单字符搜索结果需要稍长的时间,但不足以让用户注意到.
这种结构也很容易更新.要添加名称,只需浏览字符串并为相应的字符和双字母组生成条目.要删除名称,请浏览提取bigrams的名称,并从bigram索引中的相应列表中删除该名称.
查找"通用后缀树",例如https://en.wikipedia.org/wiki/Generalized_suffix_tree.对于固定的字母大小,该数据结构给出渐近最优解,以在O(z + m)时间内找到一组字符串中长度为m的子串的所有z匹配.因此,您可以获得与将搜索限制为前一个前缀的匹配项相同的好处.此外,该结构具有最佳的O(n)空间和构建时间,其中n是所有联系人的总长度.我相信你可以修改结构,这样你就可以在O(k + m)时找到包含子串的k个字符串,但一般情况下你可能不应该有每个匹配的匹配太多的匹配,所以这可能甚至没有必要.