今天去微軟面試...緊張ing...
中午11:00從學(xué)校出發(fā)..1號(hào)線轉(zhuǎn)5號(hào)線然后打D到上海科技園..到了以后不知道怎么聯(lián)系面試官...囧...打電話問(wèn)了下DY...然后1個(gè)mm來(lái)帶我去了某個(gè)空會(huì)議室...等了大概10min...一個(gè)胖胖的面試官進(jìn)來(lái)了...先問(wèn)了我一些項(xiàng)目經(jīng)歷之類的...然后問(wèn)我會(huì)玩24點(diǎn)嗎？我說(shuō)會(huì)。然后讓我算6,6,10,10....算不出來(lái)（后來(lái)發(fā)現(xiàn)這個(gè)根本沒(méi)有答案- -||）然后問(wèn)我要怎么寫(xiě)個(gè)程序來(lái)出24點(diǎn)的難題.....
思考中.我說(shuō)如果4個(gè)數(shù)可以化成2個(gè)數(shù)想乘積等于24，這四個(gè)數(shù)應(yīng)該算是比較簡(jiǎn)單的..然后他又提醒我從數(shù)學(xué)的角度定義..哎..還是想不出..后來(lái)才其實(shí)這個(gè)題目ms是開(kāi)放性的....當(dāng)時(shí)腦抽了..早知道和他胡扯一堆可以自圓其說(shuō)就好了..然后他讓我做了一道比較水 的字符串的題目..當(dāng)場(chǎng)在白板上寫(xiě)代碼..就是給一個(gè)字符串，這個(gè)字符串由有空格隔開(kāi)的單詞組成，處理這個(gè)字符串，使輸出的字符串相鄰的單詞不重復(fù)；如輸入what is is this,輸出what is this，實(shí)在是ACM的水題..但是還是出現(xiàn)了一些腦殘的錯(cuò)誤,,回來(lái)重新敲了下代碼
#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;
}
第一輪面完后又來(lái)了一個(gè)mm...進(jìn)來(lái)讓我自我介紹幾句，就讓我做題..也是比較水的字符串匹配的題目..給兩個(gè)字符串是*s和*str，s由子母'*’組成，*可以表示i個(gè)*號(hào)前面的一個(gè)字符，i=0-n；str只有子母，問(wèn)兩個(gè)串是否相同，例如*s="AB*C",*str="ABBBBBC"，則連個(gè)字符串相同..
我先想了一個(gè)線性掃描的做法..但是ms有很多細(xì)節(jié)問(wèn)題..然后我又寫(xiě)了一個(gè)DP的做法..但是復(fù)雜度太高了..然后面試官讓我我改線性的做法..ms怎么改都有點(diǎn)問(wèn)題..我只好想了一個(gè)優(yōu)化的方法..大概混過(guò)去了..
回來(lái)問(wèn)了天哥..改了下，可以先處理一下字符串，如將AB*B改為ABB*，因?yàn)閮烧呤堑葍r(jià)的..然后線性掃描就可以了...代碼如下
#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;
}
只面了兩輪就出來(lái)了..ms還比較水...明顯比DY大牛的水....累..還是感覺(jué)比較搓...
posted on 2010-07-28 16:26
ccyy 閱讀(205)
評(píng)論(0) 編輯 收藏 引用