我周围有人面腾讯，不得不说腾讯的面试官还是不一样，有的公司面试就是走个流程，腾讯的面试问的问题确实不一样。
1.看了你一个web小管理系统，会问你为什么要用mysql，换别的数据库行不行，优点和缺点分别是什么(不仅是数据库dbms，所有的工具都来了个灵魂铐问，其实这种作业一般是课程设计，这门课教什么学生就用什么，普通学生当初做的时候不太会考虑这个问题，考查知识的广度了)。
2.接着问，如果让你重构这个项目，你应该怎么优化，如果访问量特别大呢(这个真没考虑过，学生写的玩具能有多少访问量，会超过2位数吗，当初写web服务器的时候用过apache的ab，总不能用那个测试吧？)
3.然后问了算法题，这个算法题明显不是为了出题而出题，常见到没人会关心，但认真思考以后就会发现其实没有那么简单。
给一个母字符串和一个子字符串，子字符串中包含两种字符*和*，其中*可以匹配任意长度的任意字符，?可以匹配任意一个字符，问子串可以匹配母串吗。
样例:
abab可以匹配ab*
abab可以匹配?bab
abab不可以匹配?aba
这个个非常常见的问题，类似于在shell中常用的通配符。
在学过编译原理后，我的第一反应其实是有限状态机。但面试官当时的提示是动态规划。
我想了一个晚上以后把题目做了出来。代码附在最后。
解出来了以后真的是感叹数据结构与算法就在我们身边。
这个问题和编译原理所想要解决的问题有相似却又有不同。
编译原理的子串是固定的，词法分析器想要分析的词法都会提前写好正规式，有限状态机的分析矩阵也可以提前生成，到时候面对的是固定的子串，源源不断输入母串并执行判定。而且编译器的一个重要的职责就是报错，有限状态机可以清楚的告诉你在哪一步出错了，报错信息详细是基本要求。
但这个题目子串是变化的，每次对一个子串构建状态机显然时间和空间开销太大，而成果却只用来判定一次，这是不划算的。而且这个题目不需要报错。
程序要求的不同就得设计不同的算法。这个题目就得抛弃状态机这种算法转而寻求更为高效的算法。事实上你会发现这个题目和最长公共子序列的基本思想完全一样。
说实话，看到了腾讯的面试有点把我吓着了，我怀疑有多少硕士能完美地通过腾讯的所有面试提问(或者是我井底之蛙？)。
#include<stdio.h>
#include<string.h>
#define N 1000
int main(void)
{
char a[N],b[N];
// * a
while(EOF!=scanf("%s%s",a,b))
{
int i,j,res[N][N];
int lena = strlen(a), lenb = strlen(b);
for(i=0;i<lena;i++)
{
for(j=0;j<lenb;j++)
{
// 1 = yes , 0 = no
if(0==i && 0==j)
{
if('*'==a[i])
res[i][j] = 1;
else if('?'==a[i])
res[i][j] = 1;
else if(b[j]==a[i])
res[i][j] = 1;
else
res[i][j] = 0;
}
else if(0==i)
{
if('*'==a[i])
res[i][j] = 1;
else
res[i][j] = 0;
}
else if(0==j)
res[i][j] = 0;
else
{
if('*'==a[i])
res[i][j] = 1;
else if('?'==a[i])
res[i][j] = res[i-1][j-1];
else if(b[j]==a[i])
res[i][j] = res[i-1][j-1];
else
res[i][j] = 0;
}
}
}
printf("%s\n",res[lena-1][lenb-1]?"YES":"NO");
}
return 0;
}
网友评论