今天去微軟面試...緊張ing...
中午11:00從學校出發(fā)..1號線轉5號線然后打D到上海科技園..到了以后不知道怎么聯(lián)系面試官...囧...打電話問了下DY...然后1個mm來帶我去了某個空會議室...等了大概10min...一個胖胖的面試官進來了...先問了我一些項目經(jīng)歷之類的...然后問我會玩24點嗎？我說會。然后讓我算6,6,10,10....算不出來（后來發(fā)現(xiàn)這個根本沒有答案- -||）然后問我要怎么寫個程序來出24點的難題.....
思考中.我說如果4個數(shù)可以化成2個數(shù)想乘積等于24，這四個數(shù)應該算是比較簡單的..然后他又提醒我從數(shù)學的角度定義..哎..還是想不出..后來才其實這個題目ms是開放性的....當時腦抽了..早知道和他胡扯一堆可以自圓其說就好了..然后他讓我做了一道比較水 的字符串的題目..當場在白板上寫代碼..就是給一個字符串，這個字符串由有空格隔開的單詞組成，處理這個字符串，使輸出的字符串相鄰的單詞不重復；如輸入what is is this,輸出what is this，實在是ACM的水題..但是還是出現(xiàn)了一些腦殘的錯誤,,回來重新敲了下代碼
#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有很多細節(jié)問題..然后我又寫了一個DP的做法..但是復雜度太高了..然后面試官讓我我改線性的做法..ms怎么改都有點問題..我只好想了一個優(yōu)化的方法..大概混過去了..
回來問了天哥..改了下，可以先處理一下字符串，如將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 閱讀(207)
評論(0) 編輯 收藏 引用