2015年阿里研发工程师实习笔试附加题
题目1：
常常会有频繁申请、释放内存的需求，比如在发送网络报文时，每次都要分配内存以存储报文，等报文发送完成后又需要删除报文。
为了避免频繁的new/delete对系统带来的开销，需要实现一个通用的FreeList机制。使用者总是从free list中分配内存，如果存在没有使用的内存块就直接摘出来使用，如果没有的话再从系统中分配。使用完毕后并不去直接delete该内存块，而是交给FreeList保管。
要求：
1. 实现一个对固定大小内存块进行管理的通用FreeList类，给出定义和实现。要求不能使用STL中的容器类。定义类的接口和实现时注意通用性、健壮性和可测试性。
2. 如果该类的对象可能会被多个thread同时访问，请描述如何怎样保证线程安全。有没有办法在保证线程安全的同时尽可能增大并发度？如果有也请描述你的思路。
题目2：
假设这样一个场景：当很多用户并发获取服务，server端资源不足时，希望用户能够按照预先分配的配额来使用资源。
比如预先定义好user1, user2, user3的配额是20%, 30%, 50%，资源争抢时希望服务器有20%的服务能力分配给user1， 30%给user2， 50%给user3。
但是如果某个时刻只有user1的请求，server还是要把100%的服务能力分配给user1以充分利用资源；又如某个时间段只有user2/user3在访问服务，则按照30%:50%的比率来分配资源。
需要通过一个类似于队列的ManagedQueue类来封装上述功能。
入队的时候需要提供user id（32位正整数）以及用户的任务(Task)。我们假设系统的用户数是有上限的，不会超过10个。
当队列中各个用户的请求均非空时，要求出队的task分布符合用户的配额设置。延续上面的例子如果连续出队100次，要求user1的task有20个左右，user2的task 30个左右， user3的50个左右。
这里出队的task恰好能对应服务器的服务能力。
要求：
1. 给出关键数据结构以及ManagedQueue的定义。用户任务Task可以认为是一个已经实现的类来使用。可以使用STL容器类。
2. 实现出队方法Dequeue()，请尽可能写健壮的代码
注意：这里并不要求精确的按照比例分配任务，只要统计意义上满足预定义的配额比例就可以了。
题目3：
分布式系统中的RPC请求经常出现乱序的情况。
写一个算法来将一个乱序的序列保序输出。例如,假设起始序号是1，对于(1, 2, 5, 8, 10, 4, 3, 6, 9, 7)这个序列，输出是:
1
2
3, 4, 5
6
7, 8, 9, 10
上述例子中，3到来的时候会发现4,5已经在了。因此将已经满足顺序的整个序列（3, 4, 5）输出为一行。
要求：
1. 写一个高效的算法完成上述功能，实现要尽可能的健壮、易于维护
2. 为该算法设计并实现单元测试
常常会有频繁申请、释放内存的需求，比如在发送网络报文时，每次都要分配内存以存储报文，等报文发送完成后又需要删除报文。
为了避免频繁的new/delete对系统带来的开销，需要实现一个通用的FreeList机制。使用者总是从free list中分配内存，如果存在没有使用的内存块就直接摘出来使用，如果没有的话再从系统中分配。使用完毕后并不去直接delete该内存块，而是交给FreeList保管。
要求：
1. 实现一个对固定大小内存块进行管理的通用FreeList类，给出定义和实现。要求不能使用STL中的容器类。定义类的接口和实现时注意通用性、健壮性和可测试性。
2. 如果该类的对象可能会被多个thread同时访问，请描述如何怎样保证线程安全。有没有办法在保证线程安全的同时尽可能增大并发度？如果有也请描述你的思路。
题目2：
假设这样一个场景：当很多用户并发获取服务，server端资源不足时，希望用户能够按照预先分配的配额来使用资源。
比如预先定义好user1, user2, user3的配额是20%, 30%, 50%，资源争抢时希望服务器有20%的服务能力分配给user1， 30%给user2， 50%给user3。
但是如果某个时刻只有user1的请求，server还是要把100%的服务能力分配给user1以充分利用资源；又如某个时间段只有user2/user3在访问服务，则按照30%:50%的比率来分配资源。
需要通过一个类似于队列的ManagedQueue类来封装上述功能。
入队的时候需要提供user id（32位正整数）以及用户的任务(Task)。我们假设系统的用户数是有上限的，不会超过10个。
当队列中各个用户的请求均非空时，要求出队的task分布符合用户的配额设置。延续上面的例子如果连续出队100次，要求user1的task有20个左右，user2的task 30个左右， user3的50个左右。
这里出队的task恰好能对应服务器的服务能力。
要求：
1. 给出关键数据结构以及ManagedQueue的定义。用户任务Task可以认为是一个已经实现的类来使用。可以使用STL容器类。
2. 实现出队方法Dequeue()，请尽可能写健壮的代码
注意：这里并不要求精确的按照比例分配任务，只要统计意义上满足预定义的配额比例就可以了。
题目3：
分布式系统中的RPC请求经常出现乱序的情况。
写一个算法来将一个乱序的序列保序输出。例如,假设起始序号是1，对于(1, 2, 5, 8, 10, 4, 3, 6, 9, 7)这个序列，输出是:
1
2
3, 4, 5
6
7, 8, 9, 10
上述例子中，3到来的时候会发现4,5已经在了。因此将已经满足顺序的整个序列（3, 4, 5）输出为一行。
要求：
1. 写一个高效的算法完成上述功能，实现要尽可能的健壮、易于维护
2. 为该算法设计并实现单元测试
