p*****u
发帖数: 310 | 1 design an algorithm to return top 10 searched location on google map。
先查location是不是在 bloomfilter里，如果是，在把它放入另外的hashtable并计数
。这个解法如何？bloomfilter的目的是去掉大量one time的location。 |
p*****u
发帖数: 310 | |
b*******8
发帖数: 37364 | |
P*****o
发帖数: 1077 | 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。
|
f*******t
发帖数: 7549 | 5 不行吧，因为bloomfilter有false positive，存count应该还是要用hashtable。
另外既然是要找最大的10个数，用max heap存不是更好吗？从前15个数里找出10个最大的就可以了
【在 P*****o 的大作中提到】
: 感觉这个方法可行吧
: 另外，为什么还要用一个hashtable呢
: bloomfilter边计数，边compare不行么
: 最后排序，找出其中最大的10个数
|
p*****u
发帖数: 310 | 6 bloomfilter不能计数吧？就算计数，也只是用几个bit，远不够呀。 |
p****z
发帖数: 55 | 7 我有一个想法，O(1)的复杂度，大家喷一下。
1) 先抽样10000个记录.
2) 建立一个linkedHashTable来count个数
3）quickSelect找前10个O(10000)
这样就可以constant 的复杂度！欢迎高手狂喷。。。 |
p*****u
发帖数: 310 | |
p****z
发帖数: 55 | 9
我觉得是否用抽样，可以跟interviewer商量！不过就算不抽样，这个方法也是O（n）.
我只是觉得，如果重复度比较高的，可以考虑抽样的方法，节省时间
【在 p*****u 的大作中提到】
: 可要求的不一定在你的抽样里。
|
P*****o
发帖数: 1077 | 10 为什么不能计数呀
另外建一个数组map空间到bloomfileter行么
【在 p*****u 的大作中提到】
: bloomfilter不能计数吧？就算计数，也只是用几个bit，远不够呀。
|
p****z
发帖数: 55 | 11
那这样跟普通的hashtable有什么两样？
【在 P*****o 的大作中提到】
: 为什么不能计数呀
: 另外建一个数组map空间到bloomfileter行么
|
