一道阿里巴巴面试题--海量数据查找

题目：面试官问，我们阿里巴巴公司收到了很多简历，比如说是百万级别的简历，你能不能设计一个算法，让我输入一个姓，程序输出所有这个姓的人，比如我输入张，输出是张三，张四等等

设计思路：

设计思路见代码：

/*
This is a free Program, You can modify or redistribute it under the terms of GNU
*Description:阿里巴巴现在收到了百万级别的简历,设计一个系统或者算法,输入某个姓,
如输入wang,把所有有关wang的名字输出,比如输出wang0,wang1,wang2,...

*Language: C++
*Development Environment: VC6.0
*Author: Wangzhicheng
*Date: 2012/10/9
*/

#include <iostream>
#include <list>
#include <vector>
#include <string>
#include <ctime>
#include <cstdlib>
#include <cstdio>
using namespace std;

typedef string KeywordType; 
/*
简历类
*/

class Resume {
public:
    KeywordType surname;  //把姓作为关键字
    void *ptr; //指向简历
    string name; //人名
    long no; //简历编号
public:
    Resume(KeywordType surname=0,void *ptr=0,string name=0,long no=0) {
        this->surname=surname;
        this->ptr=ptr;
        this->name=name;
        this->no=no;
    }
    string getName() const {
        return name;
    }
};

const double max=1e5;  //最多的简历数

/*
简历管理类,实现核心算法
*/
class ResumeManage {
private:
    vector<list<Resume>* >surnameArray;  //向量中存放着list的地址
    list<Resume>list_wang;   //姓名是wang的双向链表
    list<Resume>list_li;     //姓名是li的双向链表
    list<Resume>list_qian;   //姓名是qian的双向链表
    list<Resume>list_zhao;   //姓名是zhao的双向链表
    list<Resume>list_sun;    //姓名是sun的双向链表
    list<Resume>list_zhang;  //姓名是zhang的双向链表
    //... 还可以增加有关简历的链表

    /*
    此函数随机产生一个string类型的对象
    */
    string LongToString() {    
        int val=rand()%(long)max;
        int a=val%10;
        char *s=new char[10];
        itoa(a,s,10);
        return static_cast<string>(s);
    }
    /*
    此函数初始化surnameArray
    */
    void InitSurnameArray() {
        long i;
        srand(unsigned(time(0)));
        for(i=0;i<long(max);i++) {
            Resume r("wang",0,"wang"+LongToString(),i);  //构造一个简历
            list_wang.push_back(r);  //加入姓为wang的链表
        }
        surnameArray.push_back(&list_wang);  //加入向量
    
        for(i=0;i<long(max);i++) {
            Resume r("li",0,"li"+LongToString(),i);  //构造一个简历
            list_li.push_back(r);  //加入链表
        }
        surnameArray.push_back(&list_li);

        for(i=0;i<long(max);i++) {
            Resume r("qian",0,"qian"+LongToString(),i);  //构造一个简历
            list_qian.push_back(r);  //加入链表
        }
        surnameArray.push_back(&list_qian);

        for(i=0;i<long(max);i++) {
            Resume r("zhao",0,"zhao"+LongToString(),i);  //构造一个简历
            list_zhao.push_back(r);  //加入链表
        }
        surnameArray.push_back(&list_zhao);

        for(i=0;i<long(max);i++) {
            Resume r("sun",0,"sun"+LongToString(),i);  //构造一个简历
            list_sun.push_back(r);  //加入链表
        }
        surnameArray.push_back(&list_sun);

        for(i=0;i<long(max);i++) {
            Resume r("zhang",0,"zhang"+LongToString(),i);  //构造一个简历
            list_zhang.push_back(r);  //加入链表
        }
        surnameArray.push_back(&list_zhang);
    }
    /*
    此函数实现将姓映射为一个整数,这个整数恰好是这个姓的链表在向量中的位置
    */
    int Map(string surname) {
        if(surname=="wang") return 0;
        if(surname=="li") return 1;
        if(surname=="qian") return 2;
        if(surname=="zhao") return 3;
        if(surname=="sun") return 4;
        if(surname=="zhang") return 5;
        //...还可以加入一些代码
        return -1;
    }
    /*
    此函数完成核心功能,能够在很短的时间内找到满足题意的解
    */
public:
    bool find(string surname) {
        clock_t start,end;
        start=clock();
        int index=Map(surname);
        if(index==-1) return false;
        list<Resume> *pos=surnameArray[index];
        list<Resume>::iterator it;
        if(pos) {
            it=pos->begin();
            while(it!=pos->end()) {
                cout<<it->getName()<<endl;
                //cout<<it->surname;
                it++;
            }
        }
        end=clock();
        cout<<"查找时间为"<<(end-start)/CLOCKS_PER_SEC<<"秒"<<endl; 
        return true;
    }

public:
    ResumeManage() {
        InitSurnameArray();
        cout<<"请输入要查找的姓:";
    }

};
void main() {
    ResumeManage rm;    
    string surname;
    cin>>surname;
    if(rm.find(surname)==false) {
        cerr<<"姓名不存在,查找失败!"<<endl;
    }
}

当max=1e5时，找到全部解

当max=1e6，内存几乎耗尽，程序崩溃