1.推理：24个人，每人至少养一种宠物，养鸟、狗、鱼、猫的分别为13、5、10、9人，同时养鸟和狗的2人，同时养鸟和鱼、鸟和猫、鱼和猫的各为4人，养狗的既不养猫也不养鱼。问只养一种宠物的总共几人？同时养鸟鱼猫的几人？
2.找程序的错和不足：
int test(char *value,int value_len,int flag)
{
char temp_buf[BUF_SIZE];
sprintf(temp_buf,value);
char temp_new_buf=new char[value_len];
if(flag)
{
strcat(temp_buf,”flag is true”);
printf(temp_buf);
return 1;
}
delete[] temp_new_buf;
return 0;
}

第一题：树的深度遍历，广度遍历，和非递归实现算法的特点。
第二题：一堆代码，找错误和潜在的危险。
第三题：一个有1kb内存和1mhz处理器的计算机在上面运行的程序的最长时间是多少

算法题目

1.包编译依赖问题，设计算法，能够最快的完成包的编译
2.对输入的字符串能够从中找到最大连续数字的字符串
系统设计题目

百度最常出的题目，如何在100万url处理path、属性等等。

1.简述深度优先及广度优先遍历算法，并说明非递归实现的特点
2. 程序找错，一大段。
3. 假设有一台迷你计算机，1KB的内存，1MHZ的cpu，已知该计算机执行的程序可出现确定性终止（非死循环），问如何求得这台计算机上程序运行的最长时间，可以做出任何大胆的假设。
4. 大型软件有很多组件，编译时存在复杂的依赖关系，比如N1和N2存在依赖关系，要编译N1必须先编译N2,假设存在N<1000个组件，之间存在复杂的依赖关系，但不存在依赖环，问采用怎样的算法来构建编译规则，说明算法的复杂度。
5.写一个函数 int MaxContinuNum(const char *inputstr,char *outputstr)
找出一个字符串中最长的连续数字串，返回最长数字串的长度，并将最长字符串存入Outputstr指定的地址，
如， abcd1234abd123abcd123456789, 最长连续字符串为123456789，长度为9
6.有100亿个url，要求设计一个系统，能实现url的添加、删除、更新，并能查看url的内容

1 编写一个简单的支持正则表达式的字符串匹配函数，简单的正则表达式如下：

字符 含义
c 匹配字符c
. 匹配任意一个字符
* 若一个字符后紧跟*,则匹配0个或多个此字符

函数原型如下，参数regexp是待匹配的正则字符串，text是原始字符串。如果text中包含该正则串，函数返回1，否则返回0。建议先写明解题思路，再编码。
int match(const char* regexp, const char* text);
例如：regexp: c* text:ccccc 返回1
A* Abcd 返回1
A* bbcd 返回0

思路：处理较为简单的*和。的组合。假设不出现连续多个* , 也不会出现连续多个. 有可能出现的情况是： . ; *; .*;
1）如果，出现了一个。那么，主串下标i自加， 字串j自加。如果下一个字符是*, 则找到*后面的字符，主串下标自加直到regexp[i]==字串*后面的字符为止。这时候求的是主穿中与*后面字符第一次匹配的情形，有可能后面还有匹配的情况，则在外面使用while循环，里面从主串和字串中相等的字符串后面的字符开始递归调用match函数如果后面的匹配了，又前面的已经匹配了，则整个匹配。否则，while循环寻找下个匹配的字符。循环执行。
2）如果出现了一个*, 说明这个*是单独出现的，若出现在.后面则在上面的1）中肯定处理完了。此处出现说明是单独出现，寻找*后面的字符，在主串中寻找第一个匹配的字符，另外要注意，匹配的字符前面的字符应该是相等的(*的缘故)。同1）由于可能存在多个匹配，使用while(i < strlen(regexp)) 并且循环里面利用递归match判断后面的时候匹配。
3）如果出现的既不是*有不是.那么肯定是正常字符，可以使用最笨的方法匹配，相等则i++,j++,不相等可以利用最笨的方法，i=i-j+1;j=0;也可以利用KMP算法不回溯。本人利用笨的了，呵呵。懒的把KMP弄上面来了。
算法如下：
#include

int match(const char *regexp, const char *text)
{
int len1 = strlen(regexp);
int len2 = strlen(text);

int i=0;
int j=0;
int flag;
char ch, next;
while (i < len1 && j < len2)
{
ch = text[j];
if( ch == ‘.’)
{
i++;
j++;
if( j >= len2)
{
printf(“match\n”);
return 1;
}
next = text[j];

if( next == ‘*’)
{
j++;
if(j >= len2)
{
printf(“match\n”);
return 1;
}
ch = text[j];

while( i < len1)
{
while( regexp[i] != ch && i < len1)
{
i++;
}
if( ++j < len2)
{
if(++i < len1)
{
flag = match(®exp[i], &text[j]);
if(flag == 1)
{
printf(“match\n”);
return 1;
}
}
else
{
printf(“mismatch\n”);
return 0;
}
}
else
{
printf(“match”);
return 1;
}
}
}
}
else if( ch == ‘*’)
{
ch = text[j-1];
j++;
if(j >= len2)
{
printf(“match”);
return 1;
}

next = text[j];
while( i < len1)
{
while( i {
if(regexp[i] != ch)
{
printf(“mismatch”);
return 0;
}

i++;
}

i++;
j++;
if( j >= len2)
{
printf(“match”);
return 1;
}
if( i>=len1 && (j +1 >= len2) && ( text[j] == ‘*’))//用以匹配AA A*A*等regexp短而text长并且
// text最后一个字符是*的情况
{
printf(“match”);
return 1;
}
if(i < len1)
{
flag = match(®exp[i], &text[j]);
if(flag == 1)
{
printf(“match”);
return 1;
}
}
else
{
printf(“mismatch”);
return 0;
}
}
}
else
{
if( regexp[i] == text[j])
{
i++;
j++;
if( j >= len2)
{
printf(“match”);
return 1;
}

}
else
{
i = i-j+1;
j=0;
}
}
}
}

int main()
{
const char *str1 = “AEGFBCDF”;
const char *str2 = “A.*BCD*F”;