面试记录
内推：
2017-03-02 14:23:55
阿里中间件一面
阿里中间件给我打电话，聊了半个小时。他说我基础还行，但是我们是搞分布式的，包括hadoop、MapReduce，你对这方面没有经验，我们的领域可能不匹配，招一个研究生希望领域能够匹配。
这个人说他是第一次面试别人。主要问了项目，两个编程题。一个：如何判断一个链表有回路（快慢指针）。另外一个：后续遍历二叉树，递归性能要求高怎么办（用栈改成非递归）
主要是JAVA GC没回答上来，分布式不懂。
说到做服务器，他问我你有没有测试过你做的服务器的并发。说做过服务器，应该都会问吧。
2017-03-22 20:58:27
腾讯MIG一面：
刚接到腾讯的电话，那个姑娘问的基本都是Android的东西，RelativeLayout和LinearLayout性能比较，Android中用SparseArray和ArrayMap代替HashMap，HashMap原理（上个问题没回答上来，只能问这个），控件绘制过程，handler原理，有没有遇到过内存泄漏，Android中线程间通信，线程同步的方法，网络图片缓存、区分热点图片？，Asynctask优缺点，创建自定义线程池的参数，项目中用到哪些设计模式，listview原理，有没有遇到过ANR，touch事件分发机制（可能回答太差就挂电话了）。
她问的好多都是性能优化方面的，我项目中没遇到过，回答的她不满意。不过这个姑娘好像一开始就不开心，总感觉她全程黑脸。。。
腾讯SNG一面：
刚刚腾讯又来了个电话，这次是个男的。他是SNG的，但是我投的是MIG，扔简历不至于这么快吧。他让我说说项目流程，问了我一些Android UI方面的问题，UI优化，进程间传大文件的方式，以及JNI。数组和链表的适用场景，查找最快的数据结构。他特别想问我C++的问题，问我C++和JAVA的区别，C++的析构函数为什么要加virtual，malloc和new的区别（我只能回答malloc），我只能说C++不太了解，只用过C和JAVA。最后我问他怎么样，他说Android和数据结构还行，C++欠缺。
校招实习：
2017-4-16 14:00:25
腾讯校招实习一面：
下午两点到西安悦豪酒店，5楼报告厅前，扫码签到。签完到没几分钟就收到短信去1402房间面试。进去就有一个人在做试卷。面试官给了我一张试卷，做正面两题。做完后，面试官在面试之前做题的那个人，应该是本科生，所以让我再写背面的题。因为他算法题没写出来，请问哈希表的原理也不会。最后面试官问他想去哪工作，他只想去北京，所以可能因为北京要的人少，并且他水平也不行，所以就问了不到二十分钟就结束了。面试官还是很好的，这个人题目没写出来，面试官还引导他想思路。
我写的四题都很简单。
一；将M进制的字符串转换成N进制的字符串输出，大小在42亿以内。
二：一个数组a[N]，0 < 范围 < N，里面有两个重复的值，找出这个值。
三：写出两个时间复杂度不一样的算法。
四：给出一个二进制数X，用两种方法求出该数值里包含1的数量。
解题思路：
一：
先将M进制的字符串用 current + total * M;方法求出其值放在int变量里，然后用current = total%N; total = total/N;把值分解到字符串里。
二：
用哈希表思想，创建N长度的数组，一一对应a数组里的值，遍历将对应位置标记1，遇到1则说明是重复值。
三：
写了冒泡和快排。冒泡：O(n) O(n^2) O(n^2) 快排：O(NlogN) O(NlogN) O(NlogN)
四：
方法一：同题一，用用current = total%N; total = total/N;判断current为1，则sum++;但是方法二没想出来，不过没让我写了，因为前面一个人面完了。
第一题，我把StringBuffer的append()方法写错了，写成了add()。算法题总体上应该没问题，他没说什么，只是让我把没写完的方法一，写完。
下面让我自我介绍。我说了我的学校以及本科和研究生分别做了两个比较完整的项目，把两个项目描述了一遍。
他问我研究生的项目中移植的难点。我大概说了两个部分，一个交叉编译的问题，一个是用strace解决缺包等问题。他问只是通过strace吗，我说还有看日志，但是我忘了说还有看源码。然后他问应用层有什么经验，我说了打印项目的app部分，主要用了ListView，然后提到了RecycleView。
然后他问了我ListView和RecycleView的区别。我提到里面的缓存不一样，以及RecycleView的功能更强大。他问到缓存不是增大了内存使用，为什么要缓存。我就举例说，50个item，每页只显示十几个，不缓存这50个item都要创建对象，而缓存则只需要十几个。
他问你还看过哪些类的源码。我说看过AsyncTask，说了AsyncTask其实就是包装了Handler和线程池，Handler用来传输过程中以及结果数据，线程池用来执行任务。以及3.0及之后的AsyncTask默认是串行的，可以改成并行的线程池。但是这个线程池大小和CPU有关系，也就5个左右的保有线程。所以后来我使用自己的线程池来管理我的任务。比如一个打印任务就需要执行命令行的主线程和标准输出和错误输出监听三个线程。
他问你说你一个任务有三个线程，那么肯定设计线程同步。我说，是的。主线程需要等待两个输出线程结束，得到返回的状态。我用自定义的Object锁对象，在里面创建finish变量。每个线程一个锁对象，线程结束就把finish置为true，如果是true，主线程就不等待了。否则，主线程用wait等待该线程，当然这是在所对象的synchronize里操作的。标准输出一个等待结束，再判断错误输出是否finish，需要就等带错误输出。他说不用说太细，这个问题就结束了。
他问你用到了哪些设计模式。这个我这两天正有准备。我说了ListView的适配器模式，使用线程池时使用单例模式，Handler是观察者模式，Binder是代理模式。他着重问适配器模式的优缺点。我这个没考虑到，简要回答了兼容性，扩展性好。我当时没说解耦这个概念，他后来提到了。之后他又补充了问我抽象工厂模式，以及它涉及哪些类。我不太清楚，回答了抽象工厂，实例化的工厂，以及实例化的产品。我说还有消费者，他说没有这个概念。结束后，我查了一下，应该是缺抽象产品（产品接口）。他又问接口的作用。我回答接口就是制定一个规范，它把实例化的东西抽象。实例化的工厂需要按照这个规范来制造，否则制造的产品不能用。
他看我本科项目中涉及的网络协议，我说用到了HTTP，JSON。问我你说说你对网络协议的了解。我说HTTP是TCP/IP之上的协议，以及HTTP里传JSON。他问我TCP/IP，HTTP，SOCKET的关系。我的大概意思是SOCKET通常指TCP SOCKET，它用来发送TCP/IP协议的数据。当然还有UDP的SOCKET，但是TCP比UDP要可靠，因为不是发出去就不管了，还有重发以及发送失败的反馈。因为我忘了TCP/IP在四层协议中的层级名称，我就说HTTP是应用层，下层是TCP/IP。然后说了HTTP的组成，请求头、/r/n分割，请求体。我这里忘了说TCP的三次握手和四次分手，不知道他会不会以为我不了解这些知识。
他问我对Android历史版本的了解程度，Android 5.0 和 6.0 的新特性了解。我对这边忘了准备了。只勉强回答了5.0 默认是 ART虚拟机，应用可以有备份功能。6.0有多窗口、分屏功能但是默认没有开启，以及权限管理更严格了，可以设置关闭相应权限。后来查了一下，忘了说最重要的了：5.0开始改用了全新的Material Design设计风格了，这边应该减分。
他问我，如果做一个应用对内存要求高，如何做。我想了想回答：
可以用弱引用之类对ListView的图片等数据进行优化，让它们及时释放。
以及后台Activity及时清理，只保留前台Activity。
有些大数据可以存在硬盘里，不用放在内存中。
少用第三方库，因为第三方库的很多功能用不到，但这些功能相关的对象还在内存里造成浪费。
我憋了半天，就说了这些手段。这里我答的应该不太行。
他问我对JAVA GC的了解程度。我说学习的是JVM里的情况，因为davilk资料少一些。回答了分代的情况，新生代的复制算法以及老年代清除，我这里说错了，老年代一般是标记-整理，而且我这里忘记说如何判断对象可以被回收，可达性分析。以及内存里的分区情况，堆、栈、程序计数器，GC主要回收的是堆里的空间。这个问题整体说的不太行。
他问我对Service的生命周期的了解程度。我说了Bind和非Bind两种，Bind的和Activity的生命周期绑定，而非Bind的则会在后台，知道app的进程被杀死。我这边回答的可能太草率的。他问如何创建非Bind的Service，我说intent，他说再详细一点，我说创建intent然后StartService。他貌似满意了？
他问我填的期望的工作城市，我说深圳，上海，北京都可以。我说我希望有个好的发展，在哪没关系。之前那个小伙咬定了要去北京，但是北京需求少，他答的也差，所以他基本没戏了。
他要了一份纸质的简历，以及把之前的一张试卷签名留下了。而且他全程会用一张纸记录我回答上来的知识点。他问我有什么问题吗，我说您觉得我怎么样。我感觉他本来想说我的缺点的，但是他又没说了。他说我各方都还行，挺好的，我们这几天会商讨后给通知。
整个面试有一个半小时吧，做题做了40分钟，面了大概40分钟。面试回来状态也没有变，是初试状态。
算法-求二进制数中1的个数
http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html
普通法：移位计算
静态表-4bit：预先计算4bit里每种情况的1的个数，然后count += table[n &0xf] ; n >>=4 ;
其他方法太麻烦了，不看了。
2017-4-17 14:50:08
腾讯校招二面
自我介绍完，两个题。
第一题：去除字符串的空格，只能用char *，不能用其他的。时间复杂度O(n)
我实现的算法复杂度高，这不是关键。关键是我涂涂改改，非常混乱。面试官一行一行的看，说我搞得这么复杂。还有几行看不清楚，我重新抄了一遍给他看。然后向他解释我的代码，解释了半天。
第二题：博弈题，50个苹果，两个人，每次只能取1或者2个，最后一个取的胜利。
这题也是非常简单，但是我倒推枚举必胜情况的时候，算到剩余7个苹果应该取1个数，算错了。导致我公式怎么带入都不对。面试官中途提示我说，你就看这10个数的规律，但是我找不出来，因为我一个数算错了。面试官还说我听不进别人的意见。以及思维定式，为什么想着取余。说这个话估计是因为他不知道我算错了，其实我在找这几个数的规律，但是没办法，数值错了当然看不出来。磨了半天，非要我给一个结果。
最后面试官给了两个建议，一，思维逻辑不清晰，简单的事情搞得很复杂。二，思维定式，听不进别人的意见。
我觉得第一个建议比较靠谱，确实逻辑比较混乱。第二个是因为我把数算错了，我就是按照他说的做，只是算数不过关。
两题都没出来，中间浪费了很多时间。结束。正常流程应该会做4题左右的，但是两题就把时间用完了。
这次面试基本可以说是，基础没搞好。平时对算法、数据结构练习的不够。
解：
第一题：用一个数记录空格数，一遇到非空格，就向前移动记录的数量。
第二题：n为剩余苹果数量，先手取n%3
取石子游戏之巴什博弈
http://blog.csdn.net/xuzengqiang/article/details/7763635
2017-5-17 16:00:00
JLRC西安子公司
与YM师父杨总聊了聊。
他们是JLRC的西安子公司，现在刚组建。
今年准备做两个点。
- 给Oracle、MySQL等数据库做统一的接入平台，让上层业务忽略数据库之间的差异，抽象成一个大数据库提供服务。
- 做一个分布式调度平台。
杨总是YM师父，他说他对YM之前的实习非常满意，觉得他逻辑清晰、理解力强等等。由于我们是YM推荐过来的，所以他对我们的基础能力非常放心。因此他没有详细的问我们技术细节。
他就大概问我几个问题。
1 对JAVA哪边熟悉，说一说。
这个问题有点抽象，我大概说线程池、同步、对接口有一定理解。
（我这边说的不太好，因为我都没有详细说，而且面对这个问题，我确实一时想不清楚怎么回答。不知道对哪方面熟悉。）
2 数据结构方面的了解。
我说快排、冒泡排序，知道快排比较优秀，冒泡时间复杂度大，O(n^2)。哈希和树也有了解。哈希查询快，O(1)，无序，树适合有序数据的存储。了解二分查找。
3 他问二分查找对于边界情况的界定，容易陷入死循环。
我说了中间指针位置计算(j-i)/2 + i，可以防止(i+j)/2数据爆掉。
（
我可能没有说到点上。，待会查一下。
二分查找(Binary Search) 常见问题解决方法总结
http://blog.csdn.net/daniel_ustc/article/details/17307937
重复元素的解决方案
）
4 你用过github，有过组织项目的经验。
是的，之前几个人通过github管理代码，把代码提交到github上面。
（这里说的还不够详细，我应该说如何利用github进行项目管理，用issue管理任务，以及利用git push/git patch提交代码，用不同的branch开发新功能。每周还定期讨论进展。）
他之后说要把你们的信息提交给他上面的总监，希望我们能把数据结构看一下，虽然总监不会问很多技术，但是也会问一些。
- 排序算法中快排、堆排序、归并排序比较重要，尤其是堆排序，用的非常多。
- 哈希和树很重要，尤其是B树、B+树。（我觉得红黑树也得看看）
- 图也是一种树，图其中的算法。（我觉得树是一种图吧，树是无环路的图）
- 其他的基础：队列、栈，以及二分查找等
之后他问ZXP几个问题。
1 你对Tomcat有了解，说一说Tomcat的工作原理。
2 对JVM的了解。这边ZXP说的比较乱，条理有问题，这个我也要整理一下。
3 new一个String对象需要多少内存。这个问题有点困难，他没回答上来。
（
http://matt33.com/2016/05/07/java-object-memory/
每个String对象都会使用40字节：
16字节表示对象，三个int实例变量各需4个字节，加上数组引用的8个字节和4个填充字节
http://wwwiteye.iteye.com/blog/1985980
那么一个空 String 所占空间为：
8(对象开销) + 12字节(3个int) + 4(char[]引用) + 24(搞java char[]:头8+length 4+ value 10 + padding 2) = 48
<32位机> 2*N + 40 + padding
https://github.com/Piasy/notes/blob/master/Android-Java/JavaObjectMemoryUsage.md
空String对象占用内存：
8(header) + 3*4(上述三个int域) + 4(char数组引用) + 12(空char数组header) + 4(char数组padding) = 40字节
）
2017-9-6 17:39:08
小米内推运维开发一面
开头问我拿到了几个offer，我说我8月底刚开始投，还没拿到offer。
他说他们是运维开发，愿不愿意做。我说有开发的话，可以。他说有一部分开发。我其实觉得不是很好，没后台开发好。
自我介绍。
说我简历上写到对Linux比较熟悉。
问我进程和线程的区别。我说进程和线程的调度粒度不一样。线程切换资源消耗少，比如文件描述符（同一个进程里的）线程之间是共享的。进程切换的开销更大，比如文件描述符都是单独的。进程适合无关程序的执行，线程适合相关程序的执行，比如服务器开启线程接收客户端的请求。
问我Linux的启动过程。我说从硬盘读取主引导记录，然后进入bootloader，然后加载内核，然后启动1号进程，之后每个进程都是1号进程fork出来的。
问我主引导记录怎么读，我说，在硬盘的前512个字节。由于以前的规定512个字节太少，所有通过引导记录转到BootLoader里面加载系统。
问我僵尸进程是什么回事。我说僵尸进程是父进程在结束的时候没有wait子进程。父进程先退出了，导致子进程的资源无法回收，造成资源浪费。在Linux里面，僵尸进程会被1号进程回收。我说我之前遇到个问题就是僵尸进程没有被回收，但是后来没解决。他说是不是父进程还在，我想了想觉得有道理，我说后来我重启了，没有浮现，就没解决了。
他问我僵尸进程怎么解决，我说可以让1号进程回收，或者重启。
让我说说觉得最有深度的项目。我说了打印机项目，主要突出，用strace以及cups日志和cups源码来定位和解决问题。觉得这部分很有难度。举了个例子，说解决usb不能打印，通过strace和源码，发现cups是调用libusb库来读写usb设备。通过strace发现usb设备的位置，Archlinux和Android上的usb设备位置不同，所以我重新编译了libusb库，然后编译cups，解决了问题。
让我说说绿盟里做了什么。我说了绿盟日志处理的流程。它问我哪部分是我做的，我说日志分析部分，用正则表达式解析日志。他说是不是python写的，我说是java写的，java里使用Grok库。
他看我问我正则表达式，问的比较简单。如何匹配ip，匹配行首，匹配多次。IP匹配我说一种可以简单的匹配，用/d+./d+./d+./d+，还有一种严谨匹配，数字匹配部分分类匹配，一位数、两位数、三维数分别匹配（防止超过255）。
问我用过grep，我说我用grep来验证我表达式写的对不对。
他说你正好做过日志，问我如何读取nginx的日志，要求实时读取、文件大了会自动分割，还有两个要求忘了。我说可以通过tail -f来读取日志文件，就能自动读取最新添加的数据。他说不用tail -f我如何能解决文件大了被分割的问题（文件被重命名）。后来讨论了很长时间，让我给个多线程解决方案。最后我说一个线程读，一个线程检测文件变化。他问我如何监测文件变化。我说Linux内核有个inotify机制检测文件改变。他中间还问我有没有考虑内存占用等性能问题，我说没考虑过。我不是很明白他的意思。
然后让我说说Hash表。我说Hash表用一个哈希函数来决定文件存储位置，比如可用把0~100大小的数放在0~9大小的数组里。最简单的函数就是取模。然后回出现冲突，可用多个hash函数重新hash，找空位，或者用链表把冲突的数据链在后面，这是两个常用的冲突解决方法。他问我Hash表的作用是什么，我说我认为主要有两个，一个是为了读取更快，无冲突的情况一次hash就能找到，另一个是把大数据存储到小的空间。主要是为了读取更快。他问我确定Hash表是为了读取更快，我说是的，这是他的一个主要目的。他没说什么。
问我知不知道B+树。我正好之前看过。我说B+树就是一个多叉树，树的非叶子节点存放的是索引，叶子节点存放的是数据。然后存放数据的叶子节点之间还有个链表相互连接。我举了个例子，数据库用B+树，就是由于B+树是多叉树，能节约查找次数，然后叶子节点之间的链表为了方便读取一个数据周围的数据，比如查找1，能够方便的读到0和2。
问题结束，问他情况，他说要回去讨论下。
2017-9-9 09:34:37
小米内推运维开发二面
他首先介绍了运维的工作问我愿不愿意干，我说有开发的话可以。
问他什么部门，他是小米的运维部。我感觉有点奇怪，不在某个产品线里面吗。
让我说Linux内核模块做过什么。我说了Linux内核审计模块项目。
问我的内核模块程序如何输出数据， 我是用printk输出到内核日志，以及写了一个用户态程序，通过自定义的系统调用和内核模块通信。
问我内核模块里面怎么分配空间。我不是很了解，就说了kmalloc、zmalloc。
问我内核空间里栈结构，我说不了解。
问我虚拟内存有哪些。我不是很清楚这个问的意思，我就说了可以dd一个swap文件，以及创建swap分区。他也没说什么。
问我系统调用和中断的区别。我回答，在老版本内核里面，貌似2.6的时候，系统调用是用软中断实现的。在后来，系统调用使用寄存器，置标记实现。
问我traceroute命令有没有用过。我说用过，它用来查找到达目标地址中间经历的路由。
问我traceroute的原理，我说它是发送一个协议和ping一样（icmp），我没说上来。其实这边我少说了和ping的区别，TTL跳数不一样。
问我网络学的怎么样。我说学习过。他问我socket服务端怎么编程的，有3个主要函数。我说，首先创建socket，然后bind端口，设置listen监听模式，最后通过accept就能等待客户端连接。
问我知不知道CAS，我说知道，这个是先比较后设值，实际使用的是一个CPU指令（CMPXCHG）。指令我记不得了，没说出来。因为这个CPU指令是原子的，所以CAS操作不会被打断。他说好。
问我线程是不是有独立的内存空间。我说是的，栈是独立的，堆的共有的。
问我JAVA是不是学了很多，我说是的，花的时间最多的就是在JAVA上。
问我JVM学了什么。我说学了JAVA运行时的内存分配，分为5个区域。JAVA是自动释放，和C语言malloc free不一样。所以需要GC机制。GC主要的就是在方法区和堆。堆里面根据对象的存活特性不一样分为了新生代和老年代。针对新生代的GC算法是标记-复制算法。老年代通常是标记-清理算法。根据这些算法，产生了一些垃圾收集器。线性、并行、CMS和G1。
问我CMS和G1的区别。我说G1没有区分老年代、新生代。它把空间划分成每一小块，里面有新生代和老年代。GC的粒度更小，停顿更短。
问我什么时候会发生young gc。我说新生代空间满了，存不下时。或者新生代里的对象存活时间太长了，会被移动到老年代。以及手动调用gc()函数，会通知系统尽快触发GC。
问我JAVA里面哪个数据结构用到了红黑树。我说HashMap在新版本里面，把链表改成了红黑树。
问我一个问题。数字1到n，统计里面有几个1，我说遍历，然后每个数字右移，看每个位的值是不是一。
问我一个问题。如何把数字的最后一位二进制位反转。我说按位与判断，然后取反。
问我字符串排序通常有哪些方式。我说可以按照ascii码排序，也可以按照长度排序。
问我字符串查找有哪些方法。我说只知道一个kmp算法。
问我设计模式知道哪些。我说了代理模式，RPC的时候使用代理模式，客户端实际操作的是代理对象。还有观察者模式，工厂模式。
问我编译原理怎么样，我说了解过。他问我词法分析有哪些方法，我说这个不太了解。
最后我说我好奇您这边的工作内容，他详细介绍了一下，有运维的部分，也有开发，包括k8s平台的优化。为业务服务的，根据需求改动。
2017-09-17 14:55:19
百度校招软件开发一面
下面三点面试。在学校门口打了半天车，快车、出租都没有。骑了个ofo过去，十五分钟。
到面试官房间先上了个厕所。
自我介绍完直接做题。
1 两个链表，可能会有公共节点，如何查找。说思路。
我刚开始想复杂了，以为和最长公共子串一样，说了个动态规划思路。
他说这样可以做，但是有没有更简单的方法。
我想了个散列表方法，把第一个链表遍历一遍，把节点放入哈希表，然后遍历第二个链表，依次查找哈希表里有 没有当前元素，有则是公共节点。
他说能不能不借助额外的数据结构。
我最后想出来了，由于链表长度可能不一样，所以先把两个链表的长度遍历出来。然后把较长的链表先遍历多出的元素个数，然后两个链表同时遍历，知道遇到相同的节点或者遍历完。
我之前以为链表合并之后可能会再分叉，是我想多了。
2 一个N阶台阶，每次可以走1或者2步，请问有多少种走法。写出来。
动态规划，dp[0]=1;dp[1]=1;dp[i]=dp[i-1]+dp[i-2];循环算出最后的数量。这题写出来了。
3 二十五匹马，只有5个跑道，没有计时器，最少几次比出前三名。
笑了，这题昨天实验室他们问过，我们之前讨论过。我表演了一番。
解法是，先把25匹马分5组，跑完。得到每组的第一名，再跑一次，得到全局第一。然后这次比赛的2，3名和第二名所在组的第二名，再跑一次得到全局二三。最少需要7次。
4 之前说的台阶题，如果可以回退一步，有且仅有一次回退，则有多少种走法。
搞了半天毫无思路。。。。面试官说下一题
5 有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为 k。当然，我们希望得到的小段越长越好，你需要计算能够得到的小段木头的最大长度。
样例：有3根木头[232, 124, 456],k=7, 最大长度为114.
直接懵了。。。。搞了半天也是没思路，他让我可以先说思路，我就说暴力遍历。过会他说算了。
http://www.lintcode.com/zh-cn/problem/wood-cut/
6 问我之前笔试的题，我说记得买书和外星人。还好他问了一个买书的题。
正好这题我之前写的差不多，AC了一部分。然后我跟他说了我之前做题动态规划的思路。并且说了之前没考虑到某类书可能没买的情况。
有魔法类和恐怖类两种书籍，每本书都有一定的价值，给定金额，求买到的最大价值。每类书至少要买一本。
他说可以。
他问我SQL语句会不会写，我说不会。。。。面试官就算了。
最后他问我JAVA的HashMap如何解决冲突的。
我说HashMap是用数组和链表，在JAVA8中，链表改成了红黑树。在HashMap元素数量达到16个的时候，就会改成红黑树。
他说是全部元素数量还是每个链表的元素数量，我说是全部元素。（后来查了，我说错了，是单个链表的元素个数达到8个）
他问我有什么想问的，我问他在什么组。
他说在AI助手，他是做JAVA的。
我问他，他说有通知的话最迟下周二，是二面的最后一天。
45分钟。
2017-09-18 9:05:07
百度校招软件开发二面
昨天一面，今天二面。骑ofo到酒店，本来时间很充足，结果排队签到等了半天，迟了会。
二面没问多少算法，他对我的项目涉及Linux内核比较感兴趣。虽然很多没回答上来，但是比全出算法题要好。
自我介绍完，他说我对Linux比较熟悉，问我平时用什么系统。我说ubuntu。
他问我ubuntu用什么命令查看已安装的软件包。
我这个其实记不清了，说了apt-get list。
他问我这个是列出所有软件包还是已安装的软件。
我说已安装的。
他问我awk会不会。
我说awk没怎么用，平时用grep和sed比较多。比如用sed取出run包里的压缩数据部分。
他问我知不知道实习公司的项目业务流程。
我说我去的比较迟了，他们框架已经做好了。我就做了业务部分。写正则表达式把日志的字段解析出来。然后整体描述了一下streamsets控制数据流把数据从udp读取，通过kafka传送到解析节点，就是我做的部分，然后再发送到存储节点的hive里。
他问我知不知道kafka怎么发送数据的。
我说生产者发送数据，由消费者接收。
他说这些部分你都没做，只是解析的数据。
我说是的。他就没再问了。
他就让我写个匹配邮箱的正则表达式。
我写的起始不完全对，他提示我@前面可能有.号。以及[a-z1-9]要不要加|分隔号，我说不用。他其他没说什么了。
他问我.*什么意思，我说0到多次匹配，+是1到多次。
我后来看了一下，完善的邮箱表达式还挺复杂的，要保证不能有连续两个点号。另外这边我没表现好。正则表达式有很多规范，grep里就提供了三种，-e -p -b 每种都有功能区别。以及.*再加上?问好是非贪婪匹配。这些我都没表现出来。
他问我一个问题，如何查找目录下的所有文件里的关键字。
我说我经常用find和grep组合来查找文件里的关键字。
find / -type f | xargs grep "关键字" 2> /dev/null
find把目录里的每个文件名输出，xargs把文件名一个一个依次作为grep的参数，传给grep，grep则查找文件里的关键字。但是有个问题，grep读取文件夹的时候会报错，因为文件夹是没有数据的，所以会出现很多错误提示，导致我看不清结果。因此使用2>把错误输出重定向到/dev/null，只显示查找结果。
他问我知不知道LRU。
我想了一会，发现是最近未使用算法。
他问我怎么实现，我说可以用队列，要用修改一下的队列。
他问我如果用链表怎么实现，他让我写一下。
我就写了一下，主要是头插入，尾删除。获取的时候遍历，删除，再从头添加。
改了几次后，他表示可以。
他问我知不知道红黑树。
我说知道特性。红黑树是一个二叉树，他是非严格平衡的，因此他和平衡二叉树比，操作代价要小。因此内核里的进程调度就是把进程放在红黑树里，因为红黑树是有序的，想要获得下一个调度的进程，直接把进程放在最左边的节点就可以了，非常高效。红黑树非常适合内存场景，如果放在硬盘里，不合适。硬盘适合多叉树，因为高度低。
他问你说内存存储，那红黑树适不适合磁盘存储。
我说不合适，磁盘存储红黑树因为是二叉的，高度高，应该用多叉树，比如B+树，它的高度低，磁盘的读取消耗低。
这边我其实没说到底，磁盘有局部效应，如果数据分布较远，那么磁盘转动时间消耗特别大，而局部数据能够一次读取，从而大大减少读取时间。多叉树降低高度，增加局部数据的数据量，非常适合磁盘存储。
他问我知不知道红黑树如何保持平衡。
我蒙了，只好说红黑树有5个规则，保持这些规则就能保持平衡。好像红的节点子节点是黑节点。我说我这边记不清了。他没问了。
他说我对Linux内核比较了解，问我内核是怎么启动的。
我一听到问题就醉了，之前小米问过我，我后来看了觉得有点多，就没仔细看。就说了从BootLoader启动内核，内核会进行实模式到保护模式的转换。
他问之后呢。
我说记不清了。。。。
他问我Linux内核和操作系统是什么关系。
我说操作系统像汽车框架，比如GNU，内核是发动机，他们组合在一起形成一个操作系统。用户看到的时候操作系统，实际核心的东西，包括文件系统、进程调度在内核。
他问我linux系统能不能换内核。
我说可以。
他说是要重启才能替换吧？
我说是的。grub会引导进新的内核。
他问我项目跟内核有什么关系。
我说这个是一个移植项目，我们想让Android上运行桌面Linux上的程序，关键是他们都是Linux内核，保证系统调用兼容。我会用strace监测程序的系统调用，然后结合日志，CUPS源码排错。我把debug过程说了一遍，如何发现和解决usb接口不能打印的问题。
他问用户态程序如何和内核态交互。
我说通过系统调用。
这边说的有点少了，应该吧copy_to_user等也给说了。
他问我用户态进入内核态，用户态是不是就在等待。
我说是的，直到内核态执行完返回。
他问我内核态有没有上下文切换。
我说有。用户态进程切换，它的空间会改变，但是内核态公用一个空间。内核态每个进程肯定有自己需要的数据，task_struct之类的。
我这边不是很清楚，所以没说出来有哪些上下文。
他问我内核态里有没有线程。
我说有，内核线程，但是使用时要注意，不能滥用资源。
他问我线程之间如何协作。
我说可以用join()，wait()等。
他说想要线程执行一段之后，可能等待另一个线程的一个任务完成，不是完全等待。
我说可以用互斥锁。pthread mutex
他说互斥锁不能达到他的目的，他要能通信，资源有没有就绪（不是原话，好像是这个意思）。
我说可以用信号量，看资源有没有就绪。还可以用管道，一个读，一个写，也可以通信。
他说好。
他问我内核里面有没有锁。
我说有的，有自旋锁，互斥锁，内存屏障。
他问我什么是内存屏障。
我说我这边没有仔细了解，大概知道内存屏障是多CPU之间保障同步操作的东西。
他问我用户态有没有内存屏障。
我说没有，这是多CPU之间的操作，用户态不用关心。
后来查了，JVM里用到内存屏障。
最后，他说我没什么问题了，你有什么问题。
我就问了他们有几面，什么时候结束。
他们有三面技术面试。
2017-09-21 08:55:12
百度校招软件开发三面
三面昨天晚上才通知我，他们前两天都通知了。今天是百度来西安的最后一天了，早晨9点面试，ofo直接到。
依旧自我介绍，瞎说一通。本科通过比赛接触编程，研究生开始学习Linux系统。
看我对Linux了解，问我平时用什么命令。
我说find、grep。
问我查看Linux进程用什么命令。
回答ps。
看我写了epoll项目，问我epoll和select的区别。
回答 1 select只支持1024个描述符，epoll不限。2 select速度慢，因为内部组织结构不好。epoll用红黑树。 3 epoll支持水平触发，边缘触发。select是水平触发。
我这里丢掉了 select需要每次像内核传递文件描述符集合，而epoll不用。
问我select为什么慢。
回答：因为select使用描述集合，在poll()调用里只挂载了当前进程编号，每次监听事件就绪时唤醒进程都要遍历一遍描述集合，找到相应的描述符。而epoll在poll()调用里不仅挂载了当前进程编号，还有描述符信息。所以epoll在事件就绪时能很快的从红黑树里找到就绪的描述符。
一个题：链表奇、偶元素交换，不能修改元素值，只能修改指针。
刚开始写了一个，题理解错了，题是没有head空节点的，而我以为有。所以重新改了一下。
他看程序，一行一行执行，在纸上画。最后有个变量赋值错了，修改后正确了。这题过。
一个题：[0,1000万]范围的数字，值不重复，数量若干，如何最快排序。
我刚开始说了切割文件。他说不要跳这么快，从头说。我说看这么多数字能不能存到内存，可以的话直接在内存排序，不能则切割文件，在外部用归并，或者堆。
他说你这复杂度是多少。
我说nlogn
他说能不能O(n)
我说排序最快就nlogn
他提示可以不考虑内存占用
我思考了一会，终于说出来，用一个长度为1000万的数组，遍历待排序元素，把扫描到的值赋1。
他说你这个时间复杂度是多少。
我说是O(n)。
他问我你这个内存占用多少。
我算了一下，1000万，一个int要4byte，一共40G。
他说你确定40G。
我：是的。
他演算给我看，是40M。我才发现我算错了。
他问空间能不能更小。
我说可以用一个bit位表示一个数，这样只要1000万个bit，空间缩小了32倍，只要1.25M。
一个题：16个学校，每个学校有红、蓝两只队伍，共32个队伍。每只队伍只和学校外面的队伍比赛，且都只比一场。某一时刻，某个学校的红队发现，除了自己队伍，其他队伍的比赛场次都不相同。求该学校蓝队的比赛场次。
看了很久，在他提示下，只能看出，其他队伍，每个队伍的比赛数分别是0~30。最后没做出来。
他问我项目有有没有做一些系统提升的地方。
我愣了，在思考。
他说有什么改进。
我说了三个线程改成两个线程的，一个改进。
他说还有什么，有什么亮眼的地方。
我憋了半天，说Android APP会经常被杀死，所以有一个保活问题。我把服务和界面放在两个进程里，这样用户只会杀死界面，服务进程不会被杀死。
他问我你觉得你有什么优势，有什么缺点。
我说我的优势就是学习能力强，举了打印机项目的例子。我的缺点是专业领域学习还不够。
他问你现在还想提高什么，
我说除了专业领域知识，我现在还想深入学习系统。因为系统是上层软件的基础，而且系统里面有很多设计模式可以借鉴。比如Android里的消息通信系统（我想说的是handler）就和Linux内核里的消息系统类似。
他问你以后的发展。
我说我喜欢编程，注重技术。可能的话，以后带领别人做项目。
他问你想去什么样的公司。
我说我想去互联网公司，因为互联网公司的技术新。我看重公司的平台，去一个小公司可能会成为骨干，但是看不到别人是怎么解决一个问题的。我想大公司能见识的更多，能看到别人的解决方案，从中学习。（大致意思）
他问我还有什么问题。
我问他我还有什么不足，有没有暴露什么缺点。他笑了，说几十分钟看不出来。
我问他什么时候出结果。他说一两周以内。
我问他做什么业务。他说商业变现。我说挺好。
一个小时结束。
2017-09-21 14:03:11
腾讯服务端开发一面
1 链表反转
用栈，直接写
2 #define middle (a,b,c)
我写了一半10分钟时间到了。
查的答案：#define MID(a, b, c) (a < b ? (b < c ? b : a < c ? c : a) : (b > c ? b : a > c ? c : a))
3 Linux中fd如何组织，用什么数据结构
查了一下，在Linux里面用的位图。
问了项目
问了select和epoll的区别
问了进程间如何通信
问了TCP分手过程
问我有什么问题
他是腾讯云部门，做C++
写了10分钟题目，问了二十几分钟问题，结束。
2017-09-22 15:00:34
京东校招开发电话一面
自我介绍
线程和进程区别
随便说说，没说好。应该把clone()调用跟他说说。
TCP建立
说了三次握手的过程。没说出建立过程中的状态名称。
HashMap的原理
数组加链表，后改成红黑树。应该吧hash函数也跟他说说。
数据库的索引是什么，原理
B+树
时间复杂度是什么
举了例子
项目里面用到了JAVA的哪些东西
多线程，一些设计模式
面向对象有什么用
三大特性
JVM的内存模型
说了内存区域，但是忘了方法区
JVM怎么加载类
双亲委派机制，但是具体我不了解，没说出来。
静态变量放在哪
我说常量池，说忘了常量池所在区域的名称
你有什么优点
我说我学习能力、研究能力强。
举个例子证明你研究能力强
举了项目例子。
问我有什么问题
他说他是大数据部门的。问他怎么没来西安，他说他们部门没来。
总共20分钟结束。希望不大。
2017-09-24 16:52:35
腾讯校招二面
没想到我的二面是电话面，下午突然来了个电话。
首先自我介绍。
让我说一个对我提升最大的项目。
我说了打印移植项目。
项目里面涉及了动态链接库，他问我两个进程调用了同一个动态链接库，一个进程修改了全局变量，另一个进程能不能读取到修改后的全局变量。
我说不能，因为两个进程是在不同的地址空间，读取的动态链接库只是代码相同，内存空间完全不同。
他问我对网络有没有了解。
我说有一些。
他问我超时重传和快速重传有什么不同。
我说超时重传是数据包丢包的时候，达到一定时间没有收到响应包会重发一个数据包。快速重传是拥塞控制的手段，当数据包发送太快，造成丢包，系统会降低发送速度，然后通过快速重传机制快速增加发送速度。
这里我把快速重传说错了，如果发送端接收到3个以上的重复ACK，就应该意识到，数据丢了，需要重新传递。这个机制不需要等到重传定时器溢出，所以叫做快速重传。
他问我知不知道TCP的定时器。
我说不知道。
以前没看过，TCP里有四种定时器：重传计时器、坚持计时器、保活计时器、时间等待计时器。
他问我能不能说说打印程序的流程。
我就说了CUPS程序的数据转换流程。
我这边没说CUPS里的epoll部分，没说好。
他问我项目里的多线程。
我就说了等待命令输出的多线程部分。
他问我你的优势是什么。
我就说我学习能力，研究能力强。
他问我现在缺乏什么。
我说专业领域的学习还不够，比如服务端框架有待学习。
他问我有什么问题。
他说他是腾讯云的，是二面，只是不是现场。
总共23分钟，领域不对口，回答的也不行，没戏。
2017-09-25 18:00:52
好未来校招一面
第一题 Z字形遍历一个树
我用两个栈做出来了。
第二题 两个等长的有序数组，求合并后的中位数，时间复杂度O(logn)
没搞出来，用归并做了个O(n)，最后放弃。
（Leetcode 4原题，《算法导论》9.3-8 原题，类似二分查找）
第三题 根据中序和前序遍历构造一个二叉树。
递归了半天，没写出来。
（《剑指Offer》第二版 面试题7 原题）
他说他们主要是搞php的。
让我说说JAVA的多线程。
我就说了Runnable和Thread两种创建方式，线程池，同步。
他不是很了解JAVA，但是他说好像还有一种创建方式。我说不了解。
回来查了一下还真有三种方式。继承Thread类、实现Runnable接口、使用ExecutorService、Callable、Future实现有返回结果的多线程
让我说说JAVA的GC
我就说了一通。
让我写个脚本，解析一个日志文件里，每天访问各个端口的次数。每个日志文件存了七天的数据。
我就用grep sort count 统计了一下，然后日期是写死的。他也没说什么。
他就没什么问题了。
我问他们后台都是php吗，他说大部分是的，JAVA很少。
他们总共来五天，这是第三天了。
2017-09-26 09:00:06
好未来校招二面 主动放弃
2017-09-26 10:18:06
京东校招电话二面 主动放弃
昨晚拿到百度offer，校招结束。
