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 排好序的
: 好奇地问你这个面是过了没有？过了的话是不是说明你这题答得不错
: 反之。。
相关阅读
roth 401k,roth IRA, 401k到底什么区别？年薪多少的人该入哪个这个算是非正式return offer？ 我是不是需要尽快回复？帮推荐湾区做视频的公司Ooyala的big data职位InsertionSort和ShellSort不要开贴讨论网友,违者封14天.ericsson research media 组情况 （NMS）关于titleHR约后天谈（follow up）但是没说是不是好消息，是不是没戏了？［求内推］UX/UI design position中型公司被大型公司收购，招人薪水 一般怎么定？有人是在网上签电子版的合同吗？请教Amazon家的group interview[BSSD]回国一趟回来做题很难进入状态了，顺便问下那个Merge k Sorted请问：邮寄OPT 资料时，需要寄回邮信封吗？有没有大牛在tableau的?G 才没那么容易衰被雷求refer求内推求bless面试 Expectation　问题一个疑惑有人了解Google Adsense for Search 组么？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。