system design - google suggestion/auto type
不对。这个问题的解决流程是这样的：
首先你需要一个 log 的service，把用户的搜索信息记录下来，比如：
{"apple": 1, "google": 2, "baidu": 3}
这个时候key是用户搜索的完整单词，value 是搜索次数。
然后用一个
离线脚本，将这个结果整理为 Trie。这个时候我们称之为 Trie' 吧。在 Trie' 中，每个 TrieNode 上也只存储到此节点为一整个单词的被搜索的次数。
接着你需要再用一个离线脚本去统计，每个 Prefix 下面的 Top 10的结果是什么。http://www.lintcode.com/en/problem/trie-service/ 这个题目就是为了让大家理解怎么完成这个部分。完成这个操作之后的 Trie 我们称之为 Trie'' ，也就是此时，TrieNode 上不仅仅存储了该 Prefix 被搜索的次数，还存储了以该 Prefix 开头的 Top 10 的单词。举个例子：
{
"a": ["ab", "ac", "ad" ...]
-- "ab": ["abc", "abe" ..]
-- "ac": ["aca", "acd" ..]
"b": ...
...
}
也就是说，这个时候的 Trie''，在给定某个 prefix的时候，就能够直接在 O(Len(prefix)) 的时间复杂度内找到 Top K，而不需要遍历整个 Trie 去搜寻。
然后此时我们发现内存不够了，要开始 sharding了，我们可能会把 "a" 和 “ab” 分在不同的机器上，但是 a的那个小的top 10 的list，也就是["ab", "ac", "ad" .. ] 会跟着 a走，也就是虽然 ab ac ad 作为key的那个prefix，不和a在同一台机器上，但是 以 a作为 prefix开头的 top 10 的结果，已经在 Trie'' 中计算好了，所以跟着a走就可以了。
https://www.jiuzhang.com/qa/1858/
https://www.interviewbit.com/problems/design-search-typeahead/
https://www.interviewbit.com/problems/design-search-typeahead/
Google系统设计面试题--设计一个auto complete 系统(type ahead系统)
Type ahead/Auto Complete 设计
二叉树 省空间但慢；trie 快但空间大；三叉树
Comments
Post a Comment