logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
auto completion如何根据popularity快速显示前几个？
avatar
auto completion如何根据popularity快速显示前几个？# JobHunting - 待字闺中
s*l
1 楼
前几天 面试
面试官问 auto complete
很简单 大家都会 是trie
follow up 那不能把所有可能的词都选了吧
那就根据popularity来显示前几个
follow up 怎么算popularity？
就用circular buffer吧
follow up 怎么把这个trie和 circular buffer里的counter联系起来呢？
把所有可能的词 根据popularity的counter排序
可是 我就想 比如
我只输入一个letter s
然后就要把 所有s打头的词都排序了 然后选前几个显示吗？
太慢了吧~
有什么好方法吗？
请大侠指点 谢谢
avatar
m*2
2 楼
不是应该还根据个人习惯么？看历史纪录显示最可能匹配的词。
avatar
s*l
3 楼
对 这个也行
但是不管什么policy
总要有个排序有rank吧~
要是 我输入letter s
那要把所有s开头的词都根据rank排序一下嘛？
太慢了吧
这个是我不解的地方~

【在 m******2 的大作中提到】
: 不是应该还根据个人习惯么？看历史纪录显示最可能匹配的词。
avatar
n*5
4 楼
能详细说说用circular buffer实现popularity吗？
关于你的问题，建trie时就按popularity 放置就可以了吧，如果popularity变化的话
在调整怎么样

【在 s********l 的大作中提到】
: 前几天 面试
: 面试官问 auto complete
: 很简单 大家都会 是trie
: follow up 那不能把所有可能的词都选了吧
: 那就根据popularity来显示前几个
: follow up 怎么算popularity？
: 就用circular buffer吧
: follow up 怎么把这个trie和 circular buffer里的counter联系起来呢？
: 把所有可能的词 根据popularity的counter排序
: 可是 我就想 比如
avatar
s*l
5 楼
就是记录 每个词被hint了多少次
比如过去一天
buffer的每个slot记录1小时内的counter
怎么用popularity放置？
popularity根据counter sort
trie就是个tree的结构

【在 n*********5 的大作中提到】
: 能详细说说用circular buffer实现popularity吗？
: 关于你的问题，建trie时就按popularity 放置就可以了吧，如果popularity变化的话
: 在调整怎么样
avatar
w*g
6 楼
建议你看看Paul Hsu www 2013的文章：
Space efficient data structures for top k completion
avatar
e*3
7 楼
1. 每个prefix都要一个buffer记录,内存要求很高吧?
2. 每个prefix 维护一个counter,并发性不好吧?
我在想把所有的hit记录下来然后每隔一个小时run个map reduce得到结果再sort下存回
去.不知道这个如何?求楼下大牛指教
avatar
l*s
8 楼
ring buffer 内的数据结构是怎样的？
我是说，ringbuffer内每个节点的数据结构

【在 s********l 的大作中提到】
: 就是记录 每个词被hint了多少次
: 比如过去一天
: buffer的每个slot记录1小时内的counter
: 怎么用popularity放置？
: popularity根据counter sort
: trie就是个tree的结构
avatar
s*l
9 楼
ring buffer里 就是一个时间段内的counter啊？
你还想要点什么？

【在 l******s 的大作中提到】
: ring buffer 内的数据结构是怎样的？
: 我是说，ringbuffer内每个节点的数据结构
avatar
s*l
10 楼
好 去看看 多谢

【在 w******g 的大作中提到】
: 建议你看看Paul Hsu www 2013的文章：
: Space efficient data structures for top k completion
avatar
n*5
11 楼
那不就是counter array
跟circular 什么关系?

【在 s********l 的大作中提到】
: 就是记录 每个词被hint了多少次
: 比如过去一天
: buffer的每个slot记录1小时内的counter
: 怎么用popularity放置？
: popularity根据counter sort
: trie就是个tree的结构
avatar
n*5
12 楼
popularity跟时间段有什么关系

【在 s********l 的大作中提到】
: ring buffer里 就是一个时间段内的counter啊？
: 你还想要点什么？
avatar
n*5
13 楼

那你怎么显示suggestion呢？把trie当前node下面的都再遍历一遍？效率太差了八

【在 s********l 的大作中提到】
: 就是记录 每个词被hint了多少次
: 比如过去一天
: buffer的每个slot记录1小时内的counter
: 怎么用popularity放置？
: popularity根据counter sort
: trie就是个tree的结构
avatar
s*l
14 楼
我也觉得效率低 所以来请教的~
那个词 被选的次数多 哪个popular啊~

【在 n*********5 的大作中提到】
:
: 那你怎么显示suggestion呢？把trie当前node下面的都再遍历一遍？效率太差了八
avatar
n*5
15 楼
trie的每个node maintain一个list咋样？按照popularity 排好序的
好奇地问你这个面是过了没有？过了的话是不是说明你这题答得不错
反之。。

【在 s********l 的大作中提到】
: 我也觉得效率低 所以来请教的~
: 那个词 被选的次数多 哪个popular啊~
avatar
s*l
16 楼
过了~
不过 最后1分钟问的 感觉面试官随便问问的~
他也没说 对与错 但是 我觉得 复杂度太大了

【在 n*********5 的大作中提到】
: trie的每个node maintain一个list咋样？按照popularity 排好序的
: 好奇地问你这个面是过了没有？过了的话是不是说明你这题答得不错
: 反之。。
相关阅读
请问consultant company是不是就是类似于ICC的公司？求解，可以让两个不同公司一起申请h1b吗？陈果仁遇害三十周年！凶手30年未赔付一分一毫未坐一天牢微软是不是争议最大的公司intel 这个公司怎么样？Uber去年在中国亏了10亿美金再说推特，以及Peter Liang #justice4liangGoogle Quantitative Analyst internship 求Host收留MS有啥可吵的发现好虫最近不来了？好虫、爱丽丝头，还有从不学习，要不要再开个赌局？PIP了，要不要辞职？没有OPT 跪求今年暑假实习的内推请问各位大神，现在NSC的OPT extension是不是特别慢啊听到的一个面试故事国内的IT DIRECTOR年薪就50万人民币靠，号召大家上腿特的被删了？急问：开101进城要收费么？880要收费么？请问这个工资在雅图税率问题，到手多少呢被人诬告的经历：我的建议 (转载)
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。