【面试必备】如何在10亿数中找出前1000大的数?

小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。

之前小史在BAT三家的面试中已经挂了两家,今天小史去了BAT中的最后一家面试了。

简单的自我介绍后,面试官给了小史一个问题。

【面试现场】

题目:如何在10亿数中找出前1000大的数?

小史:我可以用分治法,这有点类似快排中partition的操作。随机选一个数t,然后对整个数组进行partition,会得到两部分,前一部分的数都大于t,后一部分的数都小于t。

小史:如果说前一部分总数大于1000个,那就继续在前一部分进行partition寻找。如果前一部分的数小于1000个,那就在后一部分再进行partition,寻找剩下的数。

小史:首先,partition的过程,时间是o(n)。我们在进行第一次partition的时候需要花费n,第二次partition的时候,数据量减半了,所以只要花费n/2,同理第三次的时候只要花费n/4,以此类推。而n+n/2+n/4+...显然是小于2n的,所以这个方法的渐进时间只有o(n)

(注:这里的时间复杂度计算只是简化计算版,真正严谨的数学证明可以参考算法导论相关分析。)

半分钟过去了。

小史一时慌了神。

他回忆起了之前吕老师给他讲解bitmap时的一些细节。突然有了一个想法。

小史在纸上画了画。

理解了算法之后,小史的代码写起来也是非常快,不一会儿就写好了:

TopN.java

Main.java

运行结果:

面试官看了一下。

小史熟练地介绍起了自己的项目,由于准备充分,小史聊起来游刃有余。面试官问的几个问题也进行了详细的解释。

小史走后,面试官在系统中写下了面试评语:

【遇见吕老师】

小史回到学校哼着歌走在校园的路上,正好碰到吕老师。

小史把面试情况和吕老师说了一下。

小史:感悟还挺深的。虽然平时做过topN的问题,知道分治法时间更少。但是碰到具体问题的时候还是要具体分析,这种大数据量的情况下反而用堆会更快。

原文发布于微信公众号 - Java后端技术(JavaITWork)

原文发表时间:2018-10-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏女程序员的日常

腾讯面试经验2

时间:2017年10月16日11:30面试。 地点:重庆万达艾美酒店。 信息:女,本科应届生,面试后台开发岗位。   在深圳的面试已经全部结束了,偶然间听朋...

9431
来自专栏程序员互动联盟

编程到底难在哪里?

疑惑一:数据结构和算法学的晕乎乎的?怎么破局? 数据结构是算法的基础,原则上不推崇先去学习数据结构,数据结构就是对基础的组合和应用了,在基础语言还不行的情况下,...

36510
来自专栏程序人生 阅读快乐

代码之髓:编程语言核心概念(图灵程序设计丛书)

《代码之髓:编程语言核心概念》作者从编程语言设计的角度出发,围绕语言中共通或特有的核心概念,通过语言演变过程中的纵向比较和在多门语言中的横向比较,清晰地呈现了程...

1032
来自专栏ATYUN订阅号

【盘点】最适合AI开发的六种编程语言

? 自从AlphaGo战胜柯洁,AI风头就一直无人能及。而对于开发者来说,AI是一个十分广阔的领域,很多编程语言都可以利用AI进行开发。下面是整理出的几种典型...

34712
来自专栏Java职业技术分享

Java可以自学吗?自学Java要多久?自学Java能找到工作吗?

那么,这些人在选择自学的道路时,一定也有想过很多,比如:自学Java找工作好找吗?自学要学习多久呢?Java可以自学吗?

7990
来自专栏Cloud Native - 产品级敏捷

A/B Test;名字取得不好, 很容易让人产生误解

2017.9.24, 深圳, Ken Fang A/B Test;名字取得不好, 很容易让人产生误解, 认为它是 “测试”。 其实… A/B Test 是...

1829
来自专栏PPV课数据科学社区

【工具】如何根据变量类型选择数据分析方法?

面对大量数据,你将如何开展数据分析?您会选择什么样的数据分析方法呢?您是否看着数据感到迷茫,无所适从。认真读完这篇文章,或许你将有所收获。 把握两个关键 1、抓...

2866
来自专栏少儿编程

你肯定学了假的编程

很多人开始学编程的时候都会有一个疑惑,我到底该学什么编程语言?参考的依据要么来自“砖家”、要么是来自热门语言排行榜、要么是来自薪资排行榜等。殊途同归,所有的人都...

1431
来自专栏程序人生 阅读快乐

《C专家编程》

《C专家编程》展示了最优秀的C程序员所使用的编码技巧,并专门开辟了一章对C++的基础知识进行了介绍。

1162
来自专栏程序人生 阅读快乐

Go语言编程(完整版)

《Go语言编程》首先引 领读者快速浏览Go 语言的全貌,迅速消除读者对这门语言的陌生感,然后循序渐进地介绍了Go 语言的面向程和面向对象的编程语法,其中穿插了一...

1512

扫码关注云+社区

领取腾讯云代金券