baidu——郁闷的笔试

  百度采用的是网上笔试和电话面试的形式，说实话，我很不适应。再加上投职位时报了运营部，导致简历都没有通过，等到重新投简历时，已经错过了最好的机会。不过感觉百度对你重复投简历也是来者不拒，只要你有恒心，有实力，去百度还是很有希望的。

下面是我收集的笔试题目：

发信人: sea1 (tian), 信区: Career_Plaza 标 题: 30秒。。。百度测试工程师被拒（附：笔试题） 发信站: 水木社区 (Wed May 17 19:49:32 2006), 站内   说实话，本来就抱什么希望，只是想知道自己的实力怎样。结果。。哎！不过还是要赞一下 百度的相关人员，她们的态度都挺和蔼的！！（也挺PP的）   还是具体的说一下吧：   早就从网上了解到百度公司（位于海淀图书城银科大厦）很搞笑。上到18层后，先是见到 PP服务台小姐，之后就是左边的“百度人民很行”，说真的，从远处看，根本就是“百度人 民银行”。第一见是就是登记（由PPMM负责，后来知道有两个PPMM负责前台，我登记时，那 个不在，否则我会“多线程”的）。之后是负责测试的人员MM来给了我笔试题。看完之后我 差点晕了，几乎不会！！！试题如下： 1、以下符号在LINUX下代表什么文件：p , l, c, d, s, -, MS很基本，不过我对LINUX一点 也不感冒！！（结果我瞎写的，如果有计算机的同学想拍我，一定在站内信箱拍！！） 　　 b 块设备文件   　　 c 字符设备文件   　　 d 目录文件   　　 p 命名管道（ FIFO ）   　　 f 普通文件   　　 l 符号链接文件（ symbolic links ）   　　 s socket 文件 2、编写一个SHELL脚本，保存目录中的文件，并存为.bak文件。（结果还是不会）   3、怎样在LINUX下测试网络状态。不会！ Netstat 4、在LINUX下怎样查询CPU，内存，硬盘的状态。不会！ Top Fdisk -l 5、HTTP：？网络状态下的常见码状态是什么？ 不会！   6、写结果： void fun(char *temp,int n) {     char *s1,*s2;     int t;     int i =0;     s1=temp;     s2=s1+n-1;     while(i++<7)     {        t=*s1++;        *s1=*s2--;        *s2=t;     } } void main() {     char p[8]="1234567";     fun(p,strlen(p));     puts(p); }   题目还有问题，结果估计是 1111111   还有一些我答上来了！你猜是什么题？ 7、为何申请百度？百度成功在与什么？   8、怎样才能成为优秀的测试工程师？   9、这类题都可以自己想，我就不多说了！！   最后，说一下，为何30秒就挂了！！！^_^....   她一进门，拿者我的简历，之后对我说，你毕业比较晚，是吧？ 我说“是”，今年才考上研，得08年才能毕业。 之后，她又说，你打算实习几个月，我说“二个月吧”。这时，她笑了笑，对我说：“着业 太短了，我们要求尽可能长时间的实习，且，主要面向即将毕业的同学，你看。。。” 这下每戏了，后来我们简短的谈了一下，之后就走了。（她比较和蔼，临走的时候，给我很 好的印象）。   值得一体的是，我笔试在“采云归”房间，就我一个人，笔试过程中，哪个为我登记的 PPMM给我那杯水，之后，见屋子里的两个椅子多余，就将它们抬了出去（比较费力），我当 时，被笔试弄晕了，早知道，我就帮她一起抬了^_^!!!如果有高手看到的话，请支一下招， 告诉小弟以后遇到这种事情该怎么办？？顺便问一下，以后，我和这个MM还有戏吗？？？   回来后受打击了，正巧房东养了4个小王八，于是我开始玩王八解闷。。。   1.实现 void delete_char(char * str, char ch);  把str中所有的ch删掉   void delete_char(char * str, char ch) {     char *newstr = (char *)malloc(strlen(str)+1);     char *str_p = str;     char *newstr_p = newstr; // 如果没有这两个的话， while 后面的指针就出错了     while(*str_p)     {        if(*str_p == ch)            str_p++;        else            *newstr_p++ = *str_p++;     }     *newstr_p = '/0';     strcpy(str, newstr);     free(newstr); } 2.把字符串S中所有A子串换成B,这个没给函数原型   3.搜索引擎的日志要记录所有查询串,有一千万条查询,不重复的不超过三百万  要统计最热门的10条查询串. 内存<1G. 字符串长 0-255  (1) 主要解决思路 //具体用词和原题不大一样  (2) 算法及其复杂度分析   4.有字典,设计一个英文拼写纠正算法 (1) 思想 (2) 算法及复杂度 (3) 改进   5. { aaa, bb, ccc, dd }, { bbb, ff }, { gg } 等一些字符串的集合  要求把交集不为空的集合并起来,如上例会得到 { aaa, bb, ccc, dd, ff }, {gg} (1)    思想 (2) 算法及复杂度 (3) 改进   下午去百度笔试,考题有二叉搜索树和堆   1。编程：

用C语言实现一个revert函数，它的功能是将输入的字符串在原串上倒序后返回。   void revert(char * str) {     int length = strlen(str);     char temp;     for(int i = 0; i < length/2; i++)     {        temp = *(str + i);        *(str + i) = *(str + length - 1 - i);        *(str + length - 1 - i) = temp;     } }

2 。编程：

                  用C语言实现函数void * memmove(void *dest,const void *src,size_t  n)。memmove                   函数的功能是拷贝src所指的内存内容前n个字节 到dest所指的地址上。 void * memmove(void * dest,const void *src,size_t count) {     char *tmp, *s;       if (dest <= src) {//dest 在前面，故 dest 头不可能覆盖 src 尾        tmp = (char *) dest;        s = (char *) src;        while (count--)            *tmp++ = *s++;     }     else {//dest 在后面， dest 头可能覆盖 src 尾，造成 src 没有结束符         tmp = (char *) dest + count;        s = (char *) src + count;        while (count--)            *--tmp = *--s;     }       return dest; }

3 英文拼写纠错：

                  在用户输入英文单词时，经常发生错误，我们需要对其进行纠错。假设已经有一个包含了正确英文单词的词典，请你设计一个拼写纠错的程序。

                  （1）请描述你解决这个问题的思路；

                  （2）请给出主要的处理流程，算法，以及算法的复杂度；

                  （3）请描述可能的改进（改进的方向如效果，性能等等，这是一个开放问题）。                   (1) 思路 :

                   字典以字母键树组织，在用户输入同时匹配

                  (2)

                   流程 :

                   每输入一个字母：

                   沿字典树向下一层，

                  a ）若可以顺利下行，则继续至结束，给出结果；

                  b) 若该处不能匹配，纠错处理，给出拼写建议 , 继续至 a ）；                    算法 :

                  1. 在字典中查找单词

                   字典采用 27 叉树组织 , 每个节点对应一个字母 , 查找就是一个字母

                   一个字母匹配 . 算法时间就是单词的长度 k.                   2. 纠错算法

                   情况 : 当输入的最后一个字母不能匹配时就提示出错 , 简化出错处理，动态提示

                   可能 处理方法 :

                  (a) 当前字母前缺少了一个字母：搜索树上两层到当前的匹配作为建议；

                  (b) 当前字母拼写错误：当前字母的键盘相邻作为提示；（只是简单的描述，可                    以有更多的）

                   根据分析字典特征和用户单词已输入部分选择 (a),(b) 处理

                   复杂性分析：影响算法的效率主要是字典的实现与纠错处理

                   （ a ）字典的实现已有成熟的算法，改进不大，也不会成为瓶颈；

                  (b) 纠错策略要简单有效 , 如前述情况，是线性复杂度；                   (3) 改进

                   策略选择最是重要，可以采用统计学习的方法改进。

 4 寻找热门查询：

                  搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串                   的长度为1-255字节。假设目前有一千万个记录，

                  这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个                   。一个查询串的重复度越高，说明查询它的用户越多，

                  也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。

                  （1）请描述你解决这个问题的思路；

                  （2）请给出主要的处理流程，算法，以及算法的复杂度。 1G就是十亿          (1) 思路：

                   用哈希做

                  (2)

                   首先逐次读入查询串，算哈希值，保存在内存数组中，同时统计频度

                   （注意值与日志项对应关系）

                   选出前十的频度，取出对应的日志串，简单不过了。                    哈希的设计是关键。

5 集合合并：

                  给定一个字符串的集合，格式如：

                  {aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}

                  要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应                   输出

                  {aaa bbb ccc ddd hhh}，{eee fff}， {ggg}

                  （1）请描述你解决这个问题的思路；

                  （2）请给出主要的处理流程，算法，以及算法的复杂度

                  （3）请描述可能的改进（改进的方向如效果，性能等等，这是一个开放问题）。

        要求将其中交集不为空的集合合并   要求合并完成后的集合无交集 这两个要求只要 1 满足了， 2 就自然满足了。   方法 1 ：把每个集合用 vector<vector<char> > 表示，比较两个集合里面 vector<char> 是否相等 ( 是否交集不为空，有相同元素 ) ，如果有相同集合就合并。这个就是每个集合都和其后面的集合比较，复杂度为 o(n2) 。   方法 2 ：把每个集合都遍历一遍，找出所有集合的所有元素 ( 不重复 ). 然后建立一张表，记录各个元素在每个集合的出现情况，行代表元素，列代表集合，出现则相应位为 1 ，否则为 0 。表建立完成后，把每行有多个 1 的  1 所在列的集合合并就可以了。   时间复杂度： 遍历 O(n), 写表 O(n), 最后查表合并 o(n) ，总的复杂度为 O(n) 。             Map的用法     map<string ,int> a;     string b("asdf");     a.insert(map< string,int >::        value_type(b,3));     string c("sdf");     a.insert(map< string,int >::        value_type(c,4));     map<string, int>::iterator i;     for(i = a.begin(); i != a.end(); i++)        cout << (*i).first << " " << (*i).second << endl;     a.erase(b);     for(i = a.begin(); i != a.end(); i++)        cout << (*i).first << " " << (*i).second << endl;   我的方法： 先遍历集合，建立一个 hash 表， hash 表的键为集合中的字符串，值表示为包含此字符串的集合的序号，比如说集合 1 和 3 包含此元素，值就是 00001010 ，复杂度为 o （ n ） 然后遍历这个 hash 表，将这些值进行 & 运算，结果为 0 时就跳过，结果不为 0 时保存此结果，然后从 hash 表中删除这个条目，遍历完一遍后得到第一个合并后的集合的序号，就进行合并。此为 o(m) 然后再次遍历直到 hash 表为空为止。复杂度合并后集合数乘上 hash 表长度 其实也可以通过一次遍历 hash 表来确定，建立一个链表， a[0] 为保存 & 不为 0 的值， a[1] 保存 & 为 0 的值，然后将 a[] 中的数字都与 hash 表的值做 & 运算，都为 0 时将这个值加入链表，不为 0 时，将结果保存到 a[i] ，有可能还要合并，不过这样复杂度也不好算  “已知一个字串由GBK汉字和ansi编码的数字字母混合组成，编写C语言函数实现从中去掉所有ansi编码的的数字和字母（包括大小写).要求在原字串上返回结果。int filter_ansi(char* gbk_string);注：汉字的GBK编码范围是0x8140 - 0xFEFE。”   char * filter_ansi(char* gbk_string) {     assert(gbk_string!=NULL);     char *src;     char *dst;     src = dst = gbk_string;     while(*src)     {        if(*src & 0x80)        {            *dst++ = *src++;            *dst++ = *src++;        }        else            src++;     }     *dst = '/0';     return gbk_string; }