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/

Google系统设计面试题--设计一个auto complete 系统(type ahead系统)


Type ahead/Auto Complete 设计


二叉树 省空间但慢;trie 快但空间大;三叉树

Comments

Popular posts from this blog

Amazon OA 763. Partition Labels

1427. Split Array into Fibonacci Sequence

05/25 周一