2018-03-21
后台开发工程师面经
2018年3月13号
浪潮一面二面
总体来说，浪潮面试很仓促，我记得是前一天晚上在公众号上投完简历，然后当天晚上11点就发下通知第二天10点开始面试。从面试过程中的问题和招聘结果来看，浪潮公司需要掌握云服务技术和Java开发的人比较多。
面试中主要就是探讨所做项目，针对项目，面试官提出一些问题对基础进行考察。
云服务：OpenStack之类的，不了解。
web开发：
1. 参数绑定：有个人的项目中用到了SpringMVC，因此面试官问了他项目中参数绑定的问题。要了解参数绑定，可以先了解下几种前后台传参方式，具体参考：前后台交互之传参方式 - 名字被占用。 - 博客园，重点了解get和post的区别。结合项目，以FindME的更新操作为例，首先要根据list查到对应修改的Id，并根据Id获取该id所对应project全部信息，该Id参数是绑定在路径上传到后台的，即 someUrl/{Id}, 这时的Id可通过 @Pathvariable注解绑定它传过来的值到方法的参数上。此外，还有@RequestParam用于简单类型的处理和@ModelAttribute用于绑定指定的model，例如用于add和change时候，把对应属性的值绑定与注解参数model上。
具体参数的绑定注解和原理参考：
SpringMvc之参数绑定注解详解 - Frank_Lei - 博客园
SpringMVC源码之参数解析绑定原理 - 卧颜沉默 - 博客园
2. servlet生命周期：init() service() destroy()
3. Linux系统分区时哪两个区是必须的？根分区和交换分区，一个是放系统启动时的文件和系统配置文件，一个充当虚拟内存。此外/etc和/bin是必须放在根分区的目录，其实还有/sbin，/dev，/lib。
美团一面
2018.3.21
1. 容器类问了两个，HashMap()和HashSet()，前者还知道一点，后者只知道往里面放的元素不能重，可以做字符串去重工具。针对于HashMap()，先问了我些基本问题，也就是数组+链表，解决冲突等等，后来问到了一个底层实现方法indexFor()，具体实现如下：
static int indexFor (int h,int length){
return h & (length-1);
}
首先，为什么取&，其实对length取%也是可以的，但是效率会降低，因为逻辑运算比模运算时间更快（其实&运算还有别的玄机）。其次，为什么要length-1，因为Node[]数组初始大小是16，按照2^n来扩容，以16为例，即2^n-1之后从10000变为01111，用01111与h做与运算减少了碰撞的可能性，因为1与任何数与，可能为0，可能为1，而0与任何数与只能为0，那么这意味着0001，0011，0101，1001，1011，0111，1101等位置永远都不能存放元素了，空间浪费相当大，更糟的是，在这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率。前方高能哈~面试官又问了，为什么Node[]扩容是按照2^n呢？即2倍形式扩容，初始为16（2^4），扩容一次为32（2^5）…经过林哥和嘉辉的不懈努力，破解了这个谜题，我们可以这样思考，我们认为oldcap=10000，而oldcap-1=01111，扩容之后的newcap-1=11111，这样的设计使得扩容之后的HashMap所有节点重新进行了一次重排，而每个节点是否去重排仅仅取决于h的最高位，为0不重排，为1重排。至于重排的位置，也是由最高位决定。因此，HashMap()解决冲突的办法首先是扩容，然后所有节点进行充分散列重排，万不得已才会转化为红黑树，可以看得出来HashMap的设计是多么的精巧，&与-1与2^n三个trick环环相扣。
2. 面试官直接问，请你解释解释上锁，多线程
这道题回答的不好，因为我只知道需要哪个线程访问什么资源的时候，就把它上锁，用synchronized，然后说了说死锁和生产者消费者模式。但是他想看我了解更深层次的东西，也就是底层，原话几乎是“你说说synchronized”。
3. 数组链表区别
区别请看：2018 美团 春招 iOS面试分享（一面）附答案 - 简书，面试官又问数组的查找方式，我当时一愣，数组查找方式不是直接获取下标嘛，但是答案是：随机查找（好好记住这四个字，说明该了解的专业术语是需要了解的），面试官问既然数组插入效率低，那你说说Java中的ArrayList是如何优化这个问题的？（倒吸一口凉气，原来如此简单）
4. 散列表解决冲突的方法（一定注意专业术语的表达，Hash表是HashMap的说法，散列表才是数据结构正统说法，虽然二者几乎没什么不同）
答：开放地址法（增量设定方法有：线性探测法，平方探测法，再散列法和伪随机序列法）和伟大的拉链法+解释。
5. 给定一个链表，判断其是否有环。
设定两个指针，一个慢，一个快，如果快的追上慢的就说明有环，面试官又问，如果快的把慢的越过去了怎么办呢？当时的想法只是个初步想法，所以这个问题一下把我问懵，答案是不可能越过，因为运动是相对的，快慢指针的相对速度只差1，当快追慢的时候，结局就是二者可能差1步或者差2步。以慢的先走为例，假如差1步，慢的走1步，此时差两步，快的走两步直接遇到，假如差两步，慢的走1步，快的追两步，此时二者差1步，回到了第一种可能性。当然这只是快慢指针速度差1，可能后续还会讨论速度差2，差3…网上还有些关于这个问题的延伸，比如环的长度，入口等等。
环长：当两个指针在环上从第一次相遇到第二次相遇，而二者速度差1时：慢+环=快，2*慢 = 快，所以从第一次相遇到第二次相遇，慢所走的距离就是环长。
入口：二者在环上相遇时可以得到，慢=头结点到环入口的距离+环上距离x，快=头结点到环入口的距离+环上距离x+n倍的环长，而2*慢=快。因此可以得到，头结点到环入口的距离=n倍的环长-环上距离x，所以令一个指针在链表头结点，另一个慢指针在当前环上相遇结点，二者一起走，相遇结点即为入口。
参考：判断单链表中是否有环，找到环的入口节点 - CSDN博客，数据结构面试 之 单链表是否有环及环入口点 附有最详细明了的图解 - 简书
6. SQL语句
7. 给一个数字序列，里面有正数和负数没有0，返回最大值。
面试官没让我远程写，但是让我把自己的思路说清楚，比如第一层循环怎么写，从哪到哪，声明了什么变量，第二层……我用的是下面链接的第二种方法，面试官希望我能优化一下，我提出的优化方案是个很粗略的方案，因此面试官直接提出了自己的想法，即……下面链接的第四种方法。
