技术面经:数据结构和算法汇总

大家好,我是Lucy@FinTech社区,今天的文章将为大家带来技术面经:数据结构和算法汇总。欢迎添加以下微信,加入FinTech社区,提认知,攒人脉,求职招聘,投资有术!

 

在努力的过程中,人们常见的一个问题是“我该如何学习”?怎么样才能更有针对性?才是最适合自己的路径?

首先,Trello 这个工具给了我不少帮助,让我专注于各种学习的主题和方向,并且给我很好的总结归纳。

 

相关的信息:

https://trello.com/templates/personal/interview-study-tracker-5g9FvwSF

 

你可以看到实际上他提供了很多主题,可以有目的性的选择和练习,使用起来还是很方便的。

另外我们也可以谈一些学习方法,比如从不同的角度学习同一件事可以帮助大家更好地理解这个问题。

例如,有关二进制搜索树的题目,除了leetcode原题,也可以参考一些算法书来获得原理上的验证和其他灵感,这样做一些题目,再扩展知识,再做一些,可以更有效的帮助大家理解。

 

全面的学习路径

在此提供一些干货,下面列出了在技术面试中可能遇到的几乎所有数据结构和算法,以及非常简短的描述和一些资源。根据这些资源,大家可以有针对性的搜索题目和信息,构建自己的学习方案。

如果以前没有听说过列表中的某些数据结构,或者对它们不了解太多,没关系,它们可能看起来很复杂,但是随着学习的深入和进步,相信你很快就会有第一次看到并理解Array这样简单的概念相同的感受。

 

基本数据结构

这些被认为是基本的。每个人都应该知道它们是如何工作的,何时使用它们,如何实现它们:

  • Array(数组)
  • Set (集合)
  • Hashmap(哈希)
  • Linked List(链表)
  • Stack(栈)
  • Queue(队列)
  • Tree(树)
  • Graph(图)

 

如果还觉得太多,请不要担心。这些数据结构中有很多是紧密相关的,甚至是相互依存的,因此您可以比您想象的更快地学习它们。

Hashmap基于数组。stack建立在LinkedLists或Arrays上。queue建立在LinkedLists上。tree共享LinkedList中“节点”和“边”的概念。

图也具有相同的概念,和tree也有很多相似之处。从技术上讲,所有树也是图,因此许多算法也是可以互相借鉴的

 

进阶数据结构

掌握了基本的数据结构后,了解这些更高级的结构将大大提高面试成功率,实际上这些结构也是验证我们计算机水平的标志。

一些在面试中经常出现,例如“heap”和“Binary Search Tree (二叉搜索树)”。LRU缓存也变得越来越普遍。

 

它们通常是使用基本的数据结构来构建的。深入了解基本数据结构将使学习这些高级数据结构变得更加容易

  • Heap (a.k.a Priority Queue)
  • LRU Cache
  • Binary Search Tree (AVL, Redblack)
  • Disjoint Set
  • Trie
  • Skip List

 

堆(也称为优先队列)是一种行为类似于队列的树。二进制搜索树(BST)是另一种树,可以更快地搜索节点。

AVL和Redblack是平衡BST的两种流行的特殊类型。LRU缓存是通过将Hashmap与LinkedList组合而成的有效缓存算法。

Trie是另一种可快速搜索前缀/子字符串的树。不相交集是一种特殊类型的集合,它将其成员分成不重叠的子集。Skip List是LinkedList的优化版本,可减少查找某些节点所需的时间。

 

基本搜索/遍历算法

所有数据结构都旨在保存信息。一些结构需要特殊的方式来有效地访问此信息,这些方式比简单地访问数组索引或哈希图键更复杂。

保存诸如树和图之类的数据集合的数据结构使用一些基本算法来访问其中的信息。

  • 广度优先搜索(BFS)
  • 深度优先搜索(DFS)
  • 二元搜寻

 

高级搜索/遍历算法

该领域有大量研究,但出于技术面试的目的,您可能会按频率顺序遇到的最先进的搜索算法是:

  • Quick Select
  • Dijkstra
  • Bellman-Ford
  • A-star (相对少见)

 

排序算法

排序是用于提高解决方案性能的常用工具。排序算法很多,但是下面列出了最受欢迎的采访算法。知道如何在不查找任何内容的情况下实现所有这些功能。

  • 快速排序
  • 合并排序
  • 拓扑排序
  • 计数排序

 

一些重要考点

递归是一个非常重要的主题,它在日常软件工程中的重要性不如在面试中那么高。

乍一看,bit相关的算法似乎很吓人,但是一旦花时间了解二进制数字格式和操作,其实是非常简单的。

  • 递归
  • 贪婪算法
  • 动态编程
  • 位操作(AND,NOT,OR,XOR)

 

常见算法模板

这些模板可用于解决许多类似的算法问题。

  • 回溯
  • 双指针
  • 滑动窗口
  • 分而治之
  • 储层采样
  • 数学原理
  • 排列
  • 组合方式
  • 阶乘
  • 幂集