一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 840|回复: 7
收起左侧

[算法题] 求教kth most frequent element

[复制链接] |试试Instant~ |关注本帖
ryuichist 发表于 2015-4-9 06:10:34 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
如题,也是比较经典的一道题了。自己想了个方法,想看看大家有没有什么别的好思路

我自己大概的思路是,假设input是char[]
先过一遍array,放到一个hashtable里面,key是每个char,value是出现了多少次

然后建priority queue,自己写个comparator。

不知道还有没什么更好的思路

本帖被以下淘专辑推荐:

stellari 发表于 2015-4-9 11:49:57 | 显示全部楼层
这题最好的做法估计也就是这样了。主要是可以在这个题的基础上加其他的follow up,比如:如果element的总数非常非常大,怎么办?
回复 支持 反对

使用道具 举报

 楼主| ryuichist 发表于 2015-4-9 12:23:39 | 显示全部楼层
stellari 发表于 2015-4-9 11:49
这题最好的做法估计也就是这样了。主要是可以在这个题的基础上加其他的follow up,比如:如果element的总数 ...

哦,还没想到这个情况,能给点提示吗
回复 支持 反对

使用道具 举报

stellari 发表于 2015-4-9 14:32:08 | 显示全部楼层
ryuichist 发表于 2015-4-9 12:23
哦,还没想到这个情况,能给点提示吗

“非常大”的意思就是能存在文件里,但是一次放不到内存中。可以先把所有的element按照比如hash(x) % 1000的格式先分割到f1, f2, ..., f1000这1000个小文件中,这样保证相同的element肯定在同一个小文件中;且每个小文件能够单独放入内存里。然后分别对每个小文件找Top K的元素;最后再找这1000K个元素中的Top K即可。

你不妨去看看关于Scalability和Memory方面的面试题。这种题出现的概率还是挺高的。
回复 支持 反对

使用道具 举报

干.什么 发表于 2015-4-12 04:52:59 | 显示全部楼层
Many big data analysis companies like Palantir love this interview problem as its' part of their daily job.

Selection sort (a.k.a. Quick Select) can be better! It is mostly used in real-time streaming data analysis compares to the external sort which requires access to hard drive (memory latency is smaller than hard drive).

In worst case, quick select could be O(n + klogk), however, if we only need to find top k most, the O(klogk) part can be eliminated, which leaves an O(n) only.
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-4-12 08:21:15 | 显示全部楼层
楼主可以详细解释一下comparator,今天做cc150正好遇到了这个不是很明白
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-4-12 09:15:37 | 显示全部楼层
stellari 发表于 2015-4-9 01:32
“非常大”的意思就是能存在文件里,但是一次放不到内存中。可以先把所有的element按照比如hash(x) % 100 ...

如果对于每个小文件都取第K大的元素的话,那会不会有错误呢?比如说某一个文件的第k个都特别大,另外一个文件中的k个都特别小
回复 支持 反对

使用道具 举报

stellari 发表于 2015-4-12 22:14:56 | 显示全部楼层
JamesJi 发表于 2015-4-12 09:15
如果对于每个小文件都取第K大的元素的话,那会不会有错误呢?比如说某一个文件的第k个都特别大,另外一个 ...

是,所以用这种方法的话,不能只取m个文件中每个文件的第K个,而要取前K个,这样才能保证总的前K个在这m x K个元素当中。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 20:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表