二、构建扎实的基础

原文：Chapter 2: Build a Solid Foundation

译者：飞龙

协议：CC BY-NC-SA 4.0

自豪地采用谷歌翻译

这是我们的“谷歌面试准备系列指南”的第二章。 如果你注意到很多工作要求，你通常会看到像“有扎实的计算机科学基础”的东西。 这实际上是什么意思？

显然，这并不意味着你有计算机科学学位，也不意味着你写了很多代码。 在现实中，扎实的计算机科学基础意味着对基础知识有清晰的认识。

在这一章中，我想深入探讨这个话题，并给你如何建立扎实的基础的实用技巧。 我可以说这是谷歌面试准备的切入点，但同时也是最重要的一步。

最短路径

很多人都在寻求谷歌面试准备的“捷径”。 如果存在捷径的话，我想说的是把重点放在计算机科学的基础上。

这里的提示是做长远规划。 最常见的错误是，清晰理解基础知识之前练习编码问题。 这些人在短期内可能会有更好的表现，但他们迟早会回来重新学习基础知识。

这是因为如果没有完全理解基本的数据结构和算法，想出正确的想法和编写无错代码几乎是不可能的。 如果你真的想做好准备，从长远的角度来看，在基本的事情上花费足够的精力将会为你节省大量的时间。

我强烈建议人们，在对基础有信心之前不要尝试面试问题。

扎实的基础对你意味着什么？

有时，人们问我，扎实的计算机科学基础是什么意思？我可以写代码，我知道冒泡排序，这是否意味着我很好？

对于编程面试来说，基础大多意味着基本数据结构和算法的清晰理解。我将在这篇文章中逐步解释这一点。但是试着回答下面的问题：

如何在图中进行搜索？每种方法的优缺点是什么？如何决定使用哪一个？
对于对象列表，可以使用链表，数组，栈，队列和其他数据结构。你将如何决定使用哪一个？最大的优势/劣势是什么？
动态规划和递归有什么区别？你如何比较递归解决方案和它的迭代版本？
如果我想将我的解决方案从O(n^2)的时间复杂度提高到O(nlogn)，你会想到什么算法？ O(n)又如何？

这些只是我脑海中的一些示例性问题，如果你不能立即回答所有问题，最好回顾你的算法书籍。

让我们一步一步解构计算机科学基础。

定义

首先，你应该清楚每个基本数据结构和算法的定义。 大多数人解释链表是什么没有什么问题，但它还有很多东西。

首先，一些概念有点混乱。 例如，很多候选人不完全了解动态规划和递归之间的区别。 另一个例子是栈和堆，以及它们如何在内存中使用。 这篇文章不会给你具体的答案，但如果你只进行简单的谷歌搜索，你会发现这一切。

其次，你也应该能够实现它们。 最好的例子是快速排序。 该算法在实现方面并不是很容易，但可能会非常有帮助。 如果你想实现在数组中找到第k个最大的数字，你应该用一个堆（译者注，这里原文有错误）。 BFS/DFS 也是类似的，很多面试问题都是关于如何编写 BFS/DFS（例如遍历一个树）。

优缺点

试中最大的麻烦是候选人不知道要使用哪种数据结构/算法。 根本原因是他们从来没有想过每个数据结构/算法的优缺点。 这个想法是，所有这些基本的数据结构/算法都像你的武器，如果你想在正确的时间使用正确的数据结构/算法，你应该非常熟悉他们的特性。

幸运的是，大部分资源和书籍在同一个大章节中组合了类似的工具。 例如，链表，数组，栈和队列在一个集合中。 BFS 和 DFS 在另一个集合中。

我们以 BFS 和 DFS 为例。

  • 在一个树形结构中，DFS 将尝试到达最深的叶子节点，回到原处，并找到另一个叶子节点。 所以使用了一个栈，并且可以递归地（易于编写）和迭代地实现。
  • 好处是，当你要检查节点是否可到达或想要找到从 A 到 B 的路径时，DFS 是最佳选择。
  • 同样，BFS 横向遍历，并使用队列。
  • 如果你想找到最短路径的长度或者遍历层次，你应该使用 BFS。

所以作业是针对每一个数据结构/算法，你应该问自己：有什么优点/缺点？ 我什么时候可以使用它？

复杂度

这是很多人忽略的。作为一个面试，对于我所问的每一个编程问题，我一定会问及时间和空间的复杂度。同样，在复习数据结构/算法时，你应该清楚复杂度。事实上，你也应该对你练习的每一个问题做这个。

如果你对此非常熟悉，那么当你尝试确定要使用哪种算法时，这会非常有用。例如，最常见的情况是你的解决方案很慢，面试官要求你对其进行优化。假设你有一个O(n^2)的方法，为了让它更快，我们可以这样想：

  • 一般来说，为了提高速度，我们可以选择更好的数据结构/算法，或者使用更多的内存。
  • 如果我们想使它成为O(nlogn)，有几种可用的工具：二分搜索，排序，BST 等等。也许你应该尝试对数组排序，看看你是否可以利用它。
  • 要使用更多的内存，散列是一个选项。另外，DP 是优化递归的好方法。

如果你这样想，你的生活会更轻松，因为你有更少的选项来选择。

总结

技术面试备忘录和大 O 备忘录有很多这个主题的资源。 此外，也推荐《算法导论》这本书，虽然有些章节是可选的。

作为一名面试官，我绝对不会通过弄不清基本概念的候选人。 对我来说，这就像候选人不知道他在做什么。 相反，即使有人没有彻底解决问题，如果一切都清楚的话，他还是有机会的。

我会建议人们逐个查阅所有基本的数据结构/算法。 了解这个概念，弄清楚利弊，并自己实现。 在这一步完成之前，不要急于练习编程问题。

顺便提一下，如果你想得到资深的面试官的更多指导，可以查看 Gainlo，以便与 Google，Facebook 等公司的工程师进行模拟面试。