[见题拆题] 大厂面试算法真题解析 - 第一期开张

如今想要收获大厂offer,在面试的前几轮,总是躲不开算法这座大山。

常听人说,算法很难。这话没错。算法本身是是一个艰深的方向。但是算法题却有据可循。通过有针对性的学习和练习,我们完全可以掌握解题的基本方法和技巧,见题拆题,扫清通往offer之路上的障碍。

看看手上这些各个大厂的面试算法真题,我想,不如开始一个新的系列,和大家一起解析真题,学习解题方法,开阔解题思路。头脑越练习,越灵光。

接下来,就让我们来看第一题:

题目

[来自Google]

Given a list of numbers and a number k, return whether any two numbers from the list add up to k

给定一组数字,以及一个数字k,确定这组数字中,是否存在任意两个数字,其相加之和等于k

解析

初次见到一个问题,如果暂时没有什么特别清晰的思路或灵感,不妨安下心来,首先想一想这道题目的暴力解法。

简单粗暴的暴力解法不考虑效率和美观,只考虑正确性,所以往往效率较低。但是,通过观察暴力解法中冗余或者重复的部分,我们就可以找到进一步优化的切入点,想出更有效率的算法

小技巧: 在面试中,如果暂时头脑空白,想不到漂亮的解法,不妨坦率地用简洁的话语先描述一下暴力解法,在这个过程中发现思路,找到优化解法。这个过程,也有助于面试官考察你的整体解题思路,还可能给你加分哟

暴力解法

这道题的暴力解法很简单。
只要将数组中所有数字对求和,然后和给定的数字k相比较,就知道是否有和k相等的值了。
假设数组中有n个数字,将暴力解法写成伪代码pseudo code的话,就是这个样子:

function sumEqualsToK(array, k):
for i=1 to n-1
  for j=n+1 to n
    if array[i] + array[j] == k
      return true
return false

暴力解法使用了两个嵌套在一起的循环,显而易见,它的时间复杂度是O(n^2)。为了降低时间复杂度,我们来分析一下暴力解法中冗余或者重复的部分。

暴力解法试图对数组中 所有 数字对进行求和操作。
这部分操作是否存在冗余的部分呢?
我们能不能减少需要查看的数字对的数量呢?
想要对这一点进行优化,我们就要利用题目中的另一个线索,也就是数字k了。

其实这道题目就是在给元素“配对儿”。
对于数组中的任一数字array[i],如果希望它和它的“另一半”相加之和等于k,那就意味着它的“另一半”的值必须是k-array[i]
也就是说,只要数组中也存在一个等于k-array[i]的元素,就可以满足相加等于k这个条件了:

例子:
k = 10
array = [ 4, 2, 5, 6, 8 ]

那么我们寻找的“另一半”们就是:[ 10-4, 10-2, 10-5, 10-6, 10-8 ]
也就是 [6, 8, 5, 4, 2]

这样一来,我们的问题就转换成:
给定数组 array = [ 4, 2, 5, 6, 8 ],以及数组 target = [ 6, 8, 5, 4, 2 ],
array[i]和target[i]是不是同时存在于array中

在这个例子中,大家要格外关注5这个元素
5正好是k值的一半,所以array和target都包含了5
只有在原数组中包含了两个5,才能相加等于10

好了,现在我们已经有了进一步优化暴力解法的思路了。
在揭晓优化解法的伪代码之前,请你先开动脑筋,试着自己把代码写出来吧

思考~思考~


图片来自网络
优化解法

时间到~下面就是优化算法的伪代码了:

function sumEqualsToK(array, k):
for i=1 to n
  if map contains array[i]
    return true
  else
    put k-array[i] into map
return false

在优化算法中,我们使用了一个map来记录我们想要寻找的“另一半”的元素,也就是之前例子里面提到的target

接下来,我们只需要遍历array一次。
如果array[i]已经和map中的元素相符,就说明array[i]和我们之前遍历到的某一个元素恰好是相加为k的“一对儿”,算法直接返回true
如果不相符,那么我们就把k-array[i]放进map中去,期待接下来遍历到的元素能够和k-array[i]相符。

这个优化算法只需要遍历array一次,所以它的时间复杂度只有O(n)。而我们最多也只会将array中所有元素的“另一半”放进map中去,所以算法的空间复杂度也是O(n)

实现

想出解法只是第一步,为了正确地实现解法,我们还需要考虑实现中的细节。
让我们想一想这个问题的输入和输出:

输出

这个问题的输出很简单,就是一个boolean值,true/false

输入

题目中对于输入的表达较为模糊
没有说明array的长度,也没有说明元素和k的具体类型
格外要注意的是,由于在解题过程中需要进行求和操作,我们要谨慎选择在实现中使用的变量类型。两数之和的范围可能远远大于单一数字的范围,所以根据实现语言的不同,要小心避免求和操作造成溢出

小技巧:在面试中,遇到题目中比较模糊的描述,一定记得要和面试官沟通,以便得到更多信息。至少,要向面试官询问基本的输入输出的细节。这样一来,面试官可以看出你对于问题的思考较为全面和缜密,也是加分项呢

不同公司的面试方法不同,有些会要求候选人写下完整地实现解法,有些只需要候选人写出伪代码就可以了。但是在练习时,我建议大家还是尽量写下具体的实现,至少也要思考一下实现的细节。

在这个系列里,我不会给出具体的实现代码,因为大家掌握的实现语言各不相同。不过,欢迎大家提出实现时遇到的问题,我们可以集思广益,一起解决~

总结

这道题目很精巧。它不涉及任何著名的,大家耳熟能详的算法,但是可以很好地考察候选人对暴力解法进行优化的完整的思考过程,还可以考察候选人对于输入输出的要求所进行的思考。
小而强大~也许这就是Google使用这道题目的原因吧~

恭喜各位成功解决了第一道大厂面试真题~可以好好休息一下了~


图片来自网络

[转载请注明]


扫码学习慕课网技术课程
MongoDB 4.0新特性

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