|
在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大得多。
| 
发表于 2024-9-4 07:01:19
