雅虎2015校招面试总结
来源:程序员人生 发布时间:2014-09-29 15:32:48 阅读次数:3628次
时间:2014/9/26 下午1:30-5:00 地点:清华同方科技广场D座11层
一面:基本上就是跟面试官闲聊,说了一会我的RTB大赛,然后考了一道算法题。题目是,对一个0和1组成的字符串加密,加密方法是encode[i] = code[i-1]+code[i]+code[i+1]。比如0110111加密后的结果是1222232。写一个算法,输入为加密后的串,输出是解密的01串。
自己想了一会,并没有太好的思路,最后在面试官提示下写出了代码,但还是有错。回来写了份代码,很轻松,面试的时候一直在纠结怎么判断解码是否正确,其实很简单,既然源码是0和1,如果解密的结果为0/1,那就是对的,如果不为0/1,那就是错了。
然后问了问TCP三次握手,Linux创建的子进程与父进程的关系,进程、线程如何同步,PV原子操作,如何把Linux命令行结果写入文件。基本上都能说上来,有些答得不完整。
public static byte[] decode(byte[] encode)
{
int N = encode.length;
byte[] code = new byte[N];
if(N==0)
return code;
code[0] = 2;
if(N==1)
{
if(encode[0]==1||encode[0]==0)
code[0] = encode[0];
return code;
}
if(encode[0]<2)
{
code[0] = 0;
code[1] = encode[0];
for(int i=2;i<N;i++)
{
code[i] = (byte) (encode[i-1] - code[i-2] - code[i-1]);
if(code[i]!=0&&code[i]!=1)
{
code[0] = 2;
break;
}
}
}
for(int i:code)
System.out.print(i+" ");
System.out.println();
code[0] = 1;
code[1] = (byte) (encode[0]-1);
for(int i=2;i<N;i++)
{
code[i] = (byte) (encode[i-1] - code[i-2] - code[i-1]);
if(code[i]!=0&&code[i]!=1)
{
code[0] = 2;
break;
}
}
for(int i:code)
System.out.print(i+" ");
return code;
}
二面:面试官一上来也是问我的RTB大赛。然后就面算法,第一道题是把字符串中连续的数字串加上1,比如"hih#32wih459"的结果是"hih#33wih460"。自己先是会错意了,以为是把连续的数字字符串的尾子符的值加1,写了一份代码,面试官看了后说题意理解错了,然后又写了份代码,把连续数字串parse成int,加上1后再toString()替换掉原来的数字串。面试官指出int可能会溢出,自己又说出了一种改进方法。回来写了一下代码,还真不简单。
public static String stringNumIncrease(String s)
{
StringBuilder str = new StringBuilder("");
StringBuilder num = new StringBuilder("");
StringBuilder chars = new StringBuilder("");
for(int i=0;i<s.length();i++)
{
if(s.charAt(i)>='0'&&s.charAt(i)<='9')
{
if(!chars.toString().equals(""))
{
str.append(chars);
chars.delete(0, chars.length());
}
num.append(s.charAt(i));
}
if(s.charAt(i)<'0'||s.charAt(i)>'9'||i==s.length()-1)
{
if(!num.toString().equals(""))
{
byte carry = 1;
for(int k=num.length()-1;k>=0;k--)
{
int tmp = num.charAt(k)-'0';
if(tmp+carry<=9)
{
num.setCharAt(k, (char) (num.charAt(k)+carry));
break;
}
else
{
num.setCharAt(k, '0');
if(k==0)
num.insert(0, '1');
}
}
str.append(num);
num.delete(0, num.length());
}
if(s.charAt(i)<'0'||s.charAt(i)>'9')
chars.append(s.charAt(i));
}
}
str.append(chars);
return str.toString();
}
接着问了第二道算法题,题目是:一个字符串,可能由n(n>=2)个重复的子串组成。写一个算法,判断一个字符串能否被分割成n个相同的子串(最好找出最小的子串)。当时并没有考虑到子串的长度必须是n的因子,回来后在同学的提示下,得出了下面这个算法,还不确定是否是最优的。
public static String stringSplit(String s)
{
for(int i=1;i<=s.length()/2;i++)
{
if(s.length()%i==0)
{
String tmp = s.substring(0,i);
int j=i;
for(;j<s.length();j+=i)
{
if(!s.substring(j,j+i).equals(tmp))
break;
}
if (j>=s.length())
{
return tmp;
}
}
}
return "";
}
生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠