阿里面试题 海量数据TOPK问题求助!!!

阿里面试题

  1. 在十万的数字中找出前100?
    快排patition+二分,堆
  2. 10亿的数字找前10万,空间给1亿?
    (分治法加堆),时间复杂度klogk
  3. 100亿数字找前10亿,空间1亿?

主要是第三个不怎么会,求大佬解疑!!!

附面经:https://www.nowcoder.com/discuss/424615

#阿里巴巴实习##阿里巴巴##笔试题目#
全部评论
第三个问题不是算法问题了,应该是在问工程上的实现 基本得靠切分到多台机器并行运算来解决 具体怎么做,看下那个64马找前四的问题 我觉得是这样
点赞 回复
分享
发布于 2020-05-11 23:30
我讲讲我的思路:数字转换为2进制,从高位到低位遍历,如果当前位为1,则count++。如果count刚好等于10亿,那么就刚好得到结果。如果count小于10亿,说明当前位为1的数在前10亿以内,并且更新目标数,10亿减当前位为1的数的个数。
点赞 回复
分享
发布于 2020-05-16 14:03
联易融
校招火热招聘中
官网直投
不知道你第三个 面试官有机器要求没,还有就是给的空间具体多大。个人觉得如果没机器要求就分布式。单机的话, 如果空间足够大  ,我觉得可以用位图;如果空间不够大的话  ,可以分次,比如每次找出前一亿,这样10次就行。 思路有错的话 望指出。
点赞 回复
分享
发布于 2020-05-18 16:58

相关推荐

1 15 评论
分享
牛客网
牛客企业服务