中值问题

吴军老师得到97封信

Google面试题:假如有一个巨大的数组(你可以理解成一串数字),如何用最有效的方法找到它的中值?

重点关注:中值、巨大的数组、最有效的方法(是指时间上最快,还是最节省空间),本道题目追求的是时间上的有效,也就是要速度快

1.比较差的解决方法

先排序,再找到中间那个数字

首先,他掉进了题目中第二和第三个坑。排序是一种解决办法,但是绝不是最有效的,而且当面临“巨大的数组”时,为了找到一个数排序,显然做了太多的无用功。其次,他没有体会到考他这道题背后的目的。作为Google这样的公司,面试题不可能太容易,排序这种想法,是个人都能想到。考他这道题,一定是因为对于Google来讲,要处理的数据量太大,必须找到比排序更好的方法。

2.善于沟通的人

我知道,你考我这道题不是要寻找排序这样的方法,虽然排序也能解决问题,你能否给我点时间,让我想想更好的方法?

这样的回答有两个好处,首先是告诉对方他知道考这道题的目的,同时自己懂得排序,这是一个好的沟通者。其次,他给自己赢得了时间。当然,如果过了几分钟他还是想不出来,有经验的面试者会说,能否给我点提示呢?在工作中,请求帮助永远比自己闷头做不出来要好。在面试时,大约有20%的人在思考了一段时间后,能够想出更好的办法。

在这个问题上,一些候选人会想出一个比排序更好一点的方法,那就是我们前面提到的“N个加油站中找到K个距离最近的加油站”的那个方法。这里,只要把K设置成N的一半即可。忘了那一期内容的朋友,可以回头再读读那封来信,链接在信的底部。这种方法只对数值小的一半进行了排序,因此大约可以省一半时间。但是正如我们在课程一开始讲的,对于计算机科学来讲,省一半时间意义不是很大,我们追求的是更高的效率。因此,我们还要找更好的方法。

上述方法为什么效率不高呢?其根本的原因是做了太多的无用功!这道题只要求找到中值,至于那些大于中值的数字彼此的关系是什么,小于中值的数字相对的次序是什么,我们其实不用关心。排序的方法,把这些工作也顺带做了,显然多做了很多事情,自然效率高不起来。因此,要想找到好方法,一定要避免排序。

3. 最有效的方法

当然,你可能会问了,如果不排序,又怎么知道谁是中值?这确实是一个好问题。在进一步讲解我们的方法之前,我们举一个具体的例子。
假如数组中的数字是:1, -5, 3, 7, 1000, 2, -10
排好序后是这样的:-10,-5,1,2,3,7,1000

这个序列可以看得一目了然,2就是中值,因为比2小的数字都在它的左边,有三个,比它大的数字都在右边,恰好也是三个。但是,如果我们把这七个数字按照下面的方式排列:
-5,1,-10,2,1000,3,7
我们会发现,小于2的在左边,有三个,大于2的在右边,也是三个,因此也能得到2是中值的结论。所不同的是,整个数组并没有从小到大排列。其实,只要我们能够把数组重新整理成后一种样子,对于找中值是足够的。

那么怎么不经过排序,让小的数字都到左边,大的数字都到右边呢?讲起来也很简单。我们可以从数组中随便找一个数字,让它和数组中每一个数字去比较大小。如果比它小,就放在左边,如果比它大就放在右边。这个过程被称为划分(Partition)。

当然,除非你的运气特别好,第一次就随机挑上了中值,否则划分的结果肯定一边多一些,一边少一些。比如有100个数字,第一次划分之后,大的一边有60个,小的一边有40个。很显然,中值一定是在大的一边,也就是有60个数字的一边,而不可能在小的一边。因此第二次我们只要在大的一边随机选取一个数字,再做一次划分,看看是否平衡就可以了。

需要强调的是,第二次分割要考虑的数字比第一次少了一小半,如果还没找到,第三次划分的范围又缩小了一小半,直到找到为止。可以证明,这种方法通常复杂度非常低,大约只相当于把整个数组扫描了三四遍而已。

如果我们要寻找10亿个数字的中值,采用排序的方法大约需要1万亿次计算,而采用这种划分的方法大约只需要30亿次计算,时间相差300倍。这里面效率的提高完全来自于少做了很多无用功。

讲到这里,你已经理解了为什么Google会问这个问题。Google这样的公司,每天都要处理海量的数据,所使用的方法必须是最优化的,否则很轻易地就浪费掉上百倍资源。

如果你还记得我在之前讲过的快速排序算法,对今天的内容是否有似曾相识的感觉呢?事实上今天讲的方法和快速排序的方法非常相似,都是用一个随机的数值对数组进行划分。如果一个候选人掌握了快速排序思想的精髓,而不仅仅是背下来那个算法,这道题应该能很好地解决。实际上,像Google这样公司的面试,很少会直接考书本中的内容,但是通过一个实际问题很容易考察出求职者能否灵活运用所学知识。

从这个例子中我们可以总结出如下三点经验:

  1. 少做事是提高效率的关键。

  2. 一流人才和二流、三流的差别在于,后者虽然也能完成任务,但是未必能把事情做到最好,而一流的人总是能找到在当下最好的方法。而一种方法的好和坏,可以差出几十、上百倍的效率。这就是我讲的工程师水平差一级,贡献可以差出一个数量级的原因。

  3. 对所学内容掌握得好坏高低,通常不是靠直接考核那些内容能知道的,而是要看能否运用所学。只有会用了,才是真的学到手了。

4. 后续问题

这个问题其实还只是一连串问题的开始。如果候选人很快答上了这个问题,我还会让他证明为什么上述方法的计算复杂度只相当于把数组扫描几遍,最好的情况和最坏的情况会是什么样,什么时候会发生等等。此外,当数组特别特别大,以至于一台服务器都存不下了,应该怎么处理?

因此,一个好的求职者一定是能够活学活用知识的,而不是简单背一下答案。希望这些面试的经验也对你有所启发。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 215,923评论 6 498
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,154评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 161,775评论 0 351
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,960评论 1 290
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,976评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,972评论 1 295
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,893评论 3 416
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,709评论 0 271
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,159评论 1 308
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,400评论 2 331
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,552评论 1 346
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,265评论 5 341
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,876评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,528评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,701评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,552评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,451评论 2 352

推荐阅读更多精彩内容

  • 吴军 我一直在强调人要少做事情,因为提高效率的根本在于少做事情,事实上对计算机来讲也是如此。今天我们再讲解一道Go...
    康哥来了阅读 442评论 0 0
  • 少做事情:因为提高效率的根本在于少做事情,想清楚再行动 以下是得到《吴军谷歌方法论》的一篇文章: 文章有些长,请耐...
    Anna贵方007_3031阅读 955评论 1 3
  • 数组 记录《剑指offer》中所有关于数组的题目,以及LeetCode中的相似题目 相关题目列表 说明 由于简书...
    wenmingxing阅读 1,517评论 1 12
  • 我每次交钱,都源于稀缺性。 要涨价了,我就急忙去了解。我当时是因为没有人能带领我走出这条路,没有一个好的领导跟我沟...
    bangbang雪阅读 152评论 0 0
  • 穿行一片园林,灯花满地,光灿灿,明媚满目。又用细碎电灯,织成仙鹿、玉兔,通体发炽光。一时宛若置身仙境。 想写赞美诗...
    行吟斯基阅读 786评论 1 4