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） 对字典的使用读操作很大，通常每秒有上千次请求，几乎没有写入需求。
请设计一个字典服务系统，当请求是两个词的搭配时，能够快速返回搭配的相关信息。请使用尽可能少的资源，并估算出需要使用的机器资源。