2010百度校园招聘试题 R D-C-2
第一题 简答 (30分)
1, 定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素,要求min、push以及pop的时间复杂度都是0(1),请简要描述你的思路。 (10分)
2, 阅读代码,说明输出的含义并挑错 (10分)
问题1. 写出下列代码的运行结果的前7行并说明数列的含义。
问题2. 代码中是否有不安全的隐患?原因是?
#include <stdio.h>
#include <string.h>
const int MAX_LEN = 128;
const int MAX_LINE = 20;
int main(int argc, char* argv[])
{
char str[MAX_LEN] = "1";
char tmp_str[MAX_LEN] = "";
char buf[MAX_LEN] = "";
printf("%s\n",str);
for (int line = 1;line <= MAX_LINE;++line)
{
strcpy(tmp_str,str);
str[0] = '\0';
for (int i=0;tmp_str[i] != 0;++i)
{
char ch = tmp_str[i];
int count = 1;
for (;tmp_str[i+1] == tmp_str[i];++i)
{
++count;
}
sprintf(buf,"%d%c",count,ch);
strcat(str,buf);
}
printf("%s\n",str);
}
return 0;
}
3, 分别才要线性表、二叉平衡树和哈希表存储数据,请分析它们各有什么优劣?(10分)
第二题 算法与程序设计(40分)
1, 有一串首尾相连的珠子,总共m颗,每颗珠子都有自己的颜色,全部颜色总共有n(n<=10)种。现在要在里面截取一段,要求包含所有不同的颜色,并且长度越短越好。求如何截取。
请详细描述你的算法思路(如需要,可给出伪代码来辅助描述),并分析其时间复杂度和空间复杂度。(20分)
2, 设计一个strnumcmp函数,对比普通的strcmp函数,差别在于,当字符串中遇到数字时,以数字大小为准。对于只有其中一个字符串为数字的情况,仍然沿用原来的strcmp方式。 (20分)
举例说
strnumcmp的判定结果:”abc”<”abc#”<”abc1”<”abc2”<”abc10”<”abcd”
一般的strcmp的判定结果:”abc”<”abc#”<”abc1”<”abc10”<”abc2”<”abcd”
要求:请给出完整代码,在达到目标的情况下尽量高效,简洁。
第三题 系统设计题(30分)
在大规模数据处理中经常会用到大规模字典。现需要处理一个词搭配的字典。条件为:
1) 字典中存在的项是两个词的搭配,例如:字典中有“今天”和“晚上”是两个词,那么它们组成的搭配为“今天|晚上”和“晚上|今天”
2) 词的集合很大,约为10万量级
3) 一个词并不会和其他所有词搭配,通常只会和不超过1万个其他此搭配
4) 对字典的使用读操作很大,通常每秒有上千次请求,几乎没有写入需求。
请设计一个字典服务系统,当请求是两个词的搭配时,能够快速返回搭配的相关信息。请使用尽可能少的资源,并估算出需要使用的机器资源。