小米2018春季实习生服务端开发工程师笔试题

对于排序算法，经常关注的是其时间复杂度和稳定性。下列排序算法中平均时间复杂度是O(nlogn)且稳定的是？

在面向对象编程里，经常使用is-a来说明对象之间的继承关系，下列对象中不具备继承关系的是？

一个树高（根节点高度为1）为6的平衡二叉树，其节点数可能是？

若磁盘转速是7200转/分，平均寻道时间是8ms，每个磁道包含1000个扇区，则访问一个扇区的平均存取时间为？

德州扑克中总共使用52张牌(不包括大小王)，每个参与者都会先发两张手牌，请问对于一个参与者来说两张手牌组成对子的概率是？

给定一个整数数组，包含正负数且无序，找出和最大的连续子数组，比如数组[1,1,-5,6,7,-2]，则和最大的子数组为[6,7]，最大和为13
1.1定义一个函数，输入是一个整数数组，输出是和最大的连续子数组的和
1.2假设输入的是一个二维数组，而同时连续子数组的定义扩大为连续的二维子数组，比如一个3*4的二维数组[[-1,2,3,-1],[-2,1,2,-2],[-3,-3,-3,-3]]，则和最大的连续子数组是[[2,3],[1,2]]，所以最大和为8，请定义一个函数，输入是一个二维数组，输出是和最大的连续子数组的和，要求：必须使用1.1中函数来求解
1.3继续扩大二维连续子数组的定义，比如支持左右互联，即二维数组的左起始列可以和右边终止列连在一起形成子数组，请定义一个函数，输入是一个二维子数组，输出同样是和最大的连续子数组的和，要求：必须使用1.2中函数来求解
解答要求: 请使用熟悉的语言或伪代码，每个函数给出算法复杂度分析

实现一个数据结构，叫做BoundedBuffer，即初始化时传入一个参数来定义了Buffer的大小，然后有两个public方法，put方法用于存入一个元素，take方法用于取出一个元素，先进先出
2.1实现存储整型的BoundedBuffer，无需线程安全，Buffer满或空时可以抛出异常
2.2将2.1中的整型BoundedBuffer实现改为泛型
2.3实现线程安全的BoundedBuffer，同时put和take如遇到buffer满或空的情况，需要block住调用线程，直到buffer中有空间或者有新数据
2.4给2.3的BoundedBuffer提供带超时的put或take方法，即调用者可以指定超时时间，如果在指定时间内依旧没有空间或没有新数据，则抛出异常
解答要求: 请使用熟悉的语言或伪代码，底层存储只能使用数组或链表