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行么
相关阅读
Amazon onsite一般能推迟多少天？想多一点时间准备opt EAD 卡上姓和名搞错了有sponser机械工程，工业工程小硕的职位么我艹的勒export controlFEA 还是 Product Engineer?问一个RSU的问题title到底有多重要***** H1B申请求教，多谢大家 ******关于sponsorship的选项OPT必须full time paid job才能维持吗大家是如何找到另一个城市工作的？Google美国和Google英国能同时申请吗？请问一下A家的onsiteOPT后转F-2/H-4怎么衔接H1?小饭Phone Screening的经验明天onsite求blessH1B申请材料3月31日（周六）usps寄到能行吗？Amazon面试连续两次被放鸽子细节求指教...Microsoft 校园面试面经 + Onsite 求 Bless
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。