雅虎2015校招笔试

雅虎笔试的难度和强度还是挺大的,英文试题,允许中英文作答。
选择题里面难度最大的是一道是考察贝叶斯公式的题。题目说的是一种疾病,在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; 
     } 
} 


猜你感兴趣的圈子:
雅虎笔试面试圈
分享本文