时间：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 "";
}