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行么
相关阅读
实习记者写的搞笑文章 zz《20年来声誉下降最快的职业》2007第一贴,Happy New Year!!!![合集] 昨天的google面试题找工的一些资料分享 (转载)google面试全过程(简装版)昨天bloomberg on-site面试[合集] 问一下GAP期间的VOLUNTEER 微软面世经过40道Quant面试金融问题，你能做多少？风水轮流转化学找工作一点经验！OPT和H1期间交税，5000刀和5年[合集] 迟到的jobhunting经验（半导体方向）关于 OPT 加急 的小结(1) C1的一点经历[合集] 请教关于intershipgoogle phone interview今天的cisco interviewgoogle 首轮面世汇报积累RP. Capital one 面经。
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。