数据结构和算法研究编码面试备忘单
原文：https://www.techinterviewhandbook.org/algorithms/study-cheatsheet/
这个是什么
这一节深入探讨算法面试中经常出现的算法和数据结构的实用知识和技术。你掌握的技巧越多，通过面试的几率就越高。他们可能会引导你发现你可能错过的角落案例，甚至引导你找到最佳方法！
每个学习指南的内容
对于每个主题，您可以找到:
- 简要概述
- 学习资源
- 要使用的特定于语言的库
- 时间复杂性备忘单
- 面试时要注意的事情
- 角落案例
- 有用的技巧和建议练习的问题
学习指南列表
下面是你应该为编码面试准备的数据结构和算法列表，以及相应的学习指南:
| 主题 | 优先 |
|---|---|
| 数组 | 高的 |
| 字符串 | 高的 |
| 哈希表 | 中间的 |
| 递归 | 中间的 |
| 分类和搜索 | 高的 |
| 矩阵 | 高的 |
| 链表 | 中间的 |
| 队列 | 中间的 |
| 堆栈 | 中间的 |
| 树 | 高的 |
| 图形 | 高的 |
| 堆 | 中间的 |
| 排序 | 中间的 |
| 间隔 | 中间的 |
| 动态编程 | 低的 |
| 二进制 | 低的 |
| 数学 | 低的 |
| 几何形状 | 低的 |
一般面试技巧
澄清你潜意识里的任何假设。许多问题被有意地低估了。
总是首先验证输入。检查无效/空/负/不同类型的输入。永远不要假设您得到了有效的参数。或者，向面试官澄清你是否可以假设有效的输入(通常是)，这样可以节省你编写输入验证代码的时间。
是否有任何时间/空间复杂性要求/限制？
检查一个接一个的错误。
在没有自动类型强制的语言中，检查值的串联是否属于同一类型:int / str / list。
完成代码后，使用一些示例输入来测试您的解决方案。
该算法是否意味着要多次运行，例如在 web 服务器中？如果是，输入可能需要预处理，以提高每次调用的效率。
混合使用函数式和命令式编程范例:
- 尽可能写纯函数。
- 纯函数更容易推理，有助于减少实现中的错误。
- 避免改变传递到函数中的参数，特别是如果它们是通过引用传递的，除非你确定你在做什么。
- 然而，函数式编程通常在空间复杂度方面是昂贵的，因为非突变和新对象的重复分配。另一方面，命令式代码更快，因为您操作的是现有对象。因此，您需要通过在适当的地方使用适量的功能性和命令性代码来实现准确性和效率之间的平衡。
- 避免依赖和改变全局变量。全局变量引入了状态。
- 如果你必须依赖全局变量，确保你不会意外地改变它。
一般来说，要提高一个程序的速度，我们可以:(1)选择更合适的数据结构/算法；或者(2)使用更多的内存。后者展示了一个经典的空间与时间的权衡，但不一定是以牺牲空间为代价才能获得更快的速度。另外，请注意，您的程序运行速度通常有一个理论上的限制(就时间复杂性而言)。例如，一个要求你在一个未排序的数组中寻找最小/最大元素的问题的运行速度不能超过 O(N)。
数据结构是你的武器。为正确的战斗选择正确的武器是胜利的关键。非常熟悉每种数据结构的优势及其各种操作的时间复杂性。
可以扩充数据结构，以实现跨不同操作的高效时间复杂性。例如，哈希映射可以与双向链表一起使用，以实现在 LRU 缓存中的get和put操作的 O(1)时间复杂度。
哈希表可能是算法问题最常用的数据结构。如果你被困在一个问题上，你的最后一招可能是列举常见的可能的数据结构(幸好没有那么多)，并考虑是否每一个都适用于这个问题。这有时对我有用。
如果你在代码中偷工减料，大声告诉你的面试官，并告诉他在非面试环境下你会怎么做(没有时间限制)。例如，我会编写一个正则表达式来解析这个字符串，而不是使用split()，因为它可能无法涵盖所有情况。
推荐课程
AlgoMonsterT3】
AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式，并有内容帮助你快速修改基本的数据结构和算法。最重要的是，AlgoMonster 不是基于订阅的——支付一次性费用，就可以获得终身访问。 今天加入七折优惠→
寻找编码面试:编码问题的模式
设计大师的这门课程扩展了推荐练习题中的问题，但从问题模式的角度来进行练习，这是一种我也同意的学习方法，我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题，并提供这些语言的示例解决方案以及一步一步的可视化。学习和理解模式，而不是背答案！ 现在获得终身使用权→
掌握编码面试:数据结构+算法
这本 Udemy 畅销书是评分最高的面试准备课程之一(4.6 星，21.5k 评分，135k 学生)，包含了价值 19 个小时的内容。像技术面试手册一样，它超越了编码面试，涵盖了简历，非技术面试，谈判。是一个全包！请注意，JavaScript 用于编码演示。 结账→
