请教个用trie实现search autocomplete的问题 - JobHunting版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 请教个用trie实现search autocomplete的问题

相关主题
● 上午偷闲把TopKFrequentWords写出来了	● 现在出发去F onsite
● gmail/google 搜索问题，你一定也遇到过	● G家电面面经--佛云了~~
● 国庆节狗家面经	● 这个题能有几种解法？
● 急问，Boggle (crossword)的解题思路？	● 请教：boggle puzzle找所有的单词，怎么做？
● rejected by facebook after 2nd phone interview	● 又死在设计题上了...
● 面试问题请教：如何在字典中得到最长的复合词	● A家onsite, OO答的真郁闷
● 贡献几道面试题	● Leetcode Word Break I 有o(n^2)的算法吗？
● 字典里面如何快速找到一个单词对应的只有一个字母不同的单词	● 分享一盗题

相关话题的讨论汇总
话题: trie话题: 个用话题: search话题: 深度

进入JobHunting版参与讨论

1

(共1页)

n***a 发帖数: 222	1 如果要求是对于用户输入的前15个字符提供autocomplete， list里面是十个结果，每个字符平均有50种可能那么相对应的，这个trie深度是15，每个node有50个children。如果这时候用户刚输入三个字符也就是traverse到了深度为3的node，怎么能快速的从最底层的深度15的leaf里面找到前10的query呢？
w*****w 发帖数: 53	2 DFS TRIE，然后用collector是 fixed size PriorityQueue (min priority)，时间复杂度 O(#TreeNodes * 10log_2(10)) 空间复杂度O(1)

1

(共1页)

进入JobHunting版参与讨论

相关主题
● 分享一盗题	● rejected by facebook after 2nd phone interview
● 一道Facebook面经难题	● 面试问题请教：如何在字典中得到最长的复合词
● FB面经	● 贡献几道面试题
● word search follow up的问题	● 字典里面如何快速找到一个单词对应的只有一个字母不同的单词
● 上午偷闲把TopKFrequentWords写出来了	● 现在出发去F onsite
● gmail/google 搜索问题，你一定也遇到过	● G家电面面经--佛云了~~
● 国庆节狗家面经	● 这个题能有几种解法？
● 急问，Boggle (crossword)的解题思路？	● 请教：boggle puzzle找所有的单词，怎么做？

相关话题的讨论汇总
话题: trie话题: 个用话题: search话题: 深度

未名新帖统计// 7月16日

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)