Google求职面试解析：查找关系

欢迎阅读我在Google采访中问到的一系列难题中的下一篇文章， 这些难题在泄漏后被禁止。 从那以后，我辞去了Google软件工程师的职务，转而担任Reddit的开发经理一职，但是我仍然有一些很棒的话题。 迄今为止，我们已经研究了动态编程 ， 将矩阵提升 为查询 的功能和同义词 。 这次是一个全新的问题。

但是首先，有两点。 首先，Reddit的工作很棒。 在过去的八个月中，我建立并领导了新的Ads Relevance团队，并在纽约建立了新的开发办公室。 不幸的是，无论它多么有趣，我发现直到最近我都没有时间或精力去写博客。 恐怕我有点放弃了这个系列。 抱歉，延迟。

其次，如果您遵循了这些文章，那么在上一期杂志之后，您可能会认为我将开始研究查询的同义词选项。 尽管我想回到这个时候，但我必须承认，由于工作上的改变，我对该问题失去了应有的兴趣，到目前为止，我决定将其推迟。 但是，请保持联系！ 我欠我，我打算退还。 只是，你知道，过了一会儿...

快速免责声明：尽管采访候选人是我的专业职责之一，但该博客介绍了我的个人观察，个人故事和个人见解。 请勿将其用于Google，Alphabet，Reddit或任何其他个人或组织的任何官方声明。

搜索新问题

在上一篇文章中，我描述了我在长时间不可避免的泄漏之前使用了很长时间的最喜欢的问题之一。 从理论上讲，前面的问题很有趣，但是我想选择一个与Google公司更相关的问题。 当这个问题被禁止时，我想考虑新的限制找到一个替代品：使这个问题更简单 。

考虑到Google臭名昭著的采访过程，现在这似乎有点令人惊讶。 但是在那个时候，一个更简单的问题才有意义。 我的推理包括两个部分。 首先是务实的：尽管有很多暗示和简化，求职者通常不能很好地应对先前的问题，我也不总是完全确定为什么。 理论上的第二个问题：面试过程应将候选人分为“值得雇用”和“不值得雇用”两类，我很好奇是否可以通过问题更轻松些。

在澄清这两点之前，我想指出它们的含义。 “我并不总是确定一个人为什么会有问题”并不意味着这些问题毫无用处，因此我想简化面试。 即使是最困难的问题，许多人也能很好地应对。 我的意思是，当候选人遇到问题时，我很难理解他们所缺少的东西。

良好的面试可以全面了解候选人的长处和短处。 仅凭招聘委员会“失败”是不够的：招聘委员会确定候选人是否具有他们所寻找的公司特有的素质。 同样，“他很酷”一词也无助委员会决定在某些领域很强的候选人，但在另一些领域却令人怀疑。 我发现，更复杂的问题常常将候选人分为这两类。 有鉴于此，“我并不总是能确定一个人为什么会有问题”意味着“无法在这个问题上取得进展本身并不能描绘出该候选人的能力。”

将候选人分类为“值得雇用”和“不值得雇用” 并不意味着面试过程应将愚蠢的候选人与聪明的候选人区分开。 我无法回想起一个没有聪明，才华和动力的候选人。 许多人来自优秀大学，而其他人显然是非常积极的。 通过电话采访已经是一个很好的选择，即使在此阶段拒绝访问也不表示缺乏能力。

但是，我可以回想起许多人，他们没有为面试做充分的准备，或者工作太慢，或者需要太多的监督来解决问题，或者沟通方式不明确，或者无法将他们的想法转化为代码，或者所担任的职务根本不会导致“长期聘用”的定义含糊不清，视公司而定，面试过程是确定每个候选人是否满足特定公司的要求。

我阅读了很多有关评论的内容，这些评论抱怨面试问题过于复杂。 我很好奇，是否仍然可以为更简单的任务提出有价值的建议。 我怀疑这会发出有用的信号，而不会不必要地大喊候选人的神经。 我将在文章结尾告诉您我的结论...

基于这些想法，我正在寻找一个新的问题。 在理想的情况下，这是一个很简单的问题，可以在45分钟内解决，但还有其他问题，以便更强大的候选人展示自己的技能。 由于许多候选人仍在董事会上写作，因此实施起来也应该紧凑。 如果主题与Google产品相关，那么这将是一大优势。

最后，我解决了一个问题，这个问题是一些出色的googler精心描述并插入到我们的问题数据库中的。 现在，我已经咨询过以前的同事，并确保仍然禁止该问题，因此在面试中绝对不会问您。 我以对我来说似乎最有效的形式提出它，并向原作者道歉。

问题

谈论测量距离。 “手”是四英寸的度量单位，在英语国家中通常用于测量马高。 一光年是另一种度量单位，等于光的一个粒子（或波？）在一定秒数内传播的距离，大约等于一个地球年。 乍一看，它们之间的共同点很少，只是它们用于测量距离。 但是事实证明，谷歌可以很容易地转换它们：



这看起来似乎很明显：最后，它们都可以测量距离，因此很明显，这是一种转换。 但是，如果您考虑一下，这有点奇怪：他们是如何计算此转化率的？ 显然，没有人真正算过光年的手数。 实际上，您无需直接接受此操作。 您可以简单地使用众所周知的转换：

• 1手 = 4英寸
  
• 4英寸 = 0.33333英尺
  
• 0.33333英尺 = 6.3125e-5英里
  
• 6.3125e-5英里 = 1.0737e-17光年

任务的目标是开发一个将执行此转换的系统。 特别是：

在输入处，您可以使用一组初始度量单位，最终单位和因子的形式列出转换因子（以您选择的语言格式）的列表，例如：

  12英尺
脚码0.3333333
等 

这样ORIGIN * MULTIPLIER = DESTINATION。 开发一个采用两个任意单位值并返回它们之间的转换因子的算法。

讨论区

我喜欢这个问题，因为它有一个直观且显而易见的答案：只需将一个单位转换为另一个单位，然后转换为下一个单位，直到找到目标即可！ 我不记得有一个候选人遇到了这个问题，完全不知道如何解决这个问题。 这很适合“简单”问题的要求，因为以前的问题通常需要经过长期的研究和思考，然后才能找到解决问题的基本方法。

然而，许多候选人没有明显的暗示就没有意识到自己的直觉是可行的解决方案。 这个问题的优点之一是，它可以测试候选人提出问题的能力（进行取景），从而使其能够进行分析和编码。 正如我们将看到的，这里有一个非常有趣的扩展，需要新的概念上的飞跃。

就上下文而言，成帧是将非显而易见的解决方案的问题转换为等效问题的行为，其中以自然方式推导解决方案。 如果这听起来完全是抽象和不可理解的，对不起，但事实是如此。 当我提出这个问题的初步解决方案时，我将解释我的意思。 解决方案的第一部分将是开发和应用算法知识的练习。 第二部分将是操纵该知识的练习，以便获得新的且非显而易见的优化。

第0部分。直觉

在深入探讨之前，让我们充分探索“显而易见的”解决方案。 大多数所需的转换都是简单明了的。 任何在美国以外旅行的美国人都知道，世界上大多数地区都使用神秘的单位“公里”来测量距离。 要进行转换，您只需将英里数乘以1.6。

我们一生中都遇到过这样的事情。 对于大多数单位，已经有一个预先计算的转换，因此您只需要在相应的表格中查看即可。 但是，如果没有直接转换（例如，从手工到光年），则建立转换路径是有意义的，如上所述：

• 1手 = 4英寸
  
• 4英寸 = 0.33333英尺
  
• 0.33333英尺 = 6.3125e-5英里
  
• 6.3125e-5英里 = 1.0737e-17光年

这很简单，我只是用我的想象力和一个标准的转换表想到了这样一个转换！ 但是，仍然存在一些问题。 有没有更短的方法？ 系数有多精确？ 转换总是可能的吗？ 可以自动化吗？ 不幸的是，这里的幼稚方法失败了。

第1部分。天真的决定

问题有一个直观的解决方案很高兴，但是实际上，这种简单性是解决问题的障碍。 没有什么比尝试以新的方式理解您已经了解的内容更困难的了-不仅因为您经常了解的东西少于您的想像。 为了说明这一点，假设您是来面试的，而您脑中就有这种直观的方法。 但是他不允许解决许多重要问题。

例如，如果没有转换怎么办？ 显而易见的方法没有说明什么，实际上是否有可能从一个单元转换为另一个单元。 如果他们给我1000的转化率，我将很难确定原则上是否可行。 如果要求我在不熟悉的（或发明的） 指针单元和戳戳单元之间进行转换，那么我不知道从哪里开始。 直观的方法在这里有什么帮助？

我必须承认，这是一种人为设计的方案，但还有一个更现实的方案。 您会看到我对问题的陈述仅包含距离单位。 这是有目的的。 如果我要求系统将英寸转换成千克怎么办？ 您和我都知道这是不可能的，因为它们测量的是不同类型，但是输入内容并未说明每个单元测量的“类型”。

在这里，认真地提出问题可以使有力的候选人证明自己。 在开发算法之前 ，他们会考虑系统的极端情况。 这样对问题的陈述有目的地使他们有机会问我我们是否将翻译不同的单元。 如果它在早期出现，这并不是一个大问题，但是当有人事先问我：“如果无法进行转换，程序应该返回什么？”时，这总是一个好兆头。 以这种方式提出问题，使我在编写至少一行代码之前就了解了候选人的能力。

图形视图

显然，幼稚的方法不适合，因此我们需要考虑如何进行这种转换？ 答案是将单位视为图形。 这是解决此问题所需的第一步理解。

特别是，假设每个单元都是图中的一个节点，并且如果A可以转换为B那么从节点A到节点B会有一条边：



边缘标有转换率，您必须乘以A才能得到B

我几乎总是希望候选人能提出这样的建议，很少给他以严肃的暗示。 我可以原谅那些没有注意到使用不交集的解决方案或对线性代数不太了解的候选人，以实现减少到重新提高邻接矩阵的幂的解决方案，但是图形可以在任何课程或编程课程中教授。 如果候选人没有适当的知识，则这是“不雇用”信号。

反正

图表示减少了经典图搜索问题的解决方案。 特别是这里有两种算法：宽搜索（BFS）和深搜索（DFS）。 在搜索宽度时，我们根据节点到原点的距离来检查它们：


较深的蓝调意味着后代

在深入搜索时，我们按照出现的顺序检查节点：



较深的蓝调也意味着后代。 请注意，我们实际上并未访问所有网站

任何一种算法都可以轻松确定是否存在从一个单位到另一个单位的转换，只需搜索图表就足够了。 我们从源单位开始搜索，直到找到目标单位。 如果您找不到目的地（就像尝试将英寸转换为公斤一样），我们知道没有办法。

但是，等等，缺少了一些东西。 我们不想寻找一种方法，我们想找到一个转化率！ 这是候选人必须跳槽的地方：事实证明，您可以修改任何搜索算法来计算转化率，只需在进行过程中简单地保存其他状态即可。 那是插图不再有意义的地方，所以让我们直接研究代码。

首先，您需要确定图的数据结构，因此我们使用以下方法：

 class RateGraph(object): def __init__(self, rates): 'Initialize the graph from an iterable of (start, end, rate) tuples.' self.graph = {} for orig, dest, rate in rates: self.add_conversion(orig, dest, rate) def add_conversion(self, orig, dest, rate): 'Insert a conversion into the graph.' if orig not in self.graph: self.graph[orig] = {} self.graph[orig][dest] = rate def get_neighbors(self, node): 'Returns an iterable of the nodes neighboring the given node.' if node not in self.graph: return None return self.graph[node].items() def get_nodes(self): 'Returns an iterable of all the nodes in the graph.' return self.graph.keys() 

然后让我们开始使用DFS。 有很多方法可以实现它，但是到目前为止，最常见的是递归解决方案。 让我们从这个开始：

 from collections import deque def __dfs_helper(rate_graph, node, end, rate_from_origin, visited): if node == end: return rate_from_origin visited.add(node) for unit, rate in rate_graph.get_neighbors(node): if unit not in visited: rate = __dfs_helper(rate_graph, unit, end, rate_from_origin * rate, visited) if rate is not None: return rate return None def dfs(rate_graph, node, end): return __dfs_helper(rate_graph, node, end, 1.0, set()) 

简而言之，该算法从一个节点开始，遍历其邻居并立即访问每个节点，从而对该函数进行递归调用。 堆栈上的每个函数调用都保存其自己的迭代状态，因此当返回一个递归访问时，其父级立即继续迭代。 通过在所有呼叫中维护一组已访问的站点，我们避免再次访问同一站点。 我们还通过在每个节点和源之间分配一个转换因子来计算系数。 因此，当遇到目标节点/块时，我们已经从源节点创建了转换系数，我们可以简单地将其返回。

这是一个很好的实现，但是它有两个主要缺陷。 首先，它是递归的。 如果事实证明所需的路径包含一千多个跳跃，则我们将以故障方式飞出。 当然，这不太可能，但是如果长期服务不能接受，那就是失败。 其次，即使我们成功完成了，答案也有一些不良的性质。

实际上，我已经在帖子的开头给出了提示。 您是否注意到Google如何显示1.0739e-17的转换率，但是我的手动计算得出的是1.0737e-17 ？ 事实证明，所有这些浮点乘法使人们已经考虑过扩展误差。 本文有太多细微差别，但最重要的是您需要最小化浮点乘法，以避免累积和引起问题的错误。

DFS是一种很棒的搜索算法。 如果存在解决方案，它将找到它。 但是他缺乏关键属性：他不一定找到最短的路径。 这对我们很重要，因为更短的路径意味着更少的跳跃和更少的归因于浮点乘法的错误。 为了解决这个问题，我们转向BFS。

第2部分。BFS解决方案

在此阶段，如果某个候选人成功实现了递归DFS解决方案并停止使用它，那么我通常在雇用该候选人方面至少给出一个较弱的建议。 他了解了问题，选择了适当的框架并实施了可行的解决方案。 这是一个幼稚的决定，所以我不坚持要雇用他，但是如果他能很好地应付其他面试，我不建议拒绝。

值得重复：如果有疑问，请写一个天真的解决方案！ 即使不是完全最优，板上代码的存在也已经是一项成就，并且常常可以在其基础上找到正确的解决方案。 我会说不同的话：永远不要白费力气。 您很可能想到了一个简单的解决方案，但不想提供它，因为您知道它不是最佳的。 如果您准备好立即提出最佳解决方案，那很好，但是如果没有，那么在继续进行更复杂的事情之前，请记录下所取得的进展。

从现在开始，让我们谈谈对算法的改进。 递归DFS解决方案的主要缺点是它是递归的，并且不能最小化乘法次数。 正如我们将很快看到的那样，BFS将乘法的数量减到最少，并且以递归方式实现它也非常困难。 不幸的是，我们将不得不放弃递归DFA解决方案，因为要对其进行改进，我们将需要完全重写代码。

事不宜迟，我提出一种基于BFS的迭代方法：

 from collections import deque def bfs(rate_graph, start, end): to_visit = deque() to_visit.appendleft( (start, 1.0) ) visited = set() while to_visit: node, rate_from_origin = to_visit.pop() if node == end: return rate_from_origin visited.add(node) for unit, rate in rate_graph.get_neighbors(node): if unit not in visited: to_visit.appendleft((unit, rate_from_origin * rate)) return None 

此实现与上一个实现在功能上有很大不同，但是如果仔细观察，它会做同样的事情，但有一个重大变化：递归DFS将另一条路由的状态保存在调用堆栈中，有效地实现了LIFO堆栈，但迭代解决方案将其存储在队列中先进先出

这意味着属性为“最短路径/最少次数”。 我们按节点出现的顺序访问它们，这样我们就可以得到节点的世代。 第一个节点插入其邻居，然后我们按顺序访问这些邻居，一直保持邻居不变，依此类推。 最短路径属性来自以下事实：节点按其与源的距离顺序访问。 因此，当我们遇到目的地时，我们知道没有任何早期的目的地会导致它。

至此，我们几乎完成了。 首先，您需要回答一些问题，然后他们不得不返回问题的原始表述。

首先，如果原始单位不存在，最琐碎的事情是做什么？ 也就是说，我们找不到具有给定名称的节点。 实际上，您需要对字符串进行一些归一化处理，以使Pound，Pound和lb指向相同的“ pound”节点（或其他一些规范表示形式），但这超出了我们的讨论范围。

其次，如果两个单元之间没有转换该怎么办？ 回想一下，在初始数据中，仅在单位之间进行转换，并且没有给出任何迹象表明是否有可能从一个特定单位获得另一个。 这归结为以下事实：转换和路径直接等效，因此，如果两个节点之间没有路径，则没有转换。 在实践中，最终会得到不相关的单位孤岛：一个代表距离，一个代表权重，一个代表货币，等等。

最后，如果您仔细观察上图，就会发现使用此解决方案无法在指针和光年之间进行转换。 节点之间的连接方向意味着没有从手到光年的方法。 但是，这很容易解决，因为转换可以逆转。 我们可以如下更改图形初始化代码：

 def add_conversion(self, orig, dest, rate): 'Insert a conversion into the graph. Note we insert its inverse also.' if orig not in self.graph: self.graph[orig] = {} self.graph[orig][dest] = rate if dest not in self.graph: self.graph[dest] = {} self.graph[dest][orig] = 1.0 / rate 

第3部分。评估

做完了！ 如果候选人已经达到了这一点，那么我很可能会推荐他去招聘。 如果您学习计算机科学或学习过算法课程，您可能会问：“这真的足以与这个人进行面试吗？”，我将回答：“基本上是。”

在您决定这个问题太简单之前，让我们看一下候选人必须做些什么才能达到这一点：

• 了解问题
  
• 以图的形式建立一个转换网络
  
• 可以将系数与图表的边缘进行比较
  
• 查看使用搜索算法实现此目标的可能性。
  
• 选择您喜欢的算法并将其更改以跟踪赔率
  
• 如果他将DFS实施为幼稚的解决方案，请认识到他的弱点。
  
• 实施BFS
  
• 要退后一步，研究极端情况：
  
  • 如果询问我们不存在的节点怎么办？
    
  • 如果转换因子不存在怎么办？
• 认识到逆变换是可能的并且可能是必要的

这个问题比以前的问题容易，但也很困难。 与以前的所有问题一样，候选人必须在思维上从抽象提出的问题飞跃到为解决方案开辟道路的算法或数据结构。 唯一的问题是最终算法比其他问题先进。 除此算法材料之外，还适用相同的要求，尤其是在极端情况和正确性方面。

“但是等等！”您可能会问。 -Google不会沉迷于运行时的复杂性吗？ 您甚至没有问这个问题的时间或空间复杂性。 哦，好！” 您可能还会问：“等等，您给了评级“强烈推荐租用”？ 如何获得？” 都很好的问题。 这使我们进入了最后的额外奖金回合...

第4部分。有可能做得更好吗？

在这一点上，我谨向候选人表示祝贺，并明确表示，进一步的一切都只是一笔奖金。 当压力消失时，我们可以开始创造。

那么运行BFS的困难是什么？ 在最坏的情况下，我们必须考虑每个单独的节点和边，从而得出线性复杂度O(N+E) 。 这是在O(N+E)图构造相同的复杂性之上。 对于搜索引擎而言，这可能很好：对于大多数合理的应用程序而言，一千个度量单位就足够了，并且对每个查询进行内存搜索不会造成过载。

但是，可以做得更好。 为了激发动力，请考虑如何将此代码插入搜索字符串。 一些非标准单位的转换更为常见，因此我们将一再计算它们。 每次执行搜索时，都会计算中间值，依此类推。

通常建议仅缓存计算结果。 每当计算单位转换时，我们总是可以在两个转换之间添加一条边。 作为奖励，我们免费获得逆变换！ 完成了吗

确实，这将为我们提供渐近恒定的搜索时间，但将花费存储额外边的时间。 这实际上变得相当昂贵：随着时间的流逝，我们将努力建立完整的图形，因为所有对转换都是逐渐计算和存储的。 图中可能的边数是节点数的平方的一半，因此对于一千个节点，我们需要一百万个边。 对于一万个节点，大约五千万个，等等。

对于一百万个节点的图，我们超出了搜索引擎的范围，力争达到五万亿个边缘。 这个数量根本就不合理地存储，而且我们花时间在图表中插入边。 我们必须做得更好。

幸运的是，有一种方法可以实现恒定时间来搜索系数，而无需二次空间增长。 实际上，几乎所有我们需要的东西都在我们的鼻子底下。

第4部分。固定时间

因此，总缓存实际上接近最佳解决方案。 在这种方法中，我们（最终）获得了所有节点之间的边缘，也就是说，我们的变换被简化为找到一个边缘。 但是，是否真的需要存储从每个节点到每个节点的转换？ 如果我们仅将转换因子从一个节点保存到所有其他节点该怎么办？

再看一下BFS解决方案：

 from collections import deque def bfs(rate_graph, start, end): to_visit = deque() to_visit.appendleft( (start, 1.0) ) visited = set() while to_visit: node, rate_from_origin = to_visit.pop() if node == end: return rate_from_origin visited.add(node) for unit, rate in rate_graph.get_neighbors(node): if unit not in visited: to_visit.appendleft((unit, rate_from_origin * rate)) return None 

让我们看看这里发生了什么：我们从源节点开始，对于遇到的每个节点，我们计算从源节点到该节点的转换系数。 然后，一到达目的地，就返回起点和终点之间的系数，并丢弃中间系数。

这些中间比率是关键。 但是，如果我们不把它们扔掉怎么办？ 如果我们改写下来怎么办？ 所有最复杂，最不可理解的搜索都变得很简单：查找A与B的比率，首先找到X与B的比率，然后将其除以X与A的比率，就可以了！ 在视觉上，它看起来像这样：


请注意，任何两个节点之间的边缘不超过两个

事实证明，要计算此表，我们几乎不需要更改BFS解决方案：

 from collections import deque def make_conversions(graph): def conversions_bfs(rate_graph, start, conversions): to_visit = deque() to_visit.appendleft( (start, 1.0) ) while to_visit: node, rate_from_origin = to_visit.pop() conversions[node] = (start, rate_from_origin) for unit, rate in rate_graph.get_neighbors(node): if unit not in conversions: to_visit.append((unit, rate_from_origin * rate)) return conversions conversions = {} for node in graph.get_nodes(): if node not in conversions: conversions_bfs(graph, node, conversions) return conversions 

转换的结构由单位A的字典表示为两个值：单位A关联组​​件的根和根单位与单位A之间的转换系数。由于每次访问时都将一个单位插入此字典，因此我们可以将此字典的键空间用作一组访问，而不是使用专门的访问。 请注意，我们没有最终节点，而是迭代节点，直到完成。

在此BFS之外，还有一个帮助程序功能，可在图形中的节点上进行迭代。 每当遇到翻译词典之外的节点时，它都会从该节点开始启动BFS。因此，我们保证将所有节点折叠到其相关组件中。

当您需要查找单元之间的关系时，我们只需使用刚刚计算出的转换结构：

 def convert(conversions, start, end): 'Given a conversion structure, performs a constant-time conversion' try: start_root, start_rate = conversions[start] end_root, end_rate = conversions[end] except KeyError: return None if start_root != end_root: return None return end_rate / start_rate 

在访问转换结构时，通过侦听异常来处理“没有这样的单元”的情况。通过比较两个量的根来处理“没有这样的变换”的情况：如果它们具有不同的根，则可以通过两个不同的BFS调用来检测它们，也就是说，它们位于两个不同的连接组件中，因此它们之间没有办法。最后，我们执行转换。

你去！当前的解决方案具有预处理的复杂性O(V+E)（不比以前的解决方案更糟糕），但她还可以进行恒定时间的搜索。从理论上讲，我们将空间需求加倍，但是在大多数情况下，我们不再需要原始图，因此我们可以删除它并仅使用该图。而且，空间复杂度实际上比原始图形要少：O(V+E)之所以需要空间复杂性，是因为它需要存储所有的边和顶点，而这种结构仅O(V)因为我们不再需要边而需要。

结果

如果到目前为止，您可能还记得，其中一个问题最初是检查一个更简单的问题在选择有价值的候选人时是否仍然有用，以及是否可以更好地展示自己的能力。我想给出一些明确的科学答案，但是我只有一些个人经验的故事。但是，我注意到了一些积极的结果。

如果我们将这个问题的解决方法分为四个障碍（讨论框架，选择算法，实现，讨论执行固定时间），那么到面试结束时，几乎所有候选人都达到了“算法选择”。正如我所怀疑的那样，对框架的讨论是一个很好的过滤器：尽管有明显提示，候选人要么立即显示图表，要么无法以任何方式出现。

这是一个有用的信号。我可以理解，当一个人不了解高级或晦涩的数据结构时，因为老实说，您很少需要实现脱节集。但是图形是基本的数据结构，几乎是该主题的所有入门课程的一部分。如果应聘者难以理解它们或无法轻松应用它们，那么他可能很难在Google上成功（至少在我那时，我不知道今天如何）。

另一方面，算法的选择并不是特别有用的信号源。经历了成帧阶段的人们通常可以毫无问题地使用该算法。我怀疑这是由于以下事实：搜索算法几乎总是与图本身一起被教授，因此，如果有人熟悉其中一个，那么他们就会知道另一个。

实现起来并不容易。许多人对DFS的递归实现没有任何问题，但是，正如我上面提到的，该实现不适用于生产。令我惊讶的是，人们对BFS和DFS的迭代实现似乎并不十分熟悉，即使经过明显的暗示，它们也经常浮出水面。

我认为，完成实施阶段的任何人都已经为我赢得了“聘用”建议，而对持续交付时间的讨论简直是加分。尽管我们在文章中详细介绍了该解决方案，但实际上，进行口头讨论而不是编写代码通常会更有效率。很少有候选人可以立即做出决定。我经常不得不提供实质性的线索，即使那样，很多人也找不到他。这是正常现象：正如预期的那样，很难获得高度推荐的评级。

但是，等等，还不止这些！

基本上，我们研究了整个问题，但是，如果您有兴趣进一步研究它，那么我将不涉及许多扩展。我将以下练习留给读者：

首先，热身：在我布置的固定时间内的解决方案中，我任意选择了每个连接组件的根节点。特别是，我使用了遇到的第一个组件节点。这不是最佳的，因为对于所有已知值，我们选择了一个节点，尽管某些其他节点可能更靠近中心，而通向所有其他节点的路径较短。您的任务是用最小化所需乘法次数并最小化浮点误差散布的选择来替换此任意选择。

其次，在所有参数中，都假设最初通过图的所有相等路径都是相等的，但情况并非总是如此。解决此问题的一个有趣的选择是货币转换：节点是货币，从A到B的边（反之亦然）是每种货币对的供求价格。我们可以用货币套利来重新解释单位转换的问题：实施一种算法，在给定货币转换图的情况下，计算出一个遍历该图的周期，该周期将为交易者提供比初始金额更多的资金。不包括任何交易费用。

最后，这是一个真正的宝石：有些单位表示为不同基本单位的组合。例如，在SI系统中，瓦数定义为kg•m²/s³。最后的任务是扩展该系统以支持这些单位之间的转换，仅考虑基本SI单位的定义。

如果您有任何疑问，请随时通过reddit与我联系。

结论

当我开始在面试中问这个任务时，我希望它会比以前的任务容易一些。实验在很大程度上是成功的：如果应聘者立即看到解决方案，那么他通常会很快地完成任务，因此我们有很多时间来讨论固定时间的高级解决方案。通常，遇到困难的人绊倒在算法上没有概念上的飞跃：候选人无法以适当的方式完全解决问题或草拟好的解决方案，但无法将其转化为有效的代码。无论他们何时何地遇到困难，我都可以从候选人的长处和短处获得有意义的信息。

希望本文对您有所帮助。我知道算法可能没有以前的文章那么多冒险。在开发人员的访谈中，习惯上大量讨论算法。但是事实是，即使使用一种简单的众所周知的方法，也会出现很大的困难。所有代码都在本系列文章的资源库中。