谷歌面试题解析：单位换算

这是“谷歌面试题解析”系列的又一篇文章。在这些面试题被泄露之前，我曾在谷歌的面试中使用过它们。离开谷歌后，我成了 Reddit 的工程经理，但我仍然想把这些面试题分享出来。之前已经分享了动态规划、矩阵求幂和查询同义词，这一次，我想要深入探究一个全新的问题。

免责声明：虽然面试候选人是我的工作职责之一，但这篇文章仅代表我的个人观察、个人经历和个人观点。如果有任何错误，请不要将它们归咎于谷歌、Alphabet、Reddit 或任何其他个人或组织。

寻找新的面试题

在上一篇文章中，我介绍了我最喜欢的一个面试题。在它被泄露之前，我用了它很长一段时间。如果只是从理论的角度来看，之前的面试题很好，但这次我想找一个与谷歌具有更多相关性的问题。在它被泄露之后，我终于可以找一个替代品了，这次我想要简单一点的。

谷歌面试题一般都很难，所以看到这句话是不是感到有点惊讶？但当时我想要找一个简单的面试题是有理由的。首先，尽管我给出了很多提示，并进行了简化，很多候选人仍然表现不尽如人意，我也不知道是为什么。其次，面试应该把候选人分为“值得聘用的人”和“不值得聘用的人”，我想知道一个稍微简单一点的面试题是否还能起到这样的作用。

好的面试题能够让你全面了解候选人的优点和缺点。一句简单的“候选人很出色”并不能帮助招聘者决定候选人是否具备他们想要的特质。同样，当候选人在某些方面表现很好但在某些方面表现不佳时，简单地说他们“逊毕了”对招聘者来说也没有太大帮助。我发现，难一点的面试题会让候选人陷入到这两种情况中的一种。

将候选人分为“值得聘用的人”和“不值得聘用的人”并不意味着就是要在“面试过程中区分出愚蠢的求职者和聪明的求职者”。我记得几乎所有候选人都很聪明，有才华，有上进心。通过电话面试来筛选候选人固然是好，但如果在这个阶段被拒，并不能说明候选人能力不行。

不过，我见得比较多的是候选人没有为面试做好充分的准备，或者解题速度太慢，或者在解题时需要太多的督促，或者沟通不顺畅，或者没能把自己的想法变成代码，或者他们的态度无法帮助他们取得长远的成功，等等。什么才是“值得聘用的人”？这个定义很模糊，而且因公司而异，面试过程就是为了考察候选人是否符合公司的定义。

有人在 Reddit 上抱怨谷歌面试题太难。我很好奇如果我用简单一点的面试题，是否还能区分出“值得聘用的人”或者”不值得聘用的人”。

在选择新的面试题时，所有这些都是我关心的。我会用一个简单到可以 45 分钟内解决的问题，但同时又难到可以让候选人展示他们更强的技能。如果它又能够与谷歌的产品有某种关联，那就更好了。

最终，我找到了这个面试题。这个面试题来自一位出色的谷歌员工。不过，我已经联系了还在谷歌工作的熟人，确认它已经被停用，所以你不要指望会在谷歌的面试中看到它。接下来，我会以一种我认为有效的方式来呈现这道题目，如果有任何不妥，希望原作者能够原谅。

问题描述

我们来聊聊测距问题。我们用“手”来表示一个距离单位，也就是 4 英寸，在英语国家常用来测量马的高度。“光年”是另一个距离单位，也就是一个粒子在一定秒数内移动的距离，大约等于一个地球年。从表面上看，这两个单位除了用来测量距离之外，几乎没有什么关系，但事实证明，谷歌可以随意在它们之间进行转换：

它们毕竟都是用来测量距离的，所以互相转换也是很自然的事情。但如果你细想就会觉得有点奇怪：它们之间的转换比率是如何算出来的？肯定没有人算过一光年等于多少手吧？

其实你并不需要直接计算，你可以使用常用的转换比率：

• 一手等于 4 英寸；

• 4 英寸等于 0.33333 英尺；

• 0.33333 英尺等于 6.3125e-5 英里；

• 6.3125e-5 英里等于 1.0737e-17 光年。

这个问题的目的是设计一个系统，让系统为我们执行这些转换。更准确地说就是：

给定一系列转换比率，也就是源单位、目标单位和乘数，例如：

英尺 英寸 12

英尺 码 0.3333333

……

也就是 ORIGIN * MULTIPLIER = DESTINATION，然后设计一个算法，接收两个任意的单位，返回它们之间的转换比率。

讨论

我很喜欢这个面试题，因为它很直观：从一个比率转换到另一个比率，再转换到另一个，直到找到目标为止！这个题目满足了我对“简单”的需求，因为候选人在解答其他题目时往往需要长时间的思考，然后才能给出一个基本的答案。

不过，我也见过很多候选人，他们在没有明显提示的情况下无法将这种直觉转化为可行的解决方案。这个面试题的优点之一是它同时考察了候选人分析问题和编写代码的能力。

第零步：直觉

在深入探究答案之前，先让我们来研究一下“显而易见”的解决方案。大多数转换都是简单而直接的。大多人都知道，世界上有很多国家使用神秘的单位——“公里”来测量距离。从一个单位转到到另一个单位，就像将英里数乘以约 1.6 那么简单。

问题在于路径的深度有多深。对于大多数单位，我们已经有了预先计算好的转换比率，我们要做的就是将它找出来。但是，对于那些没有直接给出转换比率的单位（比如从手到光年），就需要找到一条转换路径了（重复一下之前的路径）：

• 一手等于 4 英寸；

• 4 英寸等于 0.33333 英尺；

• 0.33333 英尺等于 6.3125e-5 英里；

• 6.3125e-5 英里等于 1.0737e-17 光年。

这一点都不难，顺着路径找到目标比率就可以了。但问题是，有没有更短的转换路径？找到的比率精确吗？正确的转换比率一定存在吗？能实现自动化吗？对于这些问题，这种直观的方法就失效了。

第一步：直观的解决方案

虽然这个问题有一个直观的解决方案，但可接近性实际上是解决这个问题的一个障碍。没有什么比学习你已经知道的东西更难的了，因为你以为对它很了解，但实际上可能不是。有很多重要的问题是直观方法无法解决的。

例如，如果不存在正确的转换比率，那该怎么办？直观的方法并不能告诉你是否存在正确的转换比率，如果给我 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。实现 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())

这个算法从一个节点开始遍历它的邻居，并通过递归函数调用访问每个邻居。栈中的每个函数调用都保存了自身的迭代状态，当一个递归返回时，父函数立即继续迭代。我们通过维护一个已访问节点的集合来避免访问同一个节点多次。我们还为每个节点分配了它与原点之间的转化比率。当我们遇到目标节点/单位时，就得到了想要的转换比率，然后将它返回。

这是一个很好的实现，但它有两个缺点。首先，它是递归的。如果目标路径超过一千跳，程序很可能会崩溃。确切地说不太可能会，但如果你有一个长时间运行的服务，你最不希望发生的事情就是崩溃。其次，即使我们成功地避免了这个问题，我们得出的答案也有一些不完美的地方。

还记得文章开头的截图吗？谷歌给出的转换比率是 1.0739e-17，而我手动计算得出的是 1.0737e-17。因为在这个过程中进行了多次浮点数乘法，所以我们还要考虑到误差扩散问题。我们要尽可能少进行浮点数乘法，避免错误累积。

DFS 是一种很好的搜索算法，如果存在解，它一定会把它找出来，但它缺少一个关键的属性：它不一定能找到最短路径。这跟我们很有关系，因为较短的路径意味着较少的跳数，较少的跳数意味着更少的浮点数乘法。为了解决这个问题，我们需要使用 BFS。

第二步：广度优先搜索

到了这个时候，如果一个候选人能够实现递归 DFS 解决方案，并且就此打住，我至少会给出聘用候选人的建议。他们理解了问题，选择了一个合适的数据结构，并实现了一个有效的解决方案。但这只是一种直观的解决方案，所以我并不急于让他通过。

接下来我们要讨论的是如何做出改进。递归 DFS 解决方案的主要缺点是它是递归的，而且不能最小化浮点数乘法的次数。我们很快就会看到，BFS 可以最小化乘法的次数。

这是基于 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 将下一个要访问的状态保存在后进先出的栈中，而 BFS 将状态保存在先进先出的队列中。

这就是实现“最短路径/最少乘法次数”的关键之处。我们按照遇到节点的顺序来访问节点，将第一个节点的邻居塞入队列，然后依次访问这些邻居，同时把它们的邻居也塞进队列，依次类推。我们是按照节点到原点的距离来访问节点的，所以当遇到目标节点时，我们就知道没有比这个更短的路径了。

现在还有几个问题，它们都与最初的问题陈述有关。

首先，如果输入的单位不存在，那该怎么办？很简单，如果找不到具有给定名称的节点，那就不存在转换比率。

第二，如果两个单位之间不存在正确的转换比率，那该怎么办？回想一下，我们的输入只给出了单位之间的转换比率，并没有给出两个单位之间是否可以进行转换的信息。BFS 解决了这个问题：转换和路径是等价的，所以如果不存在从一个节点到另一个节点的路径，那就不存在合法的转换。

最后，如果你仔细观察第一步中的那张图，你会发现，这个解决方案无法完成从手到光年的转换：因为图中不存在从手到光年的有向路径。不过，这个问题很容易解决，我们可以通过取转换比率的倒数来进行逆向转换。我们可以修改图的初始化代码：

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

第三步：计算

如果一个候选人可以走到这一步，我会考虑让他通过面试。你可能会问：“这样就能通过面试吗”？我的回答是:“是的，差不多就是这样”。

你可能认为这个问题很简单，但你要知道，一个候选人要走到这一步需要做些什么：

• 理解问题；

• 想出图数据结构；

• 将单位转换映射成图的路径；

• 知道可以使用图搜索算法来找到路径；

• 选择他们最喜欢的算法，并修改算法以便获得转换比率；

• 如果他们采用了 DFS 解决方案，也要知道它的缺点；

• 实现 BFS；

• 后退一步，检查边缘情况：

• 如果一个节点不存在该怎么办？

• 如果转换比率不存在呢？

• 需要考虑实现反向转换。

这个问题比我问过的其他问题要简单，但其实也不简单。和之前的问题一样，它要求候选人能够从抽象的问题跳跃到算法或数据结构上，从而获得解题的办法。除了算法之外，他们也需要考虑很多东西，比如边界情况和正确性。

你可能会问：“难道谷歌不注重运行时复杂度吗？你还没问我这个问题的时间和空间复杂度呢？”

第四步：你能做得更好吗？

那么，BFS 解决方案的运行时复杂度是多少？在最坏的情况下，复杂度为 O(N+E)，所以实际上是线性的。对于搜索引擎来说，这可能没什么问题：对于大多数应用程序来说，1000 个单位顶多了，在内存中执行这样的搜索并不是很重的负担。

但我们可以做得更好。如果将这段代码放在搜索引擎里会怎样？一些不常见的单位转换并不见得比其他的少，所以我们会一遍又一遍地重复计算它们，每次都要执行搜索、计算中间值等步骤。

常见的方法是缓存计算结果。在计算单位转换时，我们可以在两次转换之间添加一条边，这样还可以得到逆向转换结果。

实际上，我们可以获得常量的查找时间，代价是需要保存额外的边。这样的成本有点高：图的边数将以节点数平方一半的速度增长，所以如果有 1000 个节点，需要 50 万条边，如果有 1 万个节点，需要大约 5000 万条边。

一个包含一百万个节点的图将趋向于五万亿条边。这样的存储量是不合理的，而且往图中插入边也需要耗费时间。我们必须做得更好。

所幸的是，有一种方法可以在不增加二次空间的情况下实现常量时间查找。事实上，它所需要的大部分东西已经在我们的眼皮底下了。

第五步：常量时间

“缓存”解决方案实际上已经离我们的目标不远了。我们得到了每个节点和其他节点之间的边，但我们真的需要保存从每个节点到其他节点的转换比率吗？如果我们只保存从一个节点到另一个节点的转换比率呢？

让我们再来看一看 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

我们使用字典来表示转换结构。因为我们会在访问每个节点时向字典中插入一个单位，所以可以直接使用字典的键来判断已访问过的节点。

除此之外，我们还需要一个辅助函数，用于遍历图中的节点。每当遇到不存在字典中的节点时，都会从该节点开始进行 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

就这样，我们得到了另一个解决方案，它需要 O(V+E)的预处理时间（并不比之前的解决方案差），同时还支持常量时间查找。理论上，我们需要双倍空间，但大多数时候我们不再需要原始图，所以可以将其删除，只需要使用这个字典就可以了。也就是说，空间复杂度实际上比原始图要小：图需要 O(V+E)，因为它需要保存所有的边和节点，而这个结构只需要 O(V)，因为我们不再需要保存边了。

结论

我希望这个问题比之前问过的问题简单一些。我发现我的实验是成功的：那些在这方面做得好的候选人通常很快就拿到高分，这样就有足够的时间来讨论常量时间解决方案。做得不好的候选人无法想出正确的数据结构，或者即使他们想出了一个好的解决方案，也无法将其转化为可运行的代码。

不管怎样，我希望这篇文章对你有用。它可能不像之前的算法那么难，但对于偏重算法的软件开发者面试来说，即使是一个简单的方法，也包含了很多复杂性。如果你想参看更多代码，请访问GitHub。

原文链接

Google Interview Problems: Ratio Finder

延展阅读

一道泄露并遭禁用的谷歌面试题，背后玄机全解析

刷道谷歌泄漏的面试题：面试官想从中考察你什么？