想面试字节跳动，不精通数据结构与算法？我劝你不要白日做梦了

背景

本人基本情况：本硕普通985学渣，现居深圳，Android研发，目前主语言Java，某小公司工作中。去年面试字节跳动，死在了最后一类问题上，补发面经，希望能对大家有所帮助。

由于面试时间已经较为久远，本文就不按照轮次划分了，按照我自己梳理的顺序划分。

有的内容记不清楚了，可能有遗漏；有的内容可能没有问到，但我觉得需要复习，也写出来供大家参考。

所以实际上不算是面经了，算是个经验总结。

面试注意项

个人认为，下面几点是很基本的要求，不算加分项，但做不到绝对是扣分项。

1. 守时：别迟到，最好提前十到五分钟进入面试房间（视频面），摄像头耳麦等提前一天调试好；
2. 耐心：如果面试官有事推迟，保持耐心，不要焦躁；
3. 礼貌：基本素养；
4. 诚实：简历要诚实，问答要诚实，不会的问题不要强答；
5. 保持微笑：即使身处险境，也要保持微笑；
6. 保持谦卑：切勿狂妄。

主要分享下个人一面情况，

由于每个人的情况不同，本人很菜，懂得有限，轻喷轻喷、、、

1.请编程实现单例模式，懒汉和饱汉写法
2.请编程实现Java的生产者-消费者模型
3.HashMap的内部结构？ 内部原理?
4.请简述Android事件传递机制， ACTION_CANCEL事件何时触发？
5.Android的进程间通信，Liunx操作系统的进程间通信。
6.JVM虚拟机内存结构，以及它们的作用。
这个问题也比较基础，JVM的内存结构如下图所示。
7.简述Android的View绘制流程，Android的wrap_content是如何计算的。
8.有一个整形数组，包含正数和负数，然后要求把数组内的所有负数移至正数的左边，且保证相对位置不变，要求时间复杂度为O(n), 空间复杂度为O(1)。例如，{10, -2, 5, 8, -4, 2, -3, 7, 12, -88, -23, 35}变化后是{-2, -4，-3, -88, -23,5, 8 ,10, 2, 7, 12, 35}。
9.数组中存有1-3的三种数字,例如[1,2,3,1,2,2,1,3,3]，将其排序为[1,1,1,2,2,2,3,3,3]，要求时间复杂度，后续将内容变为一个对象，继续排序
10.1~100盏灯，都是亮的，第一次将能被1整除的数的灯按下，变暗，第二次将能被2整除的数的等按下，变亮，第三次将能被3整除的数的等按下，变暗…第100次将能被100整除的数的灯按下，问，最后有多少盏灯是亮的

整个面试过程，其他都还好，最后几道题都没答好，这也跟我平时刷题训练太少，就挂在了算法这类题目上。

看到这里，我想这是许多人的疑问，是啊，为什么大厂都要考算法和数据结构呢？

实际上之所以有很多问题我们不明白不理解，是因为我们所处的角度的问题，在这里如果你站在老板的角度上思考问题一切就简单了。

升职加薪

老板开公司的目的是为了什么？钱啊，数据结构与算法有什么用呢，能为老板省钱啊，能为老板省钱的技术你说重要不重要。同样一个程序，你的运行起来需要10台服务器，另一个人的只需要2台，如果你是老板的话该为谁升职加薪呢？

数据结构与算法就是这样一种能为老板多赚钱(能省钱也就是多赚钱)的技术。

那站在程序员的角度呢？

很多初学者甚至有工作经验的程序员避免学习数据结构与算法，一方面因为其固有的复杂性；另一方面他们觉得数据结构和算法在实际工作中根本就没什么用嘛，我们用一个最简单的游戏来开始本篇的讨论。

有一个猜数的游戏，玩家说出一个数字，主持人会告诉玩家这个数字是大了还是小了，看谁猜的次数最少，最好的办法是什么呢？很显然：

假设抛出的数字是100，主持人告诉你猜大了，那么接下来应该猜50；如果主持人告诉你猜小了，那么接下来应该是75；如果又猜大了，那么接下来应该是62，如果又小了，那么应该是56，Congratulations，恭喜你猜到了，实际上你在用二分查找的策略。

这个简单的示例应该能让你意识到现实生活中算法的重要性，如果你仅仅认为数据结构与算法只在面试时才有用那就大错特错了。

因此，简单总结一下数据结构与算法的重要性：

通过面试，找到心仪的offer，进入大厂

使用数据结构与算法高效解决面临的复杂问题，为老板省钱从而升职加薪。

进入顶尖大厂

许多人会问为什么很多大厂面试第一关就是算法而不是编程语言、框架等等。

现实中公司尤其是拥有大规模用户群的的大厂会面临很多复杂且有挑战的问题，这些问题都是由像hash表、树、图以及各种算法来解决的，比起其它方面，面试官其实更看中候选者是否能运用数据结构与算法来高效解决给定问题。

来自Google、微软、Facebook、Amazon等公司的程序员可以获得更高的薪水，为什么？在这些公司中编写代码仅仅占据了大概20%-30%的时间，那么剩下的时间都在干嘛呢？剩下的时间是在寻找或设计更高效的算法以节省公司的资源(主要是服务器)，为什么这些人主要在做这件事呢？因为这些公司拥有全世界最有的用户，Facebook、YouTube、Twitter、 Instagram、 GoogleMaps等其用户都有数十亿之多，这背后需要的计算资源可想而知，那么这些资源可都是用钱堆出来的，你用高效的算法为公司节省哪怕0.1%的计算资源，换算成钱的话可能都有数亿美金了，这就是算法的重要之处。

假设你在Facebook工作并且想出来一个很牛的算法，使得计算速度由O(N^{2)提升到了O(NLogN)，假设这里的问题规模N为一亿(考虑到Facebook的用户规模这已经很保守了)，那么O(NLogN)大概为8亿，而O(N}2)是100000000亿，那么你的算法从效率上提升了大概一千万倍，想一想这种效率上的提升能为公司节约多少成本。

现在你应该知道为什么世界上顶尖公司都喜欢雇佣那些聪明家伙了吧，就是因为他们在代码效率的一点提升就能为公司节约极大的成本。

我们的现实世界充满了各种富有挑战的问题，有些问题甚至依然没有高效的解法，深度理解这些问题，哪怕你的解法能提升一点点效率，有了这样的能力想进大厂我想不会有哪个老板会傻到拒绝你吧。