现在的位置: 首页 > 综合 > 正文

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

2014年07月10日 ⁄ 综合 ⁄ 共 4379字 ⁄ 字号 小 中 大 ⁄ 评论关闭
  今天在网上偶然看到一道阿里巴巴海量面试题，感觉挺好的，所以研究了下。
    题目：面试官问到，我们阿里巴巴公司收到了很多简历，比如说百万级别的简历，你可否设计一个算法，让我输入一个姓，程序输出所有这个姓的人，比如我输入张，输出是：张三，张四，张五等。
     设计思路：
     这道题其实不难，可以利用hash+链表的方式实现。
     代码实现：

     

[cpp] view
plaincopyprint?

  1. #include <iostream>    
  2. #include <list>    
  3. #include <vector>    
  4. #include <string>    
  5. #include <ctime>    
  6. #include <cstdlib>    
  7. #include <cstdio>    
  8. using namespace std;    
  9.     
  10. typedef string KeywordType;     
  11. /*  
  12. 简历类  
  13. */    
  14.     
  15. class Resume {    
  16. public:    
  17.     KeywordType surname;  //把姓作为关键字    
  18.     void *ptr; //指向简历    
  19.     string name; //人名    
  20.     long no; //简历编号    
  21. public:    
  22.     Resume(KeywordType surname=0,void *ptr=0,string name=0,long no=0) {    
  23.         this->surname=surname;    
  24.         this->ptr=ptr;    
  25.         this->name=name;    
  26.         this->no=no;    
  27.     }    
  28.     string getName() const {    
  29.         return name;    
  30.     }    
  31. };    
  32.     
  33. const double max=1e5;  //最多的简历数    
  34.     
  35. /*  
  36. 简历管理类,实现核心算法  
  37. */    
  38. class ResumeManage {    
  39. private:    
  40.     vector<list<Resume>* >surnameArray;  //向量中存放着list的地址    
  41.     list<Resume>list_wang;   //姓名是wang的双向链表    
  42.     list<Resume>list_li;     //姓名是li的双向链表    
  43.     list<Resume>list_qian;   //姓名是qian的双向链表    
  44.     list<Resume>list_zhao;   //姓名是zhao的双向链表    
  45.     list<Resume>list_sun;    //姓名是sun的双向链表    
  46.     list<Resume>list_zhang;  //姓名是zhang的双向链表    
  47.     //... 还可以增加有关简历的链表    
  48.     
  49.     /*  
  50.     此函数随机产生一个string类型的对象  
  51.     */    
  52.     string LongToString() {        
  53.         int val=rand()%(long)max;    
  54.         int a=val%10;    
  55.         char *s=new char[10];    
  56.         itoa(a,s,10);    
  57.         return static_cast<string>(s);    
  58.     }    
  59.     /*  
  60.     此函数初始化surnameArray  
  61.     */    
  62.     void InitSurnameArray() {    
  63.         long i;    
  64.         srand(unsigned(time(0)));    
  65.         for(i=0;i<long(max);i++) {    
  66.             Resume r("wang",0,"wang"+LongToString(),i);  //构造一个简历    
  67.             list_wang.push_back(r);  //加入姓为wang的链表    
  68.         }    
  69.         surnameArray.push_back(&list_wang);  //加入向量    
  70.         
  71.         for(i=0;i<long(max);i++) {    
  72.             Resume r("li",0,"li"+LongToString(),i);  //构造一个简历    
  73.             list_li.push_back(r);  //加入链表    
  74.         }    
  75.         surnameArray.push_back(&list_li);    
  76.     
  77.         for(i=0;i<long(max);i++) {    
  78.             Resume r("qian",0,"qian"+LongToString(),i);  //构造一个简历    
  79.             list_qian.push_back(r);  //加入链表    
  80.         }    
  81.         surnameArray.push_back(&list_qian);    
  82.     
  83.         for(i=0;i<long(max);i++) {    
  84.             Resume r("zhao",0,"zhao"+LongToString(),i);  //构造一个简历    
  85.             list_zhao.push_back(r);  //加入链表    
  86.         }    
  87.         surnameArray.push_back(&list_zhao);    
  88.     
  89.         for(i=0;i<long(max);i++) {    
  90.             Resume r("sun",0,"sun"+LongToString(),i);  //构造一个简历    
  91.             list_sun.push_back(r);  //加入链表    
  92.         }    
  93.         surnameArray.push_back(&list_sun);    
  94.     
  95.         for(i=0;i<long(max);i++) {    
  96.             Resume r("zhang",0,"zhang"+LongToString(),i);  //构造一个简历    
  97.             list_zhang.push_back(r);  //加入链表    
  98.         }    
  99.         surnameArray.push_back(&list_zhang);    
  100.     }    
  101.     /*  
  102.     此函数实现将姓映射为一个整数,这个整数恰好是这个姓的链表在向量中的位置  
  103.     */    
  104.     int Map(string surname) {    
  105.         if(surname=="wang") return 0;    
  106.         if(surname=="li") return 1;    
  107.         if(surname=="qian") return 2;    
  108.         if(surname=="zhao") return 3;    
  109.         if(surname=="sun") return 4;    
  110.         if(surname=="zhang") return 5;    
  111.         //...还可以加入一些代码    
  112.         return -1;    
  113.     }    
  114.     /*  
  115.     此函数完成核心功能,能够在很短的时间内找到满足题意的解  
  116.     */    
  117. public:    
  118.     bool find(string surname) {    
  119.         clock_t start,end;    
  120.         start=clock();    
  121.         int index=Map(surname);    
  122.         if(index==-1) return false;    
  123.         list<Resume> *pos=surnameArray[index];    
  124.         list<Resume>::iterator it;    
  125.         if(pos) {    
  126.             it=pos->begin();    
  127.             while(it!=pos->end()) {    
  128.                 cout<<it->getName()<<endl;    
  129.                 //cout<<it->surname;    
  130.                 it++;    
  131.             }    
  132.         }    
  133.         end=clock();    
  134.         cout<<"查找时间为"<<(end-start)/CLOCKS_PER_SEC<<"秒"<<endl;     
  135.         return true;    
  136.     }    
  137.     
  138. public:    
  139.     ResumeManage() {    
  140.         InitSurnameArray();    
  141.         cout<<"请输入要查找的姓:";    
  142.     }    
  143.     
  144. };    
  145. void main() {    
  146.     ResumeManage rm;        
  147.     string surname;    
  148.     cin>>surname;    
  149.     if(rm.find(surname)==false) {    
  150.         cerr<<"姓名不存在,查找失败!"<<endl;    
  151.     }    
  152. }    
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞