热乎的阿里Java面经,5-12号哈尔滨站

本人东北大学研究生，第一次参加阿里面试，只面了两轮，但我想把这次经历分享给大家，供大家交流学习。来一张圣索亚菲教堂。

正常签到后，进入休息区排号阶段：一个*** 20多个座位，投影仪播放着幻灯片并且显示着接下来要面试人的名字。附上图片一张

一面（面了差不多一个小时,被问蒙蔽了）

面试官拿着简历先大概看了一下，然后让我自我介绍，我介绍完他就把简历放在我的右手边。（这个细节标志着开始进入疯狂问答模式）

1. ArrayList 与 LinkedList 的区别，我说一个类似数组一个类似链表，他说那你画一下数组怎么在内存中存储的，紧接着问我ArrayList 可以根据下表查找， LinkedList可以吗？然后问 ArrayList 初始容量，如果满了会怎么办？怎么扩容？是新建一个2倍空间的数组然后把值复制进去么？

2. 给一棵树，左右子树交换，在纸上手写出来。这考察的就是平时的积累和临场发挥了

3.用过过哪些容器，Tomcat 知道吧，你说说Tomcat给你提供了哪些服务，为什么要用它？自己写一个不行吗？这个真是一头雾水啊。

4.Top N 问题，M个数找出最大的N个（数的取值 0 ~ 65535）。

我的回答：如果M比较小的话可以先排序，用效率高的快排或者归并，然后取出前N个就可以了。若 M比较大的话，可以先把数据分成若干份（K份），每份M/K 个数维护一个含N个数的小顶堆(他很疑惑小顶堆？)，这样先求出每份的Top N，最后对这 K*N 个数筛选选出最大的N个

他追问：你总体的时间复杂度是多少？我当时回答的是将复杂度相加： K* (M/K)Log (M/K) + (K*N)Log(K*N) ，总感觉不对！

他问：还有更高效的方法吗？

我：基于数的取值是 0 ~ 65535的整数，可以用牺牲空间换取时间的方法，维护一个长度是65536的数组array，遍历M个数相应数值对应的数组下标所在的内容+1 ，比如遍历当前值是100，那么array[100]++; 这样数组中存的值表示每个数出现的次数。最后从往前扫描数组array,累加求和sum与N比较即可得到。

他问：这种方法的时间复杂度是多少？ O（M） PS：大家要注重那个时间复杂度的练习啊

他还问：那要是数的取值是浮点数呢？ 0.0，蒙逼了

5. 操作系统页面置换LRU 知道吧。讲一讲！这个平时肯定练过，由于有点紧张答得不好，建议大家好好掌握这些基础知识

LRU还没完：具体怎么实现知道么？我说了频率和记录时间先后，他继续追问我就摇头了。

6. 基于上个问题，如果多个线程请求，你会怎么处理？我说用ConcurentLinkedQueue ，跟他讲了下结构，具体实现策略不知道。

他说可以这样假如1000个线程，多整几个队列假设8个，那么并发量减少到1000/8 ，设成100个队列并发更少。至于哪个线程分到哪个队列，可以用hash的方法将线程分散开。

7.数据库里有个表，tab_demo( id , data) id是主键 , 对于 where id=' 1 ' 和 where data = ' text ' ,数据库是怎么去操作的，我当时灵光一现这肯定是考数据库索引的知识，我答到：前者数据库默认建立了Unique索引，直接根据索引能找到相应的数据，后边的要全表扫描。

追问：如果在data 上也建立索引呢，怎么获取数据然后时间复杂度是多少？我就跟他讲了讲B+树索引。后边的我真心蒙逼还是学得不够深啊

8. 多线程中锁，如何处理呢保证效率。我跟他说的是 ConcurrentHashMap , 锁分段技术 Segment ,并与 HashMap、HashTable对照着阐述了一下自己的观点，他也问了几个基本参数看我是不是真知道。

然后面试官让我去 外边的休息区 等，一面好像就这么多，具体的细节可能有遗漏。

二面（大概30分钟）

先还是自我介绍。

1. 你这项目用到了struts2 ，那你说一下struts1 与 struts2 的区别在哪里？。。。这个问题我真是没想到啊

2. java 设计模式知道吧，那你手写一个单例模式吧。我先写了一个饱汉模式的，他说另外一种！然后写了一个饿汉模式带锁的双重检查

3. 数据库连接池知道么，用的啥连接池，原理是啥？这个问题应该是我今天最大的败笔。我说用了cp30 ，原理我真是一团浆糊 0.0让我哭会

4. 你做的网站并发量是多少，怎么解决的。加行锁和客观控制法

5. 你项目中遇到的最难的问题，怎么解决的？这个也是回答失败的点。

6. 事务Transaction 知道吧，都有些什么特性？说说脏读吧！我说了 ACID ，脏读也是紧张的忘了 0.0好失败啊

7. 谈谈对Hadoop 的理解，我说了大概说了下 HDFS、Map Reduce、Hbase、Hive ，然后说毕设的思路（毕设是基于分布式的）