原文: https://www.freecodecamp.org/news/collaborative-problem-solving-with-python/

无论你是一个多么有经验的开发者,为一份新工作参加面试总是很有压力。从我自己的经验来看,确实是这样。

我从事专业软件开发工作已经两年半了,经历过五次开发者面试。

我看到人们过多地关注学习具体的算法问题,或者在专门提供面试挑战的在线平台上进行培训。但是,面试还有另一面,我认为它同样重要——而人们对它的关注度较低。

因此,如果你想知道我认为你应该如何关注你的面试训练,请冲一杯咖啡,舒服地坐下来。不要担心,我会通过 Python 示例来帮助你理解。

是我们要讨论的内容:

  1. 算法和数据结构对面试重要吗
  2. 专注于协作方式
  3. 尝试做模拟面试
    – 第一个面试问题示例
    – 第二个面试问题示例
    – 最难的面试问题示例
  4. 总结

让我们深入了解一下。

算法和数据结构对面试重要吗

简短的回答是重要

了解数据结构和算法往往能帮助你找到工作。此外,拥有扎实的算法背景的一个好处是在面对挑战性问题时能够做出更好的决定。

在现实生活中,算法问题不会像你可能研究的学术练习中的语句那样。不过,你经历的训练越多,你就越有可能识别出平衡二叉树或最短路径算法的应用。

考虑到这一点,我建议不要仅仅为了你想擅长的面试而训练数据结构和算法。即使仅仅为了学习的乐趣,算法的设计和如何使用正确的数据结构也是非常有意思的话题。

面试的范围是非常有限的。要把重点放在解决问题的部分。试着了解如何使用一种算法(或其变体)来完成类似的任务。研究所有的变体,并学会在不同情况下识别它们,这将有助于你以开放的心态面对新任务。

另外,不要背诵解决方案。它不会给你带来任何提升。如果你只针对非常具体的主题进行训练,有经验的开发人员很容易提出正确的问题,让你“大显身手”。

针对一个问题,尝试用不同的方法来解决它。每次都尝试解决更难的问题。走出你的舒适区。

这将会给你回报。

专注于协作方式

很多人在 Leetcode 等网站上进行面试训练。这并没有什么问题。这些网站对训练你解决问题的能力很有帮助。

我至少在过去八年里一直在参加竞争性编程竞赛。我一直从这些在线资源中受益。

但是,对于大多数想要在面试中表现出色的软件工程师来说,有一件事很难理解。他们没有对软件开发中最重要的方面进行训练:协作

通常情况下,当你在一个在线平台上处理问题时,它对一些输入的最大值有一些限制。它也可能有一些时间和内存的限制,要求你调整你的解决方案,以提高或降低效率。但这不是现实生活中的情况。

将这些约束条件映射到现实生活中的场景并不明显。它们通常是以来自客户的非常具体的要求或团队的非常具体的特征的形式出现。

在一个真实的项目中,团队将合作决定这些约束条件是什么。你必须分析你的用例、你有多少时间来完成任务、谁是最终的用户、有多少人将从事这项工作,等等......

经过一系列的讨论,你们会达成共识,最后开始实施适合你们的解决方案。而这个解决方案在某些情况下甚至不一定是更有效的,但可能是实施速度最快的。

这也是面试官在面试时希望从候选人那里看到的。

你不要直接跳到实施你所知道的针对你所面临的问题的最佳解决方案。相反,你应该把面试官当作一种有价值的资源,把他们当作你的队友(最终,你希望他们是)。问一些关于团队更倾向于如何实施该问题的解决方案的问题。

这将引发非常富有成效的讨论,你可以展示你的编码能力和你的协作技能。你可以先提出简单的解决方案,并带领你的面试官了解如何使用你的锦囊妙计来改进解决方案。

对于在线训练,我再说最后一点。我建议做个人和团队培训。使用诸如 CodeforcesAtCoder 这样的网站,这些网站有大量有趣(和具有挑战性)的问题,并尝试每天与自己比赛。

不要专注于你的评级。我以前也这么做过,这只会让你退步。

尝试做模拟面试

如果你读到了这里,我想提出一个小小的练习。让我们进行一次模拟面试,我将扮演面试官的角色。我会告诉你我认为候选人(你)应该如何回答每一个问题和执行每一项任务。

当然,我们将只关注编程挑战部分。面试的其他方面,如谈论以前的经验,也很重要,但我们将尝试在另一篇文章中介绍。

所以,如果你觉得准备得足够充分了,就开始吧!

第一个面试问题示例

让我们从你要解决的任务开始。请记住,如果你和我真的有机会面试,我不会使用这个相同的例子,不过我当然将使用相同的方法 😉。

这个问题的陈述如下:

“给出一个整数 X,确定它是否是一个质数。”

你可能很想去找你知道的最好的解决方案来解决这个问题。我认为这种方法,正如我之前解释的,并不总是正确的。

相反,我想知道的是解决这个问题的不同方法。另外,我希望你能问一下这个任务的要求。比如说:

  • 我们应该以性能为目标,还是以更快的速度来解决它?
  • 我们应该采取一个对其他开发者来说容易理解的解决方案吗?

通常,在为一个问题创建第一个解决方案时要考虑的是:

  • 简单或困难:我们应该制定一个容易实施的解决方案,即使它并不完美,还是应该选择一个更强大但却难以实施的解决方案?
  • 马虎与高效:我们应该先提供一个可行的、马虎的解决方案,然后再提供一个更有效的解决方案,还是应该直接选取高效的解决方案?

评估你的团队想要优化什么。达成一个共识,并实施商定的解决方案。

就我而言,如果你提出你能想到的最简单的、最快的、正确的解决方案,然后引导我改进这个方案,我会很高兴。

对于这个问题,一个非常好的初步解决方案的例子是像下面这样的:

# naive.py

def is_prime(x: int) -> bool:
    if x in [0, 1]:
        return False
    for i in range(2, x):
        if x % i == 0:
            return False
    return True

正如你所看到的,这个函数是正确的。由于质数是一个只能被数字 1 和它本身整除的整数,所以从 2x-1 迭代寻找 x 的除数是有意义的,如果我们找到一个,我们可以立即返回 False。否则,我们返回 True。作为边缘案例,数字 01 根据定义不是质数。

这是一个很好的出发点!

现在,在深入优化这个方法之前,你可以讨论一下代码的风格。它够 Pythonic 吗?我们关心它吗?它可读吗?

所有这些问题一开始可能并不重要,但是,由于我们作为一个团队工作,它们确实很重要。有一个编码风格是很重要的,因为它使每个团队成员更容易理解对方的代码,而且会加快审核和重构的速度。另外,代码更多的是被阅读而不是被书写,所以可读性也很重要!

你可能很想炫耀一下你的 Python 技能,把前面的函数改写成如下:

# pythonic_naive.py

def is_prime(x: int) -> bool:
    return False if x in {0, 1} else all(x % i != 0 for i in range(2, x))

我认为这是一个很好的、符合 Pythonic 的方法来写这个函数。但是,由于团队是最重要的,所以这种修改有待商榷。

可能有些团队成员对 Python 不是那么熟练。也许,在这种情况下,我们应该对可读性进行优化,保留我们最初写的那个函数。

在讨论性能之前,一个更有趣的补充是为该函数添加文档字符串(docstring)。正如我之前所说,这段代码很可能在将来被你的团队成员阅读。那么,重要的是,让他们(和你未来的自己)更容易理解这个函数在做什么。

也许把这个函数改成下面这样会更好:

# naive.py

def is_prime(x: int) -> bool:
    """这个函数以一个整数 `x` 为参数,检查它是否是质数。

    Args:
        x (int): 判断是否为质数的整数。

    Returns:
        bool: 如果数字 `x` 是质数,返回 True,否则返回 False。
    """
    if x in [0, 1]:
        return False
    for i in range(2, x):
        if x % i == 0:
            return False
    return True

第一次优化

到此为止,我们有了一个初步的解决方案,它是可行的。我们已经讨论了一些重要的话题,如代码的样式、可读性和开发人员的文档。这些都是作为一个团队工作时需要考虑的重要事情。

但是我们仍然没有谈及解决方案的性能问题。所以,现在可能是时候了。

在这个时候,你也许应该提出,这个函数可以被改进,这样它的运行速度就会更快。现在是你展示你的所有算法知识的时候了。

之前的解决方案的时间复杂度为 O(x),其中 x 是函数作为参数的输入整数。这可以通过以下代码优化为 O(sqrt(x))

# sqrt.py

import math

def is_prime(x: int) -> bool:
    if x in [0, 1]:
        return False
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

或者甚至像这样,不导入 math 库:

# sqrt.py

def is_prime(x: int) -> bool:
    if x in [0, 1]:
        return False
    i = 2
    while i**2 <= x:
        if x % i == 0:
            return False
        i += 1
    return True

两种方法对我来说都是可以的。

我在之前的实现中省略了文档字符串,是为了让实际的代码变化更加清晰。但是,如果能将函数的时间复杂度包含在文档中,对开发者来说是非常好的。你能提供的关于你的代码的信息越多,对你的团队成员和你自己来说就越好。

到目前为止,你做得很好。让我们继续吧!

第二个面试问题示例

到目前为止,我已经能够评估出你具有必要的协作能力,能够与团队一起承担简单的任务。现在,是时候让事情变得复杂一点了。

这是我要提出的第二个问题的陈述:

“给出两个整数 LR,计算在区间 [L, R] 内有多少个质数。”

再说一遍,我建议讨论一下团队关于这项任务的优先级是什么。从简单的开始,逐步讨论改进初始解决方案。强调过早的优化并不是一个好的实践。

同时,讨论使用你为前一个任务实施的解决方案来解决这个任务的可能性。如果我们有一个函数可以告诉我们一个整数是否是质数,我们就可以把它用于一个范围内的每个数字。

而这是你在现实生活中必须要做的事情。通常情况下,当一个新的任务出现时,团队应该研究一下所维护的项目,看看哪些东西可以被重用,以加快实施过程的速度。如果你不这样做,你可能最终要编码重复的功能。

因此,这个任务的一个好的初步解决方案可以是这样的:

# range_primes.py

from sqrt import is_prime

def count_primes(l: int, r: int) -> int:
    primes = 0
    for i in range(l, r + 1):
        if is_prime(i):
            primes += 1
    return primes

这完全没问题,你已经表明你可以重用以前的功能来构建新的功能。就像第一个例子一样,你可能很想炫耀你的 Python 技能,把这个函数写成这样:

# range_primes.py

from sqrt import is_prime

def count_primes(l: int, r: int) -> int:
    return sum(bool(is_prime(i)) for i in range(l, r + 1))

我建议不要把这个 Pythonic 实现作为你的第一选择。留待讨论,评估代码的可读性,也许还可以分析一下性能的差异。不要忘了 docstrings!

下一节是事情变得有趣的时候。继续阅读。我们正在进行最后一步......

最难的面试问题示例

还记得我之前说过,竞争性编程网站中的约束条件很难映射到现实生活中的需求吗?

下面我将为你提出一个困难的挑战,让你确定这些约束条件,并实现你能做到的最佳解决方案:

“假设一个客户希望我们把计算一个范围内的质数的功能作为一项服务来提供。他们希望把重点放在性能上,因为他们计划经常使用这项服务。你将如何实现它?”

如果你一直在为面试练习你的算法技能,你可能已经解决了几次与此类似的问题。这里的主要区别是背景的变化。

我没有给你精确的指令、数字约束和输入或输出格式,而是给你一个更宽泛的任务描述。我在这里的目标和以前一样:让你和我互动,就好像我们是队友,从我们知道的一点信息中找出如何解决这个问题。

希望在交流了一些问题和答案之后,我们可以把之前的、比较模糊的说法翻译成更熟悉的东西:

“给出一组形式为 [L, R] 的查询,对于每个查询,回答该范围内有多少个整数是质数。”

这是有道理的,因为正如描述中所说,客户希望非常频繁地使用这项服务。

我们想把重点放在性能上。这应该是我们在实施解决方案时的主要关注点。但是,要达到一个最佳的解决方案,最好的办法还是从一个简单的解决方案开始,分析是否满足我们的性能要求,并不断地逐步改进。让我们来看看整个例子。

我们可以先用上一步实现的解决方案。它够好吗?

让我们假设,作为函数参数的最大数字范围是 [1, 10^6]。另外,现实中,让我们假设服务每分钟要回答的查询数量大约为 10^5

我们之前的解决方案的时间复杂度为 O(sqrt(n)),以确定一个数字是否是质数。如果我们对范围内的每个数字都这样做,复杂度就会上升到 O(n * sqrt(n))。除此之外,如果我们对每个查询都这样做,我们最终会得到更高的时间复杂度 O(q * n * sqrt(n))

把前面的变量替换为它们可能具有的最高值,你会得到这个解决方案将需要大约 10^14 次操作来回答所有的查询。假设一台计算机每秒可以进行大约 10^8 次基本操作,那么完成所有操作大约需要 10^6 秒。

注:将 10^6 秒转换为天,你会感到惊讶的 🤯。

如果目标是优先考虑我们的解决方案的性能,这个解决方案是不可行的。让我们看看如何改进它。

在这一点上,我所期望的是你利用自己通过所有在线平台的训练获得的最好经验,向我展示一个令人印象深刻的解决方案。这是展示你所有分析和算法技能的时候。

但只是现在,因为我知道你是一个团队型开发者。

最终解决方案

由于这是一次模拟面试,我很想知道你是如何有效地解决最后这个问题的。让我知道你将如何实现这个解决方案,或者在 GitHub 上分享你的代码——不要害羞。

我向你保证一件事:如果你能在真正的面试中做到这一点,可能你不知道这个问题的最佳解决方案也不会太重要。这并不意味着你不应该尽力去解决它,但请放心,你已经做得非常好了。

就是这些啦,现在我想看看你的代码。

总结

在这篇文章中,我尝试总结一些我认为在编程面试中最重要的方面。我特别强调协作部分,因为我认为大多数人都低估了这种技能的重要性。这是必须的,特别是如果你想和其他开发者在一个团队中工作。

我尝试通过一个模拟面试来引导你,我解释了在面试中我对于一个标准的编程任务将遵循的思考过程。我希望这个练习是有用的,它可以在下一次面试中帮助你(作为候选人或面试官)。

欢迎分享你对这次模拟面试的想法,让我们开始一场富有成效的讨论。

回头见!👋

资源

👋 我是 Alberto,doWhile 的软件工程师、竞争性程序员、老师和健身爱好者。

🧡 如果你喜欢这篇文章,请考虑分享它。

🔗 All links | Twitter | LinkedIn