雅虎2015校招笔试-k6k4.com

雅虎笔试的难度和强度还是挺大的，英文试题，允许中英文作答。

选择题里面难度最大的是一道是考察贝叶斯公式的题。题目说的是一种疾病，在100000人会中有1个人患这种病，而这种病的诊断正确率为99%。一个人诊断结束后被告知患了该种病，求他真正患该种病的概率多大。

B0 =患病，B 1 =没有患病，A=诊断出患病

P(B0 |A ) =P(B 0 )*P(A|B 0 )/(P(B 0 )*P(A|B 0 )+P(B 1 )*P(A|B 1 ))

=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。

最正统的解法就是求递推公式了。

四道编程题：

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; 
}

2. 有4k+2个整数，其中k个整数出现了4次，一个整数出现了2次。找出出现2次的整数。

最笨最笨的办法就是用hash表记录每个整数出现的次数，这样干估计只能拿点幸苦分了。

比较通用的办法就是用32个整形变量bits_count[32]记录每一个bit上1出现的次数，然后选出bits_count[i]%4结果为2的bits组成一个整数，就是出现2次的整数。

高级一点的办法就是借用位运算，消除出现次数为4的整数倍的bit位。

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; 
}

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; 
}

最坏情况是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; 
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; 
     } 
}

个人资料

onion
等级：6
文章：51篇
访问：4.2w
排名： 12

推荐圈子

雅虎笔试面试圈