Skip to content

Latest commit

 

History

History
88 lines (62 loc) · 6.71 KB

八股文骚套路之数据结构.md

File metadata and controls

88 lines (62 loc) · 6.71 KB

数据结构和算法密不可分，算法+数据结构=程序。

国内现在的面试非常重视数据结构相关问题，尤其是像字节跳动、腾讯这类大公司。

数据结构相关的考察通常会以算法题的形式出现，比如面试官让你反转一个链表。面试官也会在面试中穿插提问一些数据结构相关的概念，比如在询问 MySQL 索引的时候，面试官大概率就会问你 B 树& B+树相关的问题。

上一篇八股文中我们总结了算法相关的内容，详见八股文骚套路之算法 。这篇文章我们简单来聊聊如何准备数据结构面试。

数据结构面试准备

数据结构的种类非常多，不过最常用同时也是面试最常问的数据结构主要就是下面这些：

  • 线性数据结构：
    • 数组 ：数组（Array） 是一种很常见的数据结构。它由相同类型的元素（element）组成，并且是使用一块连续的内存来存储。
    • 链表 ：链表（LinkedList） 虽然是一种线性表，但是并不会按线性的顺序存储数据，使用的不是连续的内存空间来存储数据。链表的插入和删除操作的复杂度为 O(1) ，只需要知道目标位置元素的上一个元素即可。但是，在查找一个节点或者访问特定位置的节点的时候复杂度为 O(n) 。
    • 栈 ：栈 (Stack)只允许在有序的线性数据集合的一端（称为栈顶 top）进行加入数据（push）和移除数据（pop）。因而按照 后进先出（LIFO, Last In First Out） 的原理运作。在栈中，push 和 pop 的操作都发生在栈顶。栈常用一维数组或链表来实现，用数组实现的栈叫作 顺序栈 ，用链表实现的栈叫作 链式栈 。
    • 队列 ： 队列（Queue）是 先进先出( FIFO，First In, First Out) 的线性表。在具体应用中通常用链表或者数组来实现，用数组实现的队列叫作 顺序队列 ，用链表实现的队列叫作 链式队列 。队列只允许在后端（rear）进行插入操作也就是 入队 enqueue，在前端（front）进行删除操作也就是出队 dequeue。队列的操作方式和堆类似，唯一的区别在于队列只允许新数据在后端进行添加。
  • 图 ：图就是由顶点的有穷非空集合和顶点之间的边组成的集合。通常表示为：G(V,E)，其中，G 表示一个图，V 表示顶点的集合，E 表示边的集合。图可以被简单的分为：无向图和有向图，无权图和带权图。
  • 树 : 树就是一种类似现实生活中的树的数据结构（倒置的树）。任何一颗非空树只有一个根节点。常见的树的种类有：平衡树、二叉搜索树、平衡二叉树、红黑树、B 树、LSM 树、字典树（Trie 树）
  • 堆 ：堆是一种满足特定条件的树：堆中的每一个节点值都大于等于（或小于等于）子树中所有节点的值。或者说，任意一个节点的值都大于等于（或小于等于）所有子节点的值。堆分为最大堆和最小堆。
  • 哈希表 ：也叫散列表，是根据关键码值(Key value)而直接进行访问的数据结构，通过 key 就能获取到指定的 value ，速度非常快。
  • 跳表 ：跳表（Skip List）是由 William Pugh 发明的一种查找数据结构，支持对数据的快速查找，插入和删除。跳表的查询，插入和删除操作的期望时间复杂度都为 O(log n)。

常见问题总结 ：

  • 通用常识：像数据结构的定义，查找、插入、删除元素的时间复杂度，应用场景是每一个数据结构都应该掌握的最基本的点。
  • 线性数据结构 ：
    • 数组 vs 链表
    • 栈 vs 队列
    • 实现一个栈/队列
    • 翻转链表、返回链表中倒数第 n 个节点、链表合并......
  • 图 ：
    • 图的常见概念比如顶点的度
    • 图的遍历算法（广度优先搜索和深度优先搜索）
    • 拓扑排序
    • 欧拉回路
    • 迪杰斯特拉（Dijikstra）算法（最短路径问题）
  • 树 ：
    • 二叉树的前序遍历、中序遍历、后序遍历
    • 二叉查找树的出插入、查找、删除
    • 二叉树的高度计算
    • 红黑树 vs 二叉查找树
  • 堆 ：
    • 堆中插入数据
    • 如何删除堆顶元素
    • 堆排序
  • 哈希表 ：
    • 哈希冲突是什么？如何解决？
    • 键值的映射关系如何维护？哈希函数如何设计？
  • 跳表：
    • 为什么 Redis 选择使用跳表而不是红黑树来实现有序集合？
    • 跳表的查找、插入、删除元素的流程
    • 跳表插入元素时，如何动态维护索引？

数据结构系统学习

Github 上有一个叫做 OI-wiki总结了编程竞赛相关的知识点，其中就包含了数据结构、算法、编程语言等等知识点。并且，数据结构部分基本把最常用的数据结构都总结到了。

在线阅读地址：https://oi-wiki.org/ds/ 。

数据结构和算法是不分家的，因为，大部分书籍都是同时讲数据结构和算法。比如我们在八股文骚套路之算法 这篇文章中推荐的算法和数据结构入门书籍 《我的第一本算法书》 以及算法和数据结构进阶学习书籍 《算法》 。

我在八股文骚套路之算法 较为详细地介绍了这两本书，并且，还给出了《算法》这本书的配套学习教程和网站。我这里就不在花费额外的篇幅来介绍这两本书了。

强烈安利 3 个可以可视化数据结构和算法的网站，超级顶！非常非常有助于帮助我们理解常见的算法以及数据结构。

第一个网站是 Data Structure Visualizations。地址：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html 。

这个网站已经有很多常用的数据结构与算法的可视化，例如常见的栈，队列，递归，二叉树、B 树等等。

可视化效果如下：

第二个网站是 VisuAlgo，一个非常精致的数据结构和算法可视化网站。地址：https://visualgo.net/zh 。这个网站支持搜索功能，

可视化效果如下：