第三章：算法面试详解-灵析社区

1. Stage 1：介绍

在面试开始时，大多数情况下面试官会简单介绍自己和他们在公司的角色，然后让你做自我介绍。

准备并排练一段自我介绍。自我介绍应该在 30 秒内总结你的教育背景、工作经历和兴趣爱好。
保持微笑，且让说话的声音听起来自信。
当面试官谈论他们在公司的工作时，请注意听 - 这有助于稍后提出相关问题。
如果面试官提到任何你也感兴趣的事情，无论是他们的工作还是爱好，提出来。

2. Stage 2：问题陈述

在自我介绍之后，面试官会给你一个问题陈述。如果您在共享文本编辑器中答题，他们很可能将问题描述和测试用例一起粘贴到编辑器中，然后将问题读给您听。

确保你完全理解了这个问题。在面试官把问题读完之后，通过将其解释回给他们来确认问题在问什么。
询问有关输入的问题阐述，例如:

输入是只有整数，还是可以有其他类型？

我能假设输入是有序的吗？

输入是保证有元素还是可以为空？

如果给出了无效输入，我该如何处理？

询问预期的输入大小。有时候，面试官会含糊其辞，但如果他们确实给了你一个范围，这可能是一个线索。例如，如果 n 非常小，则可能是回溯。如果 n 在 100 - 1000 左右，O(n ² ) 的解决方案可能是最优的。如果 n 非常大, 那么你可以需要比 O(n) 更好的解决方案。

提出明确的问题不仅能帮助你更好地理解问题，还能表现出对细节的关注，以及对边缘情况的考虑。

3. Stage 3：头脑风暴 DS&A

尝试找出适用的数据结构或算法。分解问题并尝试找到你会的常用解法。弄清楚问题需要你做什么，并考虑什么样的数据结构或算法可以以较好的时间复杂度来完成。

把你的想法都说出来。这会让面试官知道你善于权衡利弊。如果问题涉及到查看子数组，那么应该考虑滑动窗口，因为每个窗口都代表一个子数组。即使你错了，面试官仍然会欣赏你的思考过程。

通过把想法都说出来，面试官也可以借此给你提示，并为你指出正确的方向。

一旦决定了要使用的数据结构/算法，现在就需要构造实际的算法。在编码之前，你应该考虑算法的大致步骤，向面试官解释这些步骤，并确保他们理解并同意这是一个合理的方法。通常，如果你走错了路，他们会巧妙地暗示你。

在这个阶段你能接受面试官所说的话是非常重要的。请记住：他们知道最佳解决方案。如果他们给你提示，那是因为他们希望你成功。不要固执，准备好探索他们给你的想法。

4. Stage 4：实操

一旦你想出了一个算法，并让面试官同意了，就该开始写代码了。

如果你打算使用一个库或模块，例如 Python 的集合，在开始之前确保面试官可以接受。
当你写代码时，解释你的决策。例如，如果你正在解决一个图形问题，当你声明一个集合 seen，解释它是为了防止访问同一个节点超过一次，从而也防止了循环。
编写干净的代码。每一种主流的编程语言都有一个关于代码应该如何编写的约定。确保你知道你打算使用的语言的基础知识。Google 提供了适用于所有主流语言的总结。最重要的部分是大小写约定、缩进、空格和全局变量。
避免重复代码。例如，如果您在网格上进行 DFS 操作，则应该反复使用方向数组 [(0, 1), (1, 0), (0, -1), (-1, 0)] ，而不是为每个方向编写相同的逻辑 4 次。如果你发现自己在多个地方编写类似的代码，可以考虑创建一个函数或使用循环来简化它。
不要害怕使用辅助函数。它们使你的代码更加模块化，这在实际软件工程中非常重要。之后的代码说不定还会用上辅助函数。

如果你遇到困难或意识到你最初的计划可能行不通，不要慌。与面试官交流你的疑虑。如果你默默地挣扎，很可能又会钻牛角尖。

一种策略是首先实现一个暴力解决方案，同时承认这是一个次优解决方案。完成后，分析算法的每个部分，找出哪些步骤 “慢”，并尝试思考如何加快速度。让面试官参与进来，让他们参与讨论 —— 他们通常愿意提供帮助。

5. Stage 5：测试 & debug

一旦你写完代码，你的面试官可能会想要测试你的代码。根据公司的不同，会有一些不同的环境:

内置测试用例，代码需要运行

这些平台类似于 LeetCode。将会有各种各样的测试用例 —— 小输入，大输入，测试边缘用例的输入。

这种环境给您的代码带来了最大的压力，因为会暴露出不完美的解决方案。

但是，它也为创建您自己的测试带来了最小的压力，因为测试用例已经内置在了内部。

自己写测试用例，代码需要运行

这些平台通常是支持运行代码的共享文本编辑器。面试官会希望你编写自己的测试用例。

要真正测试代码，你应该在代码的最外层范围编写，即代码将首先运行的地方。假设你在函数中解决了问题 (就像在 LeetCode 上)，你可以用你编写的测试用例调用你的函数，并将结果打印到控制台。

在编写自己的测试时，请确保尝试各种测试。包括边缘情况、直觉输入和可能无效的输入 (如果面试官想让你处理这种情况)。

自己写测试用例，代码不需要运行

这些平台只是共享文本编辑器，不支持运行代码。面试官会希望你编写自己的测试用例，并且手动模拟运行。

为了 “测试” 代码，你必须在每个测试用例中手动检查算法。试着压缩一些琐碎的部分 —— 例如，你正在创建一个前缀和，不要字面上遍历每个元素的 for 循环。可以这样说:“在这个 for 循环之后，我们将有一个前缀和，他是这样的……”。

在遍历代码时，将函数中使用的变量写入 (在编辑器中，函数外部的某处)，并不断更新它们。

不管在什么情况下，如果您的代码出现了错误，不要慌!如果环境支持运行代码，请在相关位置放置打印语句以尝试识别问题。用一个小的测试用例手动遍历(就像你没有运行环境时所做的那样)。当你这样做的时候，讨论变量的期望值应该是什么，并将它们与实际值进行比较。再说一遍，你说话越多，面试官就越容易帮助你。

6. Stage 6：解释与跟进

在编写算法并运行测试用例之后，准备回答关于算法的问题。你应该准备好回答的问题包括:

算法的时间和空间复杂度是多少？

你应该从最坏的情况来考虑。但是，如果最坏的情况很少，并且平均情况的运行时明显更快，那么你还应该提到这一点。

你为什么选择……？

这可以是你对数据结构的选择，算法的选择，循环配置的选择。准备好解释你的思考过程。

你认为算法在时间和空间复杂度上是否可以改进？

如果问题需要遍历输入中的每个元素 (假设输入没有排序，需要找到最大的元素)，那么你很可能无法比 O(n) 更快。否则你很可能无法比 O(logn) 更快。

如果面试官问这个问题，答案通常是肯定的。在断言你的算法是最优的时候要小心 —— 不要轻易使用绝对的形容。

如果面试还有剩余时间，你可能会被问到一个全新的问题。在这种情况下，从步骤 2（问题陈述）重新开始。但是，你也可能会被要求对你已经解决的问题进行跟进。面试官可能会引入新的约束，要求改进空间复杂度，或任何其他数量的东西。

这部分是为什么真正理解解决方案而不是仅仅记住它们很重要的原因。

7. Stage 7：结尾

面试官通常会在面试结束时留出几分钟的时间让你问一些关于他们或公司的问题。在这一点上，很少能改善面试的结果，但你肯定能让它变得更糟。

面试是双向的。你应该利用这段时间来了解这家公司，看看你是否愿意在那里工作。你应该在面试前准备一些问题，比如:

在公司的一天中会做些什么？
你为什么决定加入这家公司而不是另一家公司？
关于这份工作，你最喜欢和最不喜欢的是什么？
我可以从事什么样的工作？

所有的大公司都会有自己的科技博客。展示你对这家公司感兴趣的一个好方法是阅读一些博客文章，并编制一个关于公司为什么做出这些决定的问题清单。

保持兴趣，保持微笑，倾听面试官的回答，并提出后续问题，以表明你理解他们的答案。

如果你没有高质量的问题，或者表现得无聊或不感兴趣，这可能会给面试官一个不好的信号。如果面试官最后不喜欢你，你在技术方面做得再好也没用。

8. Stage 8：面试备考总览

以下是「面试的阶段」一文的摘要。如果您进行远程面试，您可以打印此浓缩版并在面试期间将其放在您面前。

第一阶段：介绍

30-60 秒介绍您的教育、工作经验和兴趣。
自信，保持微笑。
当面试官谈论他们自己时要注意，稍后将他们的工作纳入您的问题。

第二阶段：问题陈述

在面试官将问题读给你听后，将问题复述给他们。
询问有关输入的问题描述，例如预期的输入大小、边缘情况和无效输入。

第三阶段：头脑风暴 DS&A

把你所有的想法都说出来。
分解问题：弄清楚你需要做什么，并思考什么数据结构或算法可以以良好的时间复杂度完成它。
接受面试官的任何评论或反馈，他们可能试图暗示您找到正确的解决方案。
一旦你有了想法，在编码之前，向面试官解释你的想法，并确保他们理解并同意这是一种合理的方法。

第四阶段：实操

在你实际编码时解释你的决策。当你声明集合之类的东西时，解释一下目的是什么。
编写符合规范编程语言约定的代码。
避免编写重复代码 - 如果你多次编写类似代码，请使用辅助函数或 for 循环。
如果你被卡住了，不要惊慌 - 与你的面试官交流你的疑虑。
不要害怕暴力解决方案（同时承认它是暴力解法），然后通过优化 “慢” 的部分来改进它。
继续把你的想法说出来并与面试官交谈。这让他们更容易给你提示。

第五阶段：测试 & debug

遍历测试用例时，通过在文件底部写入来跟踪变量，并不断更新它们。压缩琐碎的部分，例如创建前缀和以节省时间。
如果有错误并且环境支持运行代码，将打印语句放入你的算法并遍历一个小测试用例，比较变量的预期值和实际值。
如果遇到任何问题，请直接说出问题并继续与面试官交谈。

第六阶段：解释和跟进

您应该准备回答的问题：

时间和空间复杂度，平均和最坏情况。
你为什么选择这个数据结构、算法或逻辑？
您认为该算法可以在复杂性方面进行改进吗？如果他们问你这个问题，那么答案通常是，特别是如果你的算法比 O(n) 慢。

第七阶段：结尾

准备好有关公司的问题。
对面试官的回答表现出感兴趣、微笑并提出后续问题。