阿里面试官常用的题库
一、计算机基础&编程语言
1.1 操作系统
● 1. 进程的有哪几种状态，状态转换图，及导致转换的事件。
● 2. 进程与线程的区别。
● 3. 进程通信的几种方式。
● 4. 线程同步几种方式。(一定要会写生产者、消费者问题，完全消化理解)
● 5. 线程的实现方式. (也就是用户线程与内核线程的区别)
● 6. 用户态和核心态的区别。
● 7. 用户栈和内核栈的区别。
● 8. 内存池、进程池、线程池。(c++程序员必须掌握)
● 9. 死锁的概念，导致死锁的原因.
● 10. 导致死锁的四个必要条件。
● 11. 处理死锁的四个方式。
● 12. 预防死锁的方法、避免死锁的方法。
● 13. 进程调度算法。
● 14. Windows内存管理的方式(块式、页式、段式、段页式).
● 15. 内存连续分配方式采用的几种算法及各自优劣。
● 16. 动态链接及静态链接.
● 17. 基本分页、请求分页储存管理方式。
● 18. 基本分段、请求分段储存管理方式。
● 19. 分段分页方式的比较各自优缺点。
● 20. 几种页面置换算法，会算所需换页数。(LRU用程序如何实现？)
● 21. 虚拟内存的定义及实现方式。
● 22.操作系统的四个特性。
● 23. DMA。
● 24. Spooling。
● 25. 外存分配的几种方式，及各种优劣。
1.2 数据库
● 索引的作用？和它的优点缺点是什么？使用索引查询一定能提高查询的性能吗？为什么
● 什么是内存泄漏？如何避免内存泄露？
● 如何维护数据库的完整性和一致性？
● 什么是事务？什么是锁？
● 事务四大特性是什么？事务的隔离级别有哪些？
● 什么是主键?什么是外键?
● 对一个投入使用的在线事务处理表格有过多索引需要有什么样的性能考虑?
● 什么是数据模型？什么是规范化？
● 谈谈数据库设计的三范式
● 数据库的乐观锁和悲观锁是什么？
● 什么是死锁？如何避免死锁？如何处理死锁问题？
1.3 计算机网络
● 1. 电路交换与分组交换的区别？ 优劣对比。
● 2. OSI有哪几层，会画出来，知道主要几层的各自作用。
● 3.TCP/IP有哪几层，会画出来，知道所有层数的作用，会列举各层主要的协议名称。
● 4. 硬件(MAC)地址的概念及作用。
● 5. ARP协议的用途 及算法、在哪一层上会使用arp？
● 6. CRC冗余校验算法，反码和检验算法。
● 7. 如何实现透明传输。
● 8. 知道各个层使用的是哪个数据交换设备。（交换机、路由器、网关）
● 9. 路由表的内容。
● 10. 分组转发算法。
● 11.IP报文的格式，格式的各个字段的含义要理解。
● 12. MTU的概念，啥叫路径MTU？MTU发现机制，TraceRoute(了解)。
● 13. RIP协议的概念 及算法。
● 14. ICMP协议的主要功能。
● 15. 组播和多播的概念，IGMP的用途。
● 16. Ping协议的实现原理，ping命令格式。
● 17.子网划分的概念，子网掩码。
● 18.IP地址的分类，如何划分的，及会计算各类地址支持的主机数。
● 19. DNS的概念，用途，DNS查询的实现算法。
● 20.TCP与UDP的概念，相互的区别及优劣。
● 21. UDP报文的格式，字段的意义。
● 22.TCP报文的格式，字段的意义。
● 23. TCP通过哪些措施，保证传输可靠？
● 24.三次握手，四次断开过程。
● 25.TIME_WAIT状态的概念及意义。
● 26. 滑动窗口协议 与 停止等待协议的区别。
● 27.TCP的流量控制和拥塞控制实现原理(会画拥塞控制的典型图)。
● 28. TCP的快速重传与快速恢复算法。
● 29. TFTP与FTP的区别。
● 30. 阻塞方式和非阻塞方式，阻塞connect与非阻塞connect。(比较难，有兴趣可以了解)
● 31.HTTP基本格式。
1.4 java面试题
● 1.什么是Java虚拟机？为什么Java被称作是“平台无关的编程语言”？
● static关键字是什么意思？Java中是否可以覆盖(override)一个private或者是static的方法？
● 是否可以在static环境中访问非static变量？
● Java中的方法覆盖(Overriding)和方法重载(Overloading)是什么意思？
● Java中，什么是构造函数？什么是构造函数重载？什么是复制构造函数？
● Java支持多继承么？
● 接口和抽象类的区别是什么？
● 什么是值传递和引用传递？
● java创建线程有几种不同的方式？你喜欢哪一种？为什么？
● 概括的解释下线程的几种可用状态。
● 同步方法和同步代码块的区别是什么？
● Java集合类框架的基本接口有哪些？
● 为什么集合类没有实现Cloneable和Serializable接口？
● 什么是迭代器(Iterator)？
● Java中的HashMap的工作原理是什么？ConcurrentHashMap呢？
● hashCode()和equals()方法的重要性体现在什么地方？
● 数组(Array)和列表(ArrayList)有什么区别？什么时候应该使用Array而不是ArrayList？
● ArrayList和LinkedList有什么区别？
● java的动态代理机制是怎样的？
● 你了解大O符号(big-O notation)么？你能给出不同数据结构的例子么？
● 如何权衡是使用无序的数组还是有序的数组？
● Enumeration接口和Iterator接口的区别有哪些？
● Java中垃圾回收有什么目的？什么时候进行垃圾回收？
● finalize()方法什么时候被调用？析构函数(finalization)的目的是什么？
● 如果对象的引用被置为null，垃圾收集器是否会立即释放对象占用的内存？
● Java堆的结构是什么样子的？什么是堆中的永久代(Perm Gen space)?
● 串行(serial)收集器和吞吐量(throughput)收集器的区别是什么？
● 在Java中，对象什么时候可以被垃圾回收？
● JVM的永久代中会发生垃圾回收么？
● Java中的两种异常类型是什么？他们有什么区别？
● Java中Exception和Error有什么区别？
● throw和throws有什么区别？
● 异常处理完成以后，Exception对象会发生什么变化？
● 异常处理的时候，finally代码块的重要性是什么？
● finally代码块和finalize()方法有什么区别？
● java类是如何被虚拟机加载的？生命周期又是怎样的？
1.5 spring面试题
● 什么是Spring框架？Spring框架有哪些主要模块？
● 使用Spring框架有什么好处？
● 什么是控制反转（IOC）？什么是依赖注入？
● 请解释下Spring中的IOC？
● BeanFactory和ApplicationContext有什么区别？
● 将Spring配置到你的应用中共有几种方法？
● 什么基于XML的配置？
● 什么基Java的配置？
● 怎样用注解的方式配置Spring？
● 描述Spring Bean的生命周期？
● 描述Spring中各种Bean的范围？
● 什么是Spring的嵌入beans？
● Spring框架中的单例bean是否是线程安全的？
● 请举例说明如何用Spring注入一个Java的集合类？
● 请举例说明如何在Spring的Bean中注入一个java.util.Properties？
● 请解释Spring的Bean的自动生成原理？
● 请辨析自动生成Bean之间模块的区别？
● 如何开启基于基于注解的自动写入？
● 请举例说明@Required注解？
● 请举例说明@Autowired注解？
● 请举例说明@Qualifier注解？
● 请说明构造器注入和setter方法注入之间的区别？
● Spring框架中不同类型event有什么区别？
● FileSystemResource和ClassPathResource有何区别？
● 请列举Spring框架中用了哪些设计模式？
二、数据结构
考察学生对经典数据结构的掌握程度，数组（排序、查找算法）、链表（遍历、翻转、增删改）、堆、栈、树（二叉树遍历、B/B+树、红黑树原理，节点增删改）、图（搜索算法）
2.1 链表
● 链表是一种由节点（Node）组成的线性数据集合，每个节点通过指针指向下一个节点。它是一种由节点组成，并能用于表示序列的数据结构。
● 单链表：每个节点仅指向下一个节点，最后一个节点指向空（null）。
● 双链表：每个节点有两个指针p，n。p指向前一个节点，n指向下一个节点；最后一个节点指向空。
● 循环链表：每个节点指向下一个节点，最后一个节点指向第一个节点。
● 时间复杂度：
○ 索引：O(n)
○ 查找：O(n)
○ 插入：O(1)
○ 删除：O(1)
2.2 栈
● 栈是一个元素集合，支持两个基本操作：push用于将元素压入栈，pop用于删除栈顶元素。
后进先出的数据结构（Last In First Out, LIFO）
● 时间复杂度
○ 索引：O(n)
○ 查找：O(n)
○ 插入：O(1)
○ 删除：O(1)
2.3 队列
● 队列是一个元素集合，支持两种基本操作：enqueue 用于添加一个元素到队列，dequeue 用于删除队列中的一个元素。
● 先进先出的数据结构（First In First Out, FIFO）。
● 时间复杂度
○ 索引：O(n)
○ 查找：O(n)
○ 插入：O(1)
○ 删除：O(1)
2.4 树
2.4.1 二叉树
● 二叉树是一个树形数据结构，每个节点最多可以有两个子节点，称为左子节点和右子节点。
● 满二叉树（Full Tree）：二叉树中的每个节点有 0 或者 2 个子节点。
● 完美二叉树（Perfect Binary）：二叉树中的每个节点有两个子节点，并且所有的叶子节点的深度是一样的。
● 完全二叉树：二叉树中除最后一层外其他各层的节点数均达到最大值，最后一层的节点都连续集中在最左边。
● 重点考察：二叉树非递归遍历实现
2.4.2 二叉查找树
● 二叉查找树（BST）是一种二叉树。其任何节点的值都大于等于左子树中的值，小于等于右子树中的值。
● 时间复杂度
○ 索引：O(log(n))
○ 查找：O(log(n))
○ 插入：O(log(n))
○ 删除：O(log(n))
2.4.3 字典树
● 字典树又称为基数树或前缀树，是一种用于存储键值为字符串的动态集合或关联数组的查找树。树中的节点并不直接存储关联键值，而是该节点在树中的位置决定了其关联键值。一个节点的所有子节点都有相同的前缀，根节点则是空字符串。
2.4.4 树状数组
● 树状数组，又称为二进制索引树（Binary Indexed Tree，BIT），其概念上是树，但以数组实现。数组中的下标代表树中的节点，每个节点的父节点或子节点的下标可以通过位运算获得。数组中的每个元素都包含了预计算的区间值之和，在整个树更新的过程中，这些计算的值也同样会被更新。
● 时间复杂度
○ 区间求和：O(log(n))
○ 更新：O(log(n))
2.4.5 线段树
● 线段树是用于存储区间和线段的树形数据结构。它允许查找一个节点在若干条线段中出现的次数。
● 时间复杂度
○ 区间查找：O(log(n))
○ 更新：O(log(n))
2.4.7 红黑树
● 红黑树是一个平衡的二叉树，但不是一个完美的平衡二叉树。红黑树是在普通二叉树上，对没个节点添加一个颜色属性形成的，同时整个红黑二叉树需要同时满足一下五条性质
○ 性质一：节点是红色或者是黑色；
○ 性质二：根节点是黑色；
○ 性质三：每个叶节点（NIL或空节点）是黑色；
○ 性质四：每个红色节点的两个子节点都是黑色的（也就是说不存在两个连续的红色节点）；
○ 性质五：从任一节点到其没个叶节点的所有路径都包含相同数目的黑色节点；
2.4.6 B/B+树
● B树是为磁盘和其他直接存取的辅助存储设备而设计的一种平衡搜索树。B树类似于红黑树，但它们在降低I/O操作数方面要更好一些。许多数据库系统使用B树或者B树的变种来存储信息。B树与红黑树的不同之处在于B树的结点可以有很多孩子，从数个到树千个。也就是说，一个B树的“分支因子”可以相当大，尽管它通常依赖于所使用的磁盘单元的特性。B树类似于红黑树，就是每棵含有n个结点的B数高度为O(lgn)。然而，一棵B树的严格高度可能比一棵红黑树的高度要小许多，这是因为它的分支因子。
2.5 堆
● 堆是一种基于树的满足某些特性的数据结构：整个堆中的所有父子节点的键值都满足相同的排序条件。堆分为最大堆和最小堆。在最大堆中，父节点的键值永远大于等于所有子节点的键值，根节点的键值是最大的。最小堆中，父节点的键值永远小于等于所有子节点的键值，根节点的键值是最小的。
● 时间复杂度
○ 索引：O(log(n))
○ 查找：O(log(n))
○ 插入：O(log(n))
○ 删除：O(log(n))
○ 删除最大值/最小值：O(1)
2.6 哈希
● 哈希用于将任意长度的数据映射到固定长度的数据。哈希函数的返回值被称为哈希值、哈希码或者哈希。如果不同的主键得到相同的哈希值，则发生了冲突。
● Hash Map：hash map 是一个存储键值间关系的数据结构。HashMap 通过哈希函数将键转化为桶或者槽中的下标，从而便于指定值的查找。
● 冲突解决
○ 链地址法（Separate Chaining）：在链地址法中，每个桶（bucket）是相互独立的，每一个索引对应一个元素列表。处理HashMap 的时间就是查找桶的时间（常量）与遍历列表元素的时间之和。
○ 开放地址法（Open Addressing）：在开放地址方法中，当插入新值时，会判断该值对应的哈希桶是否存在，如果存在则根据某种算法依次选择下一个可能的位置，直到找到一个未被占用的地址。开放地址即某个元素的位置并不永远由其哈希值决定。
2.7 图
● 图是G =（V，E）的有序对，其包括顶点或节点的集合 V 以及边或弧的集合E，其中E包括了两个来自V的元素（即边与两个顶点相关联 ，并且该关联为这两个顶点的无序对）。
● 无向图：图的邻接矩阵是对称的，因此如果存在节点 u 到节点 v 的边，那节点 v 到节点 u 的边也一定存在。
● 有向图：图的邻接矩阵不是对称的。因此如果存在节点 u 到节点 v 的边并不意味着一定存在节点 v 到节点 u 的边。
● 重点考察：图的遍历算法、图的最短路径算法
三、基础算法
3.1 算法运行效率分析
大 O 表示
● 大 O 表示用于表示某个算法的上界，用于描述最坏的情况。
小 O 表示
● 小 O 表示用于描述某个算法的渐进上界，二者逐渐趋近。
大 Ω 表示
● 大 Ω 表示用于描述某个算法的渐进下界。
小 ω 表示
● 小 ω 表示用于描述某个算法的渐进下界，二者逐渐趋近。
Theta Θ 表示
● Theta Θ 表示用于描述某个算法的确界，包括最小上界和最大下界。
3.2 排序算法
3.2.1 快速排序
● 快速排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
● 稳定：否
● 时间复杂度
○ 最优：O(nlog(n))
○ 最差：O(n^2)
○ 平均：O(nlog(n))
3.2.2 合并排序
● 合并排序是一种分治算法。这个算法不断地将一个数组分为两部分，分别对左子数组和右子数组排序，然后将两个数组合并为新的有序数组。
● 稳定：是
● 时间复杂度：
○ 最优：O(nlog(n))
○ 最差：O(nlog(n))
○ 平均：O(nlog(n))
3.2.3 桶排序
● 桶排序是一种将元素分到一定数量的桶中的排序算法。每个桶内部采用其他算法排序，或递归调用桶排序。
● 时间复杂度
○ 最优：O(n + k)
○ 最差：O(n^2)
○ 平均：O(n + k)
3.2.4 基数排序
● 基数排序类似于桶排序，将元素分发到一定数目的桶中。不同的是，基数排序在分割元素之后没有让每个桶单独进行排序，而是直接做了合并操作。
● 时间复杂度
○ 最优：O(nk)
○ 最差：O(nk)
○ 平均：O(nk)
3.3 图算法
3.3.1 深度优先搜索
● 深度优先搜索是一种先遍历子节点而不回溯的图遍历算法。
● 时间复杂度：O(|V| + |E|)
3.3.2 广度优先搜索
● 广度优先搜索是一种先遍历邻居节点而不是子节点的图遍历算法。
● 时间复杂度：O(|V| + |E|)
3.3.3 拓扑排序
● 拓扑排序是有向图节点的线性排序。对于任何一条节点 u 到节点 v 的边，u 的下标先于 v。
● 时间复杂度：O(|V| + |E|)
3.3.4 最短路径算法Dijkstra
● Dijkstra 算法是一种在有向图中查找单源最短路径的算法。
● 时间复杂度：O(|V|^2)
3.3.5 Bellman-Ford算法
● Bellman-Ford 是一种在带权图中查找单一源点到其他节点最短路径的算法。
● 虽然时间复杂度大于 Dijkstra 算法，但它可以处理包含了负值边的图。
● 时间复杂度：
○ 最优：O(|E|)
○ 最差：O(|V||E|)
3.3.6 Floyd-Warshall算法
● Floyd-Warshall 算法是一种在无环带权图中寻找任意节点间最短路径的算法。
● 该算法执行一次即可找到所有节点间的最短路径（路径权重和）。
● 时间复杂度：
○ 最优：O(|V|^3)
○ 最差：O(|V|^3)
○ 平均：O(|V|^3)
3.3.7 最小生成树算法
● 最小生成树算法是一种在无向带权图中查找最小生成树的贪心算法。换言之，最小生成树算法能在一个图中找到连接所有节点的边的最小子集。
● 时间复杂度：O(|V|^2)
3.3.8 Kruskal算法
● Kruskal 算法也是一个计算最小生成树的贪心算法，但在 Kruskal 算法中，图不一定是连通的。
● 时间复杂度：O(|E|log|V|)
3.4 贪心算法
● 贪心算法总是做出在当前看来最优的选择，并希望最后整体也是最优的。
● 使用贪心算法可以解决的问题必须具有如下两种特性：
○ 最优子结构
■ 问题的最优解包含其子问题的最优解。
○ 贪心选择
■ 每一步的贪心选择可以得到问题的整体最优解。
● 实例-硬币选择问题
● 给定期望的硬币总和为 V 分，以及 n 种硬币，即类型是 i 的硬币共有 coinValue[i] 分，i的范围是 [0…n – 1]。假设每种类型的硬币都有无限个，求解为使和为 V 分最少需要多少硬币？
● 硬币：便士（1美分），镍（5美分），一角（10美分），四分之一（25美分）。
● 假设总和 V 为41,。我们可以使用贪心算法查找小于或者等于 V 的面值最大的硬币，然后从 V 中减掉该硬币的值，如此重复进行。
○ V = 41 | 使用了0个硬币
○ V = 16 | 使用了1个硬币(41 – 25 = 16)
○ V = 6 | 使用了2个硬币(16 – 10 = 6)
○ V = 1 | 使用了3个硬币(6 – 5 = 1)
○ V = 0 | 使用了4个硬币(1 – 1 = 0)
3.5 位运算算法
● 位运算即在比特级别进行操作的技术。使用位运算技术可以带来更快的运行速度与更小的内存使用。
● 测试第 k 位：s & (1 << k);
● 设置第k位：s |= (1 << k);
● 关闭第k位：s &= ~(1 << k);
● 切换第k位：s ^= (1 << k);
● 乘以2n：s << n;
● 除以2n：s >> n;
● 交集：s & t;
● 并集：s | t;
● 减法：s & ~t;
● 提取最小非0位：s & (-s);
● 提取最小0位：~s & (s + 1);
● 交换值：x ^= y; y ^= x; x ^= y;
3.6 经典算法面试题
1 查找无序数组n中的最小的k个值，要求时间复杂度越低越好。
2 给定一个整数数组，找到一个具有最大和的子数组，返回其最大和， 要求时间复杂度O(n)。
3 给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。
四、大数据处理
4.1 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
假如每个url大小为10bytes，那么可以估计每个文件的大小为50G×64=320G，远远大于内存限制的4G，所以不可能将其完全加载到内存中处理，可以采用分治的思想来解决。
Step1：遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件（记为a0,a1,…,a999 ，每个小文件约300M）；
Step2: 遍历文件b，采取和a相同的方式将url分别存储到1000个小文件（记为b0,b1,…,b999）；
巧妙之处：这样处理后，所有可能相同的url都被保存在对应的小文件（a0 vs b0, a1 vs b1 ,…,a999 vs b999）中，不对应的小文件不可能有相同的url。然后我们只要求出这个1000对小文件中相同的url即可。
Step3：求每对小文件ai和bi中相同的url时，可以把ai的url存储到hash_set/hash_map中。然后遍历bi的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。
4.2 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M，要求返回频数最高的100个词。
Step1：顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为f0 ,f1 ,… ,f4999）中，这样每个文件大概是200k左右，如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M；
Step2：对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用trie树/hash_map等），并取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100词及相应的频率存入文件，这样又得到了5000个文件；
Step3：把这5000个文件进行归并（类似与归并排序）；
4.3 现有海量日志数据保存在一个超级大的文件中，该文件无法直接读入内存，要求从中提取某天出访问百度次数最多的那个IP。
Step1：从这一天的日志数据中把访问百度的IP取出来，逐个写入到一个大文件中；
Step2：注意到IP是32位的，最多有2^32个IP。同样可以采用映射的方法，比如模1000，把整个大文件映射为1000个小文件；
Step3：找出每个小文中出现频率最大的IP（可以采用hash_map进行频率统计，然后再找出频率最大的几个）及相应的频率；
Step4：在这1000个最大的IP中，找出那个频率最大的IP，即为所求。
