logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
问一道google老题
avatar
问一道google老题# JobHunting - 待字闺中
p*u
1 楼
design an algorithm to return top 10 searched location on google map。
先查location是不是在 bloomfilter里，如果是，在把它放入另外的hashtable并计数
。这个解法如何？bloomfilter的目的是去掉大量one time的location。
avatar
p*u
2 楼
没人知道吗？
avatar
b*8
3 楼
啥是BloomFilter？
avatar
P*o
4 楼
感觉这个方法可行吧
另外，为什么还要用一个hashtable呢
bloomfilter边计数，边compare不行么
最后排序，找出其中最大的10个数

【在 p*****u 的大作中提到】
: design an algorithm to return top 10 searched location on google map。
: 先查location是不是在 bloomfilter里，如果是，在把它放入另外的hashtable并计数
: 。这个解法如何？bloomfilter的目的是去掉大量one time的location。
avatar
f*t
5 楼
不行吧，因为bloomfilter有false positive，存count应该还是要用hashtable。
另外既然是要找最大的10个数，用max heap存不是更好吗？从前15个数里找出10个最大的就可以了

【在 P*****o 的大作中提到】
: 感觉这个方法可行吧
: 另外，为什么还要用一个hashtable呢
: bloomfilter边计数，边compare不行么
: 最后排序，找出其中最大的10个数
avatar
p*u
6 楼
bloomfilter不能计数吧？就算计数，也只是用几个bit，远不够呀。
avatar
p*z
7 楼
我有一个想法，O(1)的复杂度，大家喷一下。
1) 先抽样10000个记录.
2) 建立一个linkedHashTable来count个数
3）quickSelect找前10个O(10000)
这样就可以constant 的复杂度！欢迎高手狂喷。。。
avatar
p*u
8 楼
可要求的不一定在你的抽样里。
avatar
p*z
9 楼

我觉得是否用抽样，可以跟interviewer商量！不过就算不抽样，这个方法也是O（n）.
我只是觉得，如果重复度比较高的，可以考虑抽样的方法，节省时间

【在 p*****u 的大作中提到】
: 可要求的不一定在你的抽样里。
avatar
P*o
10 楼
为什么不能计数呀
另外建一个数组map空间到bloomfileter行么

【在 p*****u 的大作中提到】
: bloomfilter不能计数吧？就算计数，也只是用几个bit，远不够呀。
avatar
p*z
11 楼

那这样跟普通的hashtable有什么两样？

【在 P*****o 的大作中提到】
: 为什么不能计数呀
: 另外建一个数组map空间到bloomfileter行么
相关阅读
第二次出来找工作，世道大不一样啊Re: 本公司提供短期、长期OPT挂靠。有人考过Clinical Laboratory Scientist Liscence 吗？分享下我找工作的经历(fresh cs phd，美国东北部，长，唐)G的recruiter要跟我在gchat上通话借人气一问，嵌入式工程师的职业规划？H1b extension工作的问题请帮助！面试归来, 求BLESS提前多久辞职？求祝福有面过google test engineer的吗？电话面试后一周了还没消息你们公司招corporate finance的人不？老驴的故事公司说和实习的mentor认识，问我可不可以拿到mentor的推荐信。。。【已派完】宝贝今天满月，顺便给爸爸带来一份新工作。找工真是漫漫长路纯好奇问个sign on的问题高分子转行做什么好？ (转载)面试是fail掉一轮就全fail掉么？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。