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行么
|