雅虎2015校招笔试
栏目：互联网时间：2014-09-29 23:52:27
雅虎笔试的难度和强度还是挺大的，英文试题，允许中英文作答。
选择题里面难度最大的是一道是考察贝叶斯公式的题。题目说的是一种疾病，在100000人会中有1个人患这种病，而这种病的诊断正确率为99%。一个人诊断结束后被告知患了该种病，求他真正患该种病的概率多大。
B0=患病，B1=没有患病，A=诊断出患病
P(B0|A)=P(B0)*P(A|B0)/(P(B0)*P(A|B0)+P(B1)*P(A|B1))
=1/100000*99/100/(1/100000*99/100+99999/100000*1/100)
=99/100098，近似1/1000
填空题里面难度最大的是求Ackerman函数值。
Ackerman函数的定义为：
{ n+1; m=0,n>0
A(m,n) = { A(m-1,1); n=0,m>0
{ A(m-1,A(m,n-1)) n>0,m>0
求Ackerman(3,8)。
求函数值代码如下，Ackerman(3,8)=2045。
public static int Ackerman(int m,int n)
{
if(m==0)
return n+1;
if(n==0)
return Ackerman(m-1,1);
return Ackerman(m-1,Ackerman(m,n-1));
}
最正统的解法就是求递推公式了。
四道编程题：
1. 给定数组A[1...n]，返回数组B[1...n]，
其中，B[i] = A[1]*A[2]...A[i-1]*A[i+1]...A[n]。
不能使用除法，O(n)的时间复杂度，O(1)的空间复杂度。
这道题不难，不细说了，代码就很直白。
public static int[] multiply(int[] A)
{
int[] B = new int[A.length];
if(A.length==0)
return B;
B[0] = 1;
for(int i=1;i<A.length;i++)
{
B[i] = B[i-1]*A[i-1];
}
int suf = 1;
for(int i=A.length-2;i>=0;i--)
{
suf *= A[i+1];
B[i] *= suf;
}
return B;
}
{
int[] B = new int[A.length];
if(A.length==0)
return B;
B[0] = 1;
for(int i=1;i<A.length;i++)
{
B[i] = B[i-1]*A[i-1];
}
int suf = 1;
for(int i=A.length-2;i>=0;i--)
{
suf *= A[i+1];
B[i] *= suf;
}
return B;
}
2. 有4k+2个整数，其中k个整数出现了4次，一个整数出现了2次。找出出现2次的整数。
最笨最笨的办法就是用hash表记录每个整数出现的次数，这样干估计只能拿点幸苦分了。
比较通用的办法就是用32个整形变量bits_count[32]记录每一个bit上1出现的次数，然后选出bits_count[i]%4结果为2的bits组成一个整数，就是出现2次的整数。
高级一点的办法就是借用位运算，消除出现次数为4的整数倍的bit位。
这个是我的一个初级版本。用了4个临时变量。
public
static int twosInFours(int[] a)
{
int ones=0,twos=0,threes=0,fours=0;
for(int i=0;i<a.length;i++)
{
threes &= ~fours;
twos &= ~fours;
ones &= ~fours;
fours = (threes&a[i]);
threes ^= (twos&a[i]);
twos ^= (ones&a[i]);
ones ^= a[i];
}
return twos;
{
int ones=0,twos=0,threes=0,fours=0;
for(int i=0;i<a.length;i++)
{
threes &= ~fours;
twos &= ~fours;
ones &= ~fours;
fours = (threes&a[i]);
threes ^= (twos&a[i]);
twos ^= (ones&a[i]);
ones ^= a[i];
}
return twos;
}
大神给出了终极版本。
public static int twosInFoursFinal(int[] a)
{
int flag1 = 0,flag2 = 0;
for(int i=0;i<a.length;i++)
{
flag2 ^= flag1&a[i];
flag1 ^= a[i];
}
return flag2;
}
{
int flag1 = 0,flag2 = 0;
for(int i=0;i<a.length;i++)
{
flag2 ^= flag1&a[i];
flag1 ^= a[i];
}
return flag2;
}
3. matrix是一个按行递增，按列递增的矩阵。给定元素，判断该元素在矩阵中是否存在。分析算法的时间复杂度。
1 3 5 7 9
2 4 6 8 10
5 7 8 10 15
6 8 10 11 17
public static boolean targetLocate(int[][] matrix,int target)
{
if(matrix==null||matrix.length==0||matrix[0].length==0)
return false;
int rows = matrix.length,columns = matrix[0].length;
int rdown = 0, rup = rows-1;
while(rdown<rows&&matrix[rdown][columns-1]<target)
rdown++;
while(rup>=0&&matrix[rup][0]>target)
rup--;
if(rdown>rup)
return false;
for(int i=rdown;i<=rup;i++)
{
for(int j=0;j<columns;j++)
{
if(matrix[i][j]==target)
return true;
}
}
return false;
}
{
if(matrix==null||matrix.length==0||matrix[0].length==0)
return false;
int rows = matrix.length,columns = matrix[0].length;
int rdown = 0, rup = rows-1;
while(rdown<rows&&matrix[rdown][columns-1]<target)
rdown++;
while(rup>=0&&matrix[rup][0]>target)
rup--;
if(rdown>rup)
return false;
for(int i=rdown;i<=rup;i++)
{
for(int j=0;j<columns;j++)
{
if(matrix[i][j]==target)
return true;
}
}
return false;
}
最坏情况是O(M*N)。
4.一个老鼠对象包含两个属性：体重和速度。输入一个老鼠对象的序列，找出一个按体重升序、速度降序排列的最大子集。这是一个最大上升子序列问题。 常规解法的时间复杂度是O(n^2)，使用二分查找可使时间复杂度降到O(nlog(n))。
public static Mice[] maxRiseSubSeq(Mice[] M)
{
Arrays.sort(M,new MiceComparator());
int[] dp = new int[M.length];
dp[0] = 1;
int gmax = 0;
for(int i=1;i<M.length;i++)
{
int max = 0;
for(int j=0;j<i;j++)
{
if(dp[j]>dp[max]&&M[j].speed>M[i].speed)
{
max = j;
}
}
dp[i] = dp[max] + 1;
if(dp[i]>dp[gmax])
gmax = i;
}
ArrayList<Mice> result = new ArrayList<>();
int pre = gmax;
result.add(M[gmax]);
for(int i=gmax-1;i>=0;i--)
{
if(M[i].speed>M[pre].speed)
{
result.add(0, M[i]);
pre = i;
}
}
Mice[] m = new Mice[result.size()];
for(int i=0;i<m.length;i++)
m[i] = result.remove(0);
return m;
{
Arrays.sort(M,new MiceComparator());
int[] dp = new int[M.length];
dp[0] = 1;
int gmax = 0;
for(int i=1;i<M.length;i++)
{
int max = 0;
for(int j=0;j<i;j++)
{
if(dp[j]>dp[max]&&M[j].speed>M[i].speed)
{
max = j;
}
}
dp[i] = dp[max] + 1;
if(dp[i]>dp[gmax])
gmax = i;
}
ArrayList<Mice> result = new ArrayList<>();
int pre = gmax;
result.add(M[gmax]);
for(int i=gmax-1;i>=0;i--)
{
if(M[i].speed>M[pre].speed)
{
result.add(0, M[i]);
pre = i;
}
}
Mice[] m = new Mice[result.size()];
for(int i=0;i<m.length;i++)
m[i] = result.remove(0);
return m;
}
class Mice{
int weight;
int speed;
public Mice(int w,int s)
{
this.weight = w;
this.speed = s;
}
}
class MiceComparator implements Comparator<Mice>{
@Override
public int compare(Mice o1, Mice o2) {
if(o1.weight<o2.weight)
return -1;
else if(o1.weight>o2.weight)
return 1;
else
return 0;
}
}
int weight;
int speed;
public Mice(int w,int s)
{
this.weight = w;
this.speed = s;
}
}
class MiceComparator implements Comparator<Mice>{
@Override
public int compare(Mice o1, Mice o2) {
if(o1.weight<o2.weight)
return -1;
else if(o1.weight>o2.weight)
return 1;
else
return 0;
}
}
------分隔线----------------------------
------分隔线----------------------------