算法面试题
# 数据结构和算法
数组和链表随机访问的时间复杂度，数组和链表的区别，数组和链表优点缺点，应用场景【描述】
数组有 10 万个数据，取第一个和取第 10 万个的耗时多久？
你觉得递归有什么缺点？怎么改进代码（爆栈和内存溢出）
爆栈属于什么类型的错误？系统错误还是什么？（没答上来...）
说说对堆栈溢出的理解
简单说下栈和队列？如何用栈实现队列？
栈和队列特点?相互实现?
尾递归、尾调用
最小生成树的定义和构建过程，知道的算法实现思路都说一下
B 树、B+树的区别
栈、队列、堆的分别使用场景，链表平时有用到吗
KMP 算法和 KMP 改进算法的具体思路和实现方法
哈希存储结构的构成方式 （哈希值，哈希表，哈希冲突）
一个很大的树结构，不去递归，怎么快速定位到某一结点
从底层谈谈 map 数据结构的设计。如果容量不够了怎么办，扩容过程中可能会耗费比较多的时间，如果在扩容时要访问怎么办；
# 算法题
实现 36 进制转换
合并乱序区间
LRU 算法
这个题我最开始用 Map 做的，面试官跟我说如果不用 Map，如何实现每次查询和删除都能做到 O(1)，我没思路，面试官问我查询 O(1)用什么，我说用哈希，问我插入删除 O(1)用什么，我说用链表，可我不知道怎么结合到一起，面试官提示我可以用双向链表，然后我才做出来的
算法: 股票买卖
# 排序算法题
常用的排序算法，时间复杂度和空间复杂度分别是多少
二分查找的时间复杂度是多少，简要描述一下过程，O(logN)是怎么算出来的，TopK 的时间复杂度是多少，快排的时间复杂度是多少
归并排序的思路是什么，一个数组做归并排序的话，一共经历了多少次合并
希尔排序的时间复杂度和空间复杂度多少？
统计大文件 tok k 词频 用桶排序,优化成堆排序,又用 hash 优化,好像都不满意
插入排序
讲一讲插排和快排的实现过程，插排与快排的时间复杂度分析
快速排序
说说快排的优化
快速排序第一轮过程，怎么优化快速排序(中轴选中位数,随机打乱)
快排思路及时间复杂度，如果头尾指针每次相遇都在 1/3 处，其时间复杂度是多少（orz）
快排是不是稳定的
为什么快排是 nlogn
归并排序
归并排序是怎么实现的
外排序
有 1TB 的数据，32GB 内存，怎么排序（外排序）
# 数据结构算法题
# 数组
概念
数组存储怎么压缩(稀疏矩阵，三元组有关知识)
算法题
给你一个已经升序排列的数组，给一个数字，找一下这个数字在这个数组里出现了几次
合并两个有序数组
合并多个有序数组
这题里我解答完之后自认为时间复杂度是 O(n2)，循环中用到了 shift 这个方法，面试官问我这个的时间复杂度是多少，我说是 O(n)，面试官说有什么办法可以解决这个么，我说可以基于原有的方式倒着循环，这样就可以用 pop 代替 shift 了，面试官问我为什么 pop 时间复杂度是 O(1)，我说不知道，面试官让我有时间可以去了解一下均摊算法
- 输出数组中频率第二高的元素的下标
在一个无序数组中找到第二大的数
对去重算法进行 O(n)的时间复杂度的优化 并且不能使用 Set,
去重算法再度升级 只能去重引用类型
算法: 最长连续数组和
数组去重，数组内包含 number、string、object 等
# 链表
单向链表反转
如何判断链表是否有环？不用快慢指针的话有什么方法？
链表有环怎么判断?环的长度怎么计算？
# hash 哈希表
hash 冲突怎么解决(拉链法,探针法)
# 树算法题
算法：树的遍历有几种方式，实现下层次遍历
算法：判断对称二叉树
# 图算法题
- 有向图判断是否有环。