在2010年至2019年时期,我在谷歌采访了数十名软件工程师候选人。我几乎总是问一样的面试问题。另外,这个问题恰好在谷歌的禁名单上,由于它在Glassdoor和其他面试网站上公开供给,但我继续运用它,由于我从候选人那里得到了良好的信号。
Daniel Tunkelang对这个问题亦有类似的积极经历,但在2011年就退役了:“离休是一个伟大的面试问题”。这本身便是一本很好的读物,但因为我对这个问题的经验更广泛,我决定把它写下来。
为何这是一个很好的面试问题
问题起始很简单。非常简单,以至于有些候选人认为她们无正确理解它。从那里,它探索了候选人对各样基本算法和数据结构概念的理解。
另外,正如我所介绍的那样,这个问题有足够的范围来筛选出好的候选人,即使候选人以前见过这个问题,这便是为何我成功地运用了它,尽管它被谷歌禁止了。我两次问招聘委员会我是不是应该停止运用这个,她们对此无问题。
面试
这是一个45分钟的软件工程职位技术面试,从初级到中级候选人。亦许令人惊讶的是,初级候选人有时在这个问题上排名更高,由于她们的数据结构和算法知识更鲜嫩。但这种模式并不广泛。优秀的高级候选人对面试完全无问题。
有些轶事始终留在我身边: 我曾经有一个有15年工作经验的候选人给了我非常多态度,能够问她们这么简单的问题,同期又在奋斗处理。我让候选人用所有的铃铛和口哨处理全部问题最快的是在20分钟内,由滑铁卢大学的一名新生完成,他是参加高中比赛的那种。我看到的最令人懊丧的失败是多伦多大学的一名博士毕业生,他没法在45分钟内为问题的第1部分生成工作代码。一位候选人预先告诉我,她们已然看到了问题。我咧嘴一笑,说:“太好了,因此你应该晓得怎样处理它!”她们仍然在与之斗争。另一位候选人清楚地记住认识决方法代码,并立即编写了它。我需求她们退后一步,完成我需求她们完成的过程。她们亦挣扎了。她们以前亦不诚实地看过它。
我首要告诉候选人,我爱好听她们的思维过程,在我需求她们这般做之前,我不想让她们写代码。而后我告诉她们,这个问题有两个部分。
第1部分
问题
“写一个给定字符串的函数,确定它是不是是两个字典单词的串联。”
当被问到时,我解释说,字典能够做为查找成员字符串的功能。
处理方法
任何优秀的候选人都应该能够快速找到问题的蛮力/琐碎处理方法,即:在所有可能的位置拆分输入字符串,并在字典中查找双方。
不外,你会惊讶于有多少候选人难以找到这个处理方法。有些人想出了一个贪婪的算法,找到字典中的第1个前缀,而后返回字符串的其余部分是不是在字典中。有些人可能会认为蛮力处理方法太简单/效率低下,并立即寻求更快的处理方法。我试着引导她们先提出任何处理方法。
在这一点上,我需求她们为它编写代码。以下是Python中的单行处理方法代码,运用生成器: def splitString2(s):
返回任何(inDict(s[:i])和inDict(s[i:])针对iin range(1, len(s)))大都数候选人都写一个for循环,这一样是能够接受的。
运行时间
而后我需求候选人分析这个处理方法的运行时间。
大都数候选人意见O(n)做为答案。(让咱们假设制作子字符串s[:i]和s[i:]是常量时间。)我会问她们怎样实现字典函数,使这个处理方法是O(n)。她们大多意见,倘若做为散列函数实现,将是O(1)查询。而后我推动她们这般做,直到她们认识到字符串的字典查询函数的任何实现充其量都是o(n),因此呢处理方法的总运行时间是O(n²)。
更快的处理方法
倘若候选人火速就能走这么远(即不到20分钟),我会问候选人她们是不是能想出一种办法来加快这个处理方法。大都数候选人会有点挣扎。我告诉她们,倘若字典查询按原样运用函数,那样这个算法是渐近最优的(我不需求她们证明,但你能证明这一点吗?)。因此呢,任何加速都需要字典的区别暗示方式。
非常好的候选人认识到,前缀的字典查询正在做非常多重复的工作,经过以树的形式暗示字典来避免,更确切地说,这是一个尝试。我让几个候选人就地重新尝试,而其他人则依稀记得她们。无论怎样,将字典暗示为一个尝试将使字典O(n)总数中的所有前缀都检测。咱们仍然有检测所有后缀的问题。经过对叫作性,咱们还能够将字典中包括单词的另一个尝试反转。届时,检测字典成员资格的所有后缀亦是O(n)。咱们只需要一个o(n)体积的数组来保留这个。而后,咱们只需要将前缀和后缀结果相交,并找到重叠。总算法是O(n),因此呢是最优的。
我不需求候选人为此编写代码。倘若她们被卡太久,我会跳到第2部分。
第2部分
问题
“编写一个给定字符串的函数,确定它是不是是多个字典单词的串联。”
一样,咱们从将字典暗示为查找函数起始。当被问及字典中的字符串本身是不是应该经过测试时,答案是肯定的。
处理方法
我再次强调,我爱好先看到任何处理方法。优秀的候选人认识到,她们能够简单地将处理方法从第1部分修改为递归处理方法。例如: def splitString(s):
倘若inDict(s):
返回True
返回任何(inDict(s[:i])和splitString(s[i:]) for i inrange(1, len(s)))然而,许多候选人在为递归处理方法而苦苦挣扎。
运行时间
分析递归处理方法的运行时间对有些人来讲可能是一个挑战。一样,假设字符串拆分操作是O(1),归根结底是认识到,在最坏的状况下,字符串被拆分为所有可能的拆分,并且有o(2^n),与字典查询成本相结合,引起O(n.2^n)运行时。
更快的处理方法
而后我需求一个更快的处理方法,这次我期望候选人找到一个。优秀的候选人观察到,针对相同的输入,splitString函数被递归调用,因此呢到达了记忆或动态编程做为解救办法。
我不需求她们为此编写代码,只需转到运行时分析。
运行时间
在这儿正确分析的关键是认识到,咱们仅在带有原始字符串后缀的splitString函数上递归,该后缀有n。针对每一个后缀,咱们执行O(n)操作,思虑到字典查询成本,该操作变成为了O(n²)。总运行时为O(n³)。
我不需求候选人展示这个,但假设字典是做为查询功能供给的,瞧瞧你是不是能证明这是最优的。
更快的处理方法
针对大都数候选人来讲,咱们日前已然无时间了,但倘若有时间,我问候选人她们是不是能够想出一个更快的处理方法。倘若她们已然到达了第1部分的三方解,她们将在这儿意见三办法,这将形成一个组合的O(n²)运行时。
瞧瞧你是不是能证明这是最优的。
更新:假设字典中的单词数量比n大得多。
|