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. 为该算法设计并实现单元测试
已邀请:

第三题借用STL 实现了 不如bitset 那个效率 供参考 多指点

include <iostream>

include <vector>

include <queue>

using namespace std;

int main(int argc, const char *argv[])
{
    vector<int> vec{1,2,5,8,10,4,3,6,9,7};
    priority_queue<int,vector<int>,greater<int> >q;
    int want = 1;

    for(int i=0; i!= vec.size(); i++)
    {
        if(vec[i] == want)
        {
            cout << vec[i];
            want++;

            while(!q.empty() && q.top() == want)
            {
                cout <<"," << q.top();
                q.pop();
                want++;
            }
            cout << endl;
        }else
            q.push(vec[i]);
    }
    return 0;
}

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~