一道阿里巴巴面试题--海量数据查找
题目：面试官问，我们阿里巴巴公司收到了很多简历，比如说是百万级别的简历，你能不能设计一个算法，让我输入一个姓，程序输出所有这个姓的人，比如我输入张，输出是张三，张四等等
设计思路：
设计思路见代码：
/*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*E-mail: 2363702560@qq.com*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，内存几乎耗尽，程序崩溃
