雅虎2015校招筆試
來源：程序員人生 發布時間：2014-09-29 23:52:27 閱讀次數：3240次
雅虎筆試的難度和強度還是挺大的，英文試題，允許中英文作答。
選擇題里面難度最大的是一道是考察貝葉斯公式的題。題目說的是一種疾病，在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;
}
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;
}
大神給出了終極版本。
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;
}
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
