今天去微软面试...紧张ing...
中午11:00从学校出发..1号线转5号线然后打D到上海科技园..到了以后不知道怎么联系面试官...囧...打电话问了下DY...然后1个mm来带我去了某个空会议室...等了大概10min...一个胖胖的面试官进来了...先问了我一些项目经历之类的...然后问我会玩24点吗？我说会。然后让我算6,6,10,10....算不出来（后来发现这个根本没有答案- -||）然后问我要怎么写个程序来出24点的难题.....
思考中.我说如果4个数可以化成2个数想乘积等于24，这四个数应该算是比较简单的..然后他又提醒我从数学的角度定义..哎..还是想不出..后来才其实这个题目ms是开放性的....当时脑抽了..早知道和他胡扯一堆可以自圆其说就好了..然后他让我做了一道比较水 的字符串的题目..当场在白板上写代码..就是给一个字符串，这个字符串由有空格隔开的单词组成，处理这个字符串，使输出的字符串相邻的单词不重复；如输入what is is this,输出what is this，实在是ACM的水题..但是还是出现了一些脑残的错误,,回来重新敲了下代码
#include<stdio.h>
#include<string.h>
void Noduplicate(char *str,char *res)
{
int i=0,j=0,pre=-1;
int l=strlen(str);
while(i<l)
{
if(str[i]==' ')
{
res[j++]=str[i++];
continue;
}
if(pre==-1||str[i]!=str[pre])
{
pre=i;
while(i<l&&str[i]!=' ')
{
res[j++]=str[i++];
}
}
else
{
int flag=0;
int tmp_p=pre,tmp_i=i;
while(tmp_i<l&&str[tmp_i]!=' '&&str[tmp_p]!=' ')
{
if(str[tmp_p]!=str[tmp_i])
{
flag=1;
break;
}
tmp_i++;tmp_p++;
}
if(flag)
{
pre=i;
while(str[i]!=' ')
{
res[j++]=str[i++];
}
}
else
i=tmp_i+1;
}
}
res[j]='\0';
}
int main()
{
int i,j;
char str[100],res[100];
while(gets(str)!=NULL)
{
memset(res,0,sizeof(str));
Noduplicate(str,res);
printf("%s\n",res);
}
return 0;
}
第一轮面完后又来了一个mm...进来让我自我介绍几句，就让我做题..也是比较水的字符串匹配的题目..给两个字符串是*s和*str，s由子母'*’组成，*可以表示i个*号前面的一个字符，i=0-n；str只有子母，问两个串是否相同，例如*s="AB*C",*str="ABBBBBC"，则连个字符串相同..
我先想了一个线性扫描的做法..但是ms有很多细节问题..然后我又写了一个DP的做法..但是复杂度太高了..然后面试官让我我改线性的做法..ms怎么改都有点问题..我只好想了一个优化的方法..大概混过去了..
回来问了天哥..改了下，可以先处理一下字符串，如将AB*B改为ABB*，因为两者是等价的..然后线性扫描就可以了...代码如下
#include<stdio.h>
#include<string.h>
bool ifmatch(char *s,char *str)
{
int i=0,j=0,k,pre=-1;
int s_len=strlen(s);
int str_len=strlen(str);
for(i=0;i<s_len;i++)
{
if(s[i]!='*')
pre=i;
if(s[i]=='*')
{
if(s[i+1]!='*'&&s[i+1]==s[pre])
{
k=i;
while(s[k]=='*')
k--;
k++;
char temp=s[k];
s[k]=s[i+1];
s[i+1]=temp;
}
}
}
//printf("%s\n",s);
pre=-1;
i=0;j=0;
while(i<s_len&&j<str_len)
{
if(s[i]!=str[j]&&s[i]!='*')
return false;
if(s[i]=='*')
{
while(str[j]==s[pre])
j++;
i++;
}
else
{
pre=i;
i++;j++;
}
}
if(j<str_len)
return false;
while(i<s_len)
{
if(s[i]!='*')
return false;
i++;
}
return true;
}
int main()
{
char s[200],str[200];
while(scanf("%s %s",s,str)!=EOF)
{
if(ifmatch(s,str))
printf("yes\n");
else
printf("no\n");
}
return 0;
}
只面了两轮就出来了..ms还比较水...明显比DY大牛的水....累..还是感觉比较搓...
posted on 2010-07-28 16:26
ccyy 阅读(199)
评论(0) 编辑 收藏 引用