互联网公司最常见的面试算法题有哪些？

忘是亡心i 2023-06-13 09:13 1阅读 0赞

**很多时候，你即使提前复习了这些最常见的面试算法题，你依旧无法通过算法面试！**

**为什么？**

1.  **你在提前准备复习的时候，在网上找了半天相应题目的分析文章，但你看了就是不懂。**
2.  **你在面试的时候，卡壳了，一时间忘了怎么写代码了**

**怎么办？**

**我来助你一臂之力！！**

为了避免知乎大佬觉得我吹逼，先贴一下自己的 GitHub 地址，**目前 20 k star。**

12月初，将**图解算法**项目放到了GitHub上面去，短短两天登上了 trending 版第一的位置，点击这了解如何

**我是如何**  [21天，在Github上获取 6300 star][21_Github_ 6300 star]  **的。**

![v2-18e366164812f84a473fea4672c4946d\_b.jpg][v2-18e366164812f84a473fea4672c4946d_b.jpg]

![v2-a207d4b674ee3e9925b66db15f1f467d\_b.jpg][v2-a207d4b674ee3e9925b66db15f1f467d_b.jpg]

![v2-bce42665367e5b6423e6fb30adb6e5f4\_b.jpg][v2-bce42665367e5b6423e6fb30adb6e5f4_b.jpg] 目前有 16k star

\----------------------------------------------------------------------------------------------

我将那几个有意思的经典互联网公司的面试题目都详细的分析了一遍，每个题目都写了比较详细的分析过程，大部分文章都**配了动画，目前还在持续更新中。。。**

**配了动画是为了加强理解，并且希望等你面试的时候没有思路，通过动画能联想起来！（觉得有帮助的，记得点个赞关注走一波，谢谢大家）**

## \------------------------------------------------------------------------------- ##

1. 给你一个长度为 n 的数组，其中只有一个数字出现了奇数次，其他均出现偶数次，问如何使用优秀的时空复杂度快速找到这个数字。

[一道让你拍案叫绝的算法题][Link 1]

2. 假设有 100 层的高楼，给你两个完全一样的鸡蛋。请你设计一种方法，能够试出来从第几层楼开始往下扔鸡蛋，鸡蛋会碎。 请问最坏情况下，至少需要试验多少次才能知道从第几层楼开始往下扔鸡蛋，鸡蛋会碎。

[一道腾讯面试题：厉害了我的杯][Link 2]

3. 请设计一个 LRU 算法。

[看动画轻松理解「链表」实现「LRU缓存淘汰算法」][LRU]

4.什么是动态规划？ 30 张图片动画详细分析！

[看动画轻松理解「递归」与「动态规划」][Link 3]

2019年04月25日补充：

我按标签**用动画**整理了一下 LeetCode 的题目，可以按需查看。

[链表算法面试问题？看我就够了！][Link 4] [几道和「二叉树」有关的算法面试题][Link 5] [几道和散列（哈希）表有关的面试题][Link 6] [几道和「堆栈、队列」有关的面试算法题][Link 7] [有点难度，几道和「滑动窗口」有关的算法面试题][Link 8] [几道和「黑洞照片」那种海量数据有关的算法问题][Link 9] [几道 BAT 算法面试中经常问的「字符串」问题][BAT]

更多类似的算法题分析，请前往我的个人博客 [https://www.cxyxiaowu.com][https_www.cxyxiaowu.com] 或我的原创公众号「**五分钟学算法**」中进行阅读。

当然，大佬们都说过，**学算法之前起码得了解数据结构呀**！

**你是否当程序员这么多年，还只是能手写出个冒泡排序的代码？**

别怕！

我也将程序员常见常用的那些数据结构都配了大量的图片和动画进行讲解，相信你看了一定能有所收获！

**比如我做了十大经典排序动画，你看着动画应该能理解吧。**

**下文中所有文章的配图动画耗费了我大量的时间和精力，在本文最后部分把这个 动画和算法学习书籍 分享给大家，觉得有用的麻烦点赞关注走一波，谢谢！！！**

## **1. 冒泡排序** ##

## **1.1 算法步骤** ##

*  比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 *  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
 *  针对所有的元素重复以上的步骤，除了最后一个。
 *  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

## **1.2 动画演示** ##

![v2-de77d5632626c95812dc6fb1fa0f2aba\_b.gif][v2-de77d5632626c95812dc6fb1fa0f2aba_b.gif]

## **2. 选择排序** ##

## **2.1 算法步骤** ##

*  首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
 *  再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
 *  重复第二步，直到所有元素均排序完毕。

## **2.2 动画演示** ##

![v2-64fd7db485a8416fc5fa2cbf19410e9d\_b.gif][v2-64fd7db485a8416fc5fa2cbf19410e9d_b.gif]

## **3. 插入排序** ##

## **3.1 算法步骤** ##

*  将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
 *  从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

## **3.2 动画演示** ##

![v2-ffda0249330d775e6fd3488f198c5c43\_b.gif][v2-ffda0249330d775e6fd3488f198c5c43_b.gif]

## **4. 希尔排序** ##

## **4.1 算法步骤** ##

*  选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
 *  按增量序列个数 k，对序列进行 k 趟排序；
 *  每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

## **4.2 动画演示** ##

![v2-4b59f2fb05fb9124f60ab305df6f5f94\_b.gif][v2-4b59f2fb05fb9124f60ab305df6f5f94_b.gif]

## **5. 归并排序** ##

## **5.1 算法步骤** ##

*  申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
 *  设定两个指针，最初位置分别为两个已经排序序列的起始位置；
 *  比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
 *  重复步骤 3 直到某一指针达到序列尾；
 *  将另一序列剩下的所有元素直接复制到合并序列尾。

## **5.2 动画演示** ##

![v2-b478eca84d811b3c3bf952734082c198\_b.gif][v2-b478eca84d811b3c3bf952734082c198_b.gif]

## **6. 快速排序** ##

## **6.1 算法步骤** ##

*  从数列中挑出一个元素，称为 “基准”（pivot）;
 *  重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
 *  递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

## **6.2 动画演示** ##

![v2-ec81c80107fb8acfbf47ec9341b77d0d\_b.gif][v2-ec81c80107fb8acfbf47ec9341b77d0d_b.gif]

## **7. 堆排序** ##

## **7.1 算法步骤** ##

*  创建一个堆 H\[0……n-1\]；
 *  把堆首（最大值）和堆尾互换；
 *  把堆的尺寸缩小 1，并调用 shift\_down(0)，目的是把新的数组顶端数据调整到相应位置；
 *  重复步骤 2，直到堆的尺寸为 1。

## **7.2 动画演示** ##

![v2-acce604ba89b6dcd87efe1aee94b258f\_b.gif][v2-acce604ba89b6dcd87efe1aee94b258f_b.gif]

## **8. 计数排序** ##

## **8.1 算法步骤** ##

*  花O(n)的时间扫描一下整个序列 A，获取最小值 min 和最大值 max
 *  开辟一块新的空间创建新的数组 B，长度为 ( max - min + 1)
 *  数组 B 中 index 的元素记录的值是 A 中某元素出现的次数
 *  最后输出目标整数序列，具体的逻辑是遍历数组 B，输出相应元素以及对应的个数

## **8.2 动画演示** ##

![v2-c2b4f262c8cdca517d2ec199472b1370\_b.gif][v2-c2b4f262c8cdca517d2ec199472b1370_b.gif]

## **9. 桶排序** ##

## **9.1 算法步骤** ##

*  设置固定数量的空桶。
 *  把数据放到对应的桶中。
 *  对每个不为空的桶中数据进行排序。
 *  拼接不为空的桶中数据，得到结果

## **9.2 动画演示** ##

![v2-55bdaa0253026d20564c7da9f8c3dcff\_b.gif][v2-55bdaa0253026d20564c7da9f8c3dcff_b.gif]

## **10. 基数排序** ##

## **10.1 算法步骤** ##

*  将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
 *  从最低位开始，依次进行一次排序
 *  从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列

## **10.2 动画演示** ##

![v2-0f2384641de8078384ce1a987c34ba64\_b.gif][v2-0f2384641de8078384ce1a987c34ba64_b.gif]

为了让文章加载动画更快，录制动画时进行了压缩，有可能会模糊，如果你想获取上述文章的所有超清动画，请在公众号「**五分钟学算法」**内回复 **MP4** 进行获取。

不仅是这些，像上面 栈、队列、堆、二叉树、图等各种结构，我都配了大量的图片和动画进行讲解。你看完肯定有收获！

[看动画轻松理解「 堆 」][Link 10] [冰与火之歌：「时间」与「空间」复杂度][Link 11] [数据结构与算法--2-3-4树][--2-3-4] [详解什么是平衡二叉树（AVL）（修订补充版）][AVL] [动画：什么是散列表？][Link 12]

**我的专栏：**

[和程序员小吴一起学算法][Link 13]

大家一起加油~

## **❤️ 看完三件事：** ##

如果你觉得这篇内容对你挺有启发，我想邀请你帮我三个忙：

1.  **点赞，**让更多的人也能看到这篇内容（**收藏不点赞，都是耍流氓 -\_-**）
2.  **关注我和专栏，**让我们成为长期关系
3.  **关注公众号「五分钟学算法」，**第一时间阅读最新的算法文章，公众号后台回复 1024 送你 50 本 算法编程书籍。

![v2-3af2339a6056d546cf4383d39233e8fa\_b.jpg][v2-3af2339a6056d546cf4383d39233e8fa_b.jpg]

[21_Github_ 6300 star]: https://zhuanlan.zhihu.com/p/53584215
[v2-18e366164812f84a473fea4672c4946d_b.jpg]: https://img-blog.csdnimg.cn/img_convert/bd0854ed68dc20b95df10e8305b35327.png
[v2-a207d4b674ee3e9925b66db15f1f467d_b.jpg]: https://img-blog.csdnimg.cn/img_convert/9c1ac53efaaa2dfb296f1427697b0016.png
[v2-bce42665367e5b6423e6fb30adb6e5f4_b.jpg]: https://img-blog.csdnimg.cn/img_convert/eda512ae2265bbc550e13ed834086cc4.png
[Link 1]: https://link.zhihu.com/?target=https%3A//mp.weixin.qq.com/s%3F__biz%3DMzUyNjQxNjYyMg%3D%3D%26mid%3D2247484505%26idx%3D1%26sn%3D4c1c056dd4852c3b4b1ead51c90a9b2d%26chksm%3Dfa0e6bd8cd79e2ce8188dcdd8843a5d071248906bfb8971c62d513dbd69b816acc191a78e4b2%26scene%3D21%23wechat_redirect
[Link 2]: https://link.zhihu.com/?target=https%3A//mp.weixin.qq.com/s%3F__biz%3DMzUyNjQxNjYyMg%3D%3D%26mid%3D2247484557%26idx%3D1%26sn%3D739d80488fe1169a9c9ca26ecfcdfba6%26chksm%3Dfa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63%26token%3D110841213%26lang%3Dzh_CN%23rd
[LRU]: https://link.zhihu.com/?target=https%3A//mp.weixin.qq.com/s%3F__biz%3DMzUyNjQxNjYyMg%3D%3D%26mid%3D2247484322%26idx%3D1%26sn%3D7a12bcef22dda2c97cffe8ad4d55ea9d%26chksm%3Dfa0e6c23cd79e53514cc85fb0a2bae55ab5965049eabf633ca537c0ecba1309db80119661b05%26token%3D110841213%26lang%3Dzh_CN%23rd
[Link 3]: https://link.zhihu.com/?target=https%3A//mp.weixin.qq.com/s%3F__biz%3DMzUyNjQxNjYyMg%3D%3D%26mid%3D2247484350%26idx%3D1%26sn%3Dfc88aa125f5a5269575b4c4d83774f41%26chksm%3Dfa0e6c3fcd79e5297257a05b8c75898b4059b1193956c702ff5ef3f2d8d46432bb7484bf6428%26token%3D110841213%26lang%3Dzh_CN%23rd
[Link 4]: https://link.zhihu.com/?target=https%3A//mp.weixin.qq.com/s%3F__biz%3DMzUyNjQxNjYyMg%3D%3D%26mid%3D2247484830%26idx%3D1%26sn%3D9d24fc787da4b49b82ac01c7f8de257b%26chksm%3Dfa0e6a1fcd79e309a2e7f3e09ec9913a55f1c077287c907f13528578b7785831a2effb3104e0%26scene%3D21%23wechat_redirect
[Link 5]: https://link.zhihu.com/?target=https%3A//mp.weixin.qq.com/s%3F__biz%3DMzUyNjQxNjYyMg%3D%3D%26mid%3D2247484985%26idx%3D1%26sn%3D93343d355abf36c77a361c9931cbe2d1%26chksm%3Dfa0e69b8cd79e0ae1e6b57665a456da5f421cc92fe6934337f1eb1e18c3fd6a3c1adc8ca88c2%26scene%3D21%23wechat_redirect
[Link 6]: https://link.zhihu.com/?target=https%3A//mp.weixin.qq.com/s%3F__biz%3DMzUyNjQxNjYyMg%3D%3D%26mid%3D2247484977%26idx%3D1%26sn%3Df4a6148480555e3cca83231ac1df8d02%26chksm%3Dfa0e69b0cd79e0a686e31c547fc783eb9663d9fe19cc95ecd524e9f8f7e0d4a168945f8755e5%26scene%3D21%23wechat_redirect
[Link 7]: https://link.zhihu.com/?target=https%3A//mp.weixin.qq.com/s%3F__biz%3DMzUyNjQxNjYyMg%3D%3D%26mid%3D2247484846%26idx%3D2%26sn%3De508da06e9f7a0b3d00db5415d7ce622%26chksm%3Dfa0e6a2fcd79e3397fe8083f9493ae639f47c9448ac2a0026026494d098c47ecc6e08f1f8e28%26scene%3D21%23wechat_redirect
[Link 8]: https://link.zhihu.com/?target=https%3A//mp.weixin.qq.com/s%3F__biz%3DMzUyNjQxNjYyMg%3D%3D%26mid%3D2247485197%26idx%3D1%26sn%3D1bbd40d49adb09875fd324664bd5bc8b%26chksm%3Dfa0e688ccd79e19a36599b53e4a8acf9a725ace3f6df28925075ff25778238471a283f0f8e1f%26token%3D763920087%26lang%3Dzh_CN%23rd
[Link 9]: https://link.zhihu.com/?target=https%3A//mp.weixin.qq.com/s%3F__biz%3DMzUyNjQxNjYyMg%3D%3D%26mid%3D2247485123%26idx%3D1%26sn%3D118f7f665b902b924e949b01d76d7a25%26chksm%3Dfa0e6942cd79e054eaa763aca52efc3d25248abf00b7fcb4620b0bafc04f98230b1672f8fad6%26token%3D763920087%26lang%3Dzh_CN%23rd
[BAT]: https://link.zhihu.com/?target=https%3A//mp.weixin.qq.com/s%3F__biz%3DMzUyNjQxNjYyMg%3D%3D%26mid%3D2247485091%26idx%3D1%26sn%3D1503058d7c1313552f84073b495c5e76%26chksm%3Dfa0e6922cd79e034471194c636e89aa124941a13dabdf4d6197669f51d146f27098b124e5dd8%26token%3D763920087%26lang%3Dzh_CN%23rd
[https_www.cxyxiaowu.com]: https://link.zhihu.com/?target=https%3A//www.cxyxiaowu.com/
[v2-de77d5632626c95812dc6fb1fa0f2aba_b.gif]: https://img-blog.csdnimg.cn/img_convert/4b7e281d4e3f4da881ab5fba03872ed5.gif
[v2-64fd7db485a8416fc5fa2cbf19410e9d_b.gif]: https://img-blog.csdnimg.cn/img_convert/2f68f5868cff82523620d338a13ec493.gif
[v2-ffda0249330d775e6fd3488f198c5c43_b.gif]: https://img-blog.csdnimg.cn/img_convert/539c22a267b053b5ae89e3440eba95e2.gif
[v2-4b59f2fb05fb9124f60ab305df6f5f94_b.gif]: https://img-blog.csdnimg.cn/img_convert/1ed4b8630ff905418ee71f8f54e7d430.gif
[v2-b478eca84d811b3c3bf952734082c198_b.gif]: https://img-blog.csdnimg.cn/img_convert/54d5868b00145e09ce67835c498c5f98.gif
[v2-ec81c80107fb8acfbf47ec9341b77d0d_b.gif]: https://img-blog.csdnimg.cn/img_convert/f4731e24553ae95ecabf8db8bf6782ff.gif
[v2-acce604ba89b6dcd87efe1aee94b258f_b.gif]: https://img-blog.csdnimg.cn/img_convert/0e0fec60ae403b81c22e1acf9603c252.gif
[v2-c2b4f262c8cdca517d2ec199472b1370_b.gif]: https://img-blog.csdnimg.cn/img_convert/3df4267fd7828ba7045a2141bb5341b8.gif
[v2-55bdaa0253026d20564c7da9f8c3dcff_b.gif]: https://img-blog.csdnimg.cn/img_convert/5fce9c5f3b0f2fb8f8668a2945fab517.gif
[v2-0f2384641de8078384ce1a987c34ba64_b.gif]: https://img-blog.csdnimg.cn/img_convert/ce76f59ab00acf0afd7e7d47af97dc99.gif
[Link 10]: https://link.zhihu.com/?target=https%3A//mp.weixin.qq.com/s%3F__biz%3DMzUyNjQxNjYyMg%3D%3D%26mid%3D2247484290%26idx%3D1%26sn%3D971ae3365a8a9d284e427e623d825bba%26chksm%3Dfa0e6c03cd79e5155675799b8dff854fd1f0763f8a0991c401e64a549774522cf64b026cb39f%26token%3D110841213%26lang%3Dzh_CN%23rd
[Link 11]: https://link.zhihu.com/?target=https%3A//mp.weixin.qq.com/s%3F__biz%3DMzUyNjQxNjYyMg%3D%3D%26mid%3D2247484284%26idx%3D1%26sn%3D8c4d26bd5857c93593ac65b8763cd0ef%26chksm%3Dfa0e6cfdcd79e5eb18114c6d1528c1edf304c79fd2837831f58812903b0029a5bb7a59b640ba%26token%3D110841213%26lang%3Dzh_CN%23rd
[--2-3-4]: https://link.zhihu.com/?target=https%3A//mp.weixin.qq.com/s%3F__biz%3DMzUyNjQxNjYyMg%3D%3D%26mid%3D2247484706%26idx%3D1%26sn%3D645713dba123f71a014dcc1204083293%26chksm%3Dfa0e6aa3cd79e3b5b2ebf903a52bd90f6728e9def50da80eb0ee5aa3aa9f6e940c9822217fe2%26token%3D1313026425%26lang%3Dzh_CN%23rd
[AVL]: https://link.zhihu.com/?target=https%3A//mp.weixin.qq.com/s%3F__biz%3DMzUyNjQxNjYyMg%3D%3D%26mid%3D2247484608%26idx%3D1%26sn%3D68b96e6e65a048da54177b6e95b02676%26chksm%3Dfa0e6b41cd79e257daa1f276e0921ed4a060c9caf964e4131f68010ae2a9b8211f56af866fed%26token%3D1313026425%26lang%3Dzh_CN%23rd
[Link 12]: https://link.zhihu.com/?target=https%3A//mp.weixin.qq.com/s%3F__biz%3DMzUyNjQxNjYyMg%3D%3D%26mid%3D2247484447%26idx%3D1%26sn%3D78bc3d7a69616de0676f176b7b47520e%26chksm%3Dfa0e6b9ecd79e288dbaf3817d3b5f7ec0b17c18626f4485e3b5fb62fbc79e89fa8f114857770%26token%3D1313026425%26lang%3Dzh_CN%23rd
[Link 13]: https://zhuanlan.zhihu.com/c_1039097450233057280
[v2-3af2339a6056d546cf4383d39233e8fa_b.jpg]: https://img-blog.csdnimg.cn/img_convert/56f3cc39ccf4db2ab7f0965fca52d436.png