面试数据结构

数据结构

定义

用网络形式相互连接的节点

术语

顶点：节点

边：edge，一对节点

权重/成本

类型

有向图

无向图

表示方式

邻接矩阵

邻接表

遍历算法

广度优先搜索DFS

深度优先搜索TFS

面试相关

实现广度和深度优先搜索

检查图是否为树

计算图的边数

找到两个顶点之间的最短距离

单调栈monotone stack很少考

双端队列Deque，很少考

并查集Union Find很少考

线段树，很少考

树状数组Binary Indexed Tree，BIT，很少考

字典树Trie，很少考

也称：前缀树，特殊的树状数据结构

用途

解决字符串相关问题很有效

提供快速检索

搜索字典中的单词

搜索引擎中自动提供建议

用于IP的路由

面试

计算字典树中的总单词数

打印存储在字典树中的所有单词

使用字典树对数组中的元素进行排序

使用字典树从字典中形成单词

构建T9字典：字典树+DFS

键值对的形式存储唯一标识的对象

字典：键值对的集合

使用键key搜索对象value

Java 中的 HashSet / HashMap，C++ 中的 unordered_map，Python 中的 dict

支持操作:O(1) Insert / O(1) Find / O(1) Delete

哈希表的工作原理

工作原理：对于set。key通过hash函数得到一个index，然后把value存在数组里。对于get，通过key和hash函数求出index，得到value。

为什么 hash 上各种操作的时间复杂度不能单纯的认为是 O(1) 的

key可以是字符串，整数等未知长度的东西。所以用O(L)合适；任何操作的时间复杂度从严格意义上来说 都是 O(keySize) 而不是 O(1)

哈希函数该如何实现

128 哈希函数

哈希冲突（Collision）该如何解决

如何让哈希表可以不断扩容？

129 重哈希

性能因素

哈希函数

哈希表大小

碰撞处理方法

数组中查找对称的键值对

是否会灵活的使用哈希表解决问题

是否熟练掌握哈希表的基本原理

追踪便利的完整路径

查找数组是否是另一个数组的子集

检查给定的数组是否不相交

526. 负载均衡器

134. LRU缓存策略657. Insert Delete GetRandom O(1)954. Insert Delete GetRandom O(1) - Duplicates allowed209. 第一个只出现一次的字符

Data Stream类问题960. First Unique Number in a Stream II138. 子数组之和105. 复制带随机指针的链表171. 乱序字符串124. 最长连续序列

排序查找

排序

插入排序

快速排序

选择排序

归并排序

基数排序

堆排序

查找

静态查找表

动态查找表

哈希表

数据结构定义：数据结构可以认为是一个数据存储集合以及定义在这个集合上的若干操作(功能)

考法1：问某种数据结构的基本原理，并要求实现

例题:说一下 Hash 的原理并实现一个 Hash 表

考法2:使用某种数据结构完成事情

例题:归并 K 个有序数组

考法3:实现一种数据结构，提供一些特定的功能

例题:最高频 K 项问题

时间复杂度：

对多个接口的时间复杂度进行描述

比如你需要设计一个 Set 的数据结构

算法1:O(n) lowerBound O(1) add

实现方法：使用数组存储，每次打擂台进行比较，插入就直接插入到数组最后面

算法2:O(logn) lowerBound O(logn) add

实现方法：使用红黑树(Red-black Tree)存储，Java 里的 TreeSet，C++ 里的 map

数组Array，最常考

一维数组

二维数组

多维数组

子数组

数组一部分

面试题

数组区间问题

30. 插入区间793. 多个数组的交集156. 合并区间

外排序问题

定义：外排序算法（External Sorting），是指在内存不够的情况下，如何对存储在一个或者多个大文件中的数据进行排序的算法。

两个基本步骤：将大文件切分为若干个个小文件，并分别使用内存排好序使用K路归并算法（k-way merge）将若干个排好序的小文件合并到一个大文件中

486. Merge K Sorted Arrays104. Merge K Sorted Lists

位运算

定义：对二进制位的运算

365. 二进制中有多少个1

树状数组很少考

又名:Fenwick Tree 英文名字：Binary Indexed Tree 简写:BIT 基于“前缀和”信息来实现——

时间复杂度

Log(n) 修改任意位置值Log(n) 查询任意区间和

功能特性

817. 范围矩阵元素和-可变的249. 统计前面比自己小的数的个数

操作

增get

删delete

插入insert、

大小size

寻找数组中第二小的元素

找第一个不重复的整数

重新排列数组中的正负值

65. 两个排序数组的中位数，难题

6. 合并排序数组 II64. 合并排序数组839. 合并两个排序的间隔列表486. Merge K Sorted Arrays577. 合并K个排序间隔列表547. 两数组的交集548. 两数组的交集 II793. 多个数组的交集654. 稀疏矩阵乘法931. Median of K Sorted Arrays149. 买卖股票的最佳时机405. 和为零的子矩阵944. Maximum Submatrix943. Range Sum Query - Immutable665. 平面范围求和 -不可变矩阵840. 可变范围求和

栈Stack，不常考

后进先出LIFO。比如物流装车，后装的货物先卸

支持操作:O(1) Push / O(1) Pop / O(1) Top

应用

用于非递归的遍历二叉树，计算逆波兰表达式，等等。

非递归实现DFS的主要数据结构

在宽度优先搜索(BFS）中，记录待扩展的节点。

队列可用于实现消息队列（message queue），以完成异步（asynchronous）任务。

当消息“生产”和“消费”的速度不一致时，就需要消息队列，临时保存那些已经发送而并未接收的消息。

实现栈方式

用一个存储结构（常用数组，偶见链表），存储元素

用一个数组实现三个栈？

用两个队列实现一个栈？

区别

数组对随机访问有较好性能。链表对插入和删除元素有较好性能。

练习题

lintcode: 495. 实现栈

494. 双队列实现栈

224. 用一个数组实现三个栈

push，顶部插入元素

pop返回并且移除栈顶元素

isEmpty栈是空，返回true

top返回顶部元素，但不移除它

Java，使用java.util.Stack，它是扩展自Vector类，支持push()，pop()，peek()，empty()，search()等操作。

C++，使用<stack>中的stack即可，方法类似Java，只不过C++中peek()叫做top()，而且pop()时，返回值为空。

Python，直接使用list，查看栈顶用[-1]这样的切片操作，弹出栈顶时用list.pop()，压栈时用list.append()。

使用栈计算后缀表达式

对栈的元素进行排序

判断表达式是否括号平衡

队列Queue，常考

FIFO先进先出的顺序存储线性数据结构，超市结账

支持操作:    O(1) Push / O(1) Pop / O(1) Top

用作 BFS 算法的主要数据结构

enqueue队列尾部插入元素

dequeue移除队列头部元素

isEmpty对列为空，返回true

top返回队列的第一个元素

实现方式

用链表实现队列？

用两个栈实现一个队列？

用循环数组实现队列？

练习题：955. Implement Queue by Circular Array

使用队列表示栈

对队列的前面k个元素倒序

使用队列生成1到n的二进制数

642. Moving Average from Data Stream

955. Implement Queue by Circular Array

链表Linked List，常考

节点链：每个节点包含数据和指向后续节点的指针

实现文件系统，哈希表，邻接表

单向链表

双向链表

insertAtEnd

insertAtHead

Delete

DeleteAtHead

Search

反转链表

检测链表中的循环

返回链表倒数第n个节点

删除链表中重复项

树Tree

层级式的数据结构

顶点和边组成

树中没有图中的环路

root根节点

parent父节点

child子节点

leaf叶子节点

sibling兄弟节点

N元树

线段树，基本不考，万能的

二叉树，常考

二叉搜索树

定义：左子树小于根节点，根节点小于右子树。效果就是：左边永远小于右边

平衡二叉树

平衡树(AVL树)

定义：

它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

实现方法

红黑树、AVL、替罪羊树、Treap、伸展树

堆

定义：堆是一种平衡二叉树，父节点小于子节点，多余的子节点尽可能的放在左子节点，左右子节点无大小关系。可以用数组实现

支持操作:O(log N) Add / O(log N) Remove / O(1) Min or Max

Max Heap vs Min Heap

值特性：对于min堆，父节点小于子节点，左右子节点无大小关系；对于max类型堆，父节点大于子节点，左右子节点无大小关系；

结构特性：是个二叉树，高度logN

插入方法：永远从左侧插入，保证是一个平衡二叉树，如果插入数字小，那就上移，父节点下移。所以复杂度最大就是logN

删除方法类似

实现方法：练习题：lintcode 130 heapify

面试练习题

104. Merge K Sorted Lists612. K个最近的点545. 前K大数 II613. 优秀成绩486. Merge K Sorted Arrays81. 数据流中位数544. 前K大数401. 排序矩阵中的从小到大第k个数

线段树 Segment Tree

定义：线段树是一种高级数据结构，也是一种树结构，准确的说是二叉树。它能够高效的处理区间修改查询等问题。

备注：基本不考，但是如果能掌握，可以一口气解决一大堆问题 线段树是基于分治法实现的，可以作为很好的分治法的练习

求二叉树高度

在二叉搜索树中查找第k个最大值

查找和根节点距离k的节点

在二叉树中查找给定节点的祖先节点

104. Merge K Sorted Lists

3种方法

方法一:使用 PriorityQueue

方法二:类似归并排序的分治算法

方法三:自底向上的两两归并算法

时间复杂度均为 O(NlogK)

来自：大数据文摘：应对程序员面试，你必须知道的八大数据结构

公众号：《湾区人工智能》发布

结合:九章算法 整理而成

练习题都是lintcode的题