阿里巴巴筆試題選解
--9月22日，阿里巴巴北郵站
小題：1、有三個結點，可以構成多少種樹形結構？
2、一副牌52張(去掉大小王)，從中抽取兩張牌，一紅一黑的概率是多少？
程式設計題：
3、設計乙個最優演算法來查詢一n個元素陣列中的最大值和最小值。已知一種需要比較2n次的方法，請給乙個更優的演算法。情特別注意優化時間複雜度的常數。
4、已知三個公升序整數陣列a[l], b[m]和c[n]。請在三個陣列中各找乙個元素，是的組成的三元組距離最小。三元組的距離定義是：
假設a[i]、b[j]和c[k]是乙個三元組，那麼距離為:
distance = max(|a[ i ] – b[ j ]|, |a[ i ] – c[ k ]|, |b[ j ] – c[ k ]|)
請設計乙個求最小三元組距離的最優演算法，並分析時間複雜度。
5、在黑板上寫下50個數字：1至50.在接下來的49輪操作中，每次做如下動作：
選取兩個黑板上的數字a和b，擦去，在黑板上寫|b - a|。請問最後一次動作之後剩下數字可能是什麼？為什麼？
題解：(題解非官方，僅供參考，有錯誤的地方望指正！謝謝)
1、有三個結點的，可以構成多少個種樹形結構？
解：應該是5種；
2、一副牌52張(去掉大小王)，從中抽取兩張牌，一紅一黑的概率是多少？
考察概率論知識
解法一： 52張牌從中抽兩張，就是 c(2,52)種情況，一紅一黑是c(1,26) * c(1,26)種
p = [c(1,26) * c(1,26) ] / c(2,52) = 26 * 26 / (26 * 51) = 26/51
解法二： 全為黑或者全為紅是c(2,26)種情況，由於是黑和紅兩種，所以要乘以2
p = 1 - c(2,26) / c(2,52) - c(2,26) / c(2,52) = 1 - 2 * (26 * 25)/(51 * 52) = 1 - 25/51 = 26/51
3、設計乙個最優演算法來查詢一n個元素陣列中的最大值和最小值。已知一種需要比較2n次的方法，請給乙個更優的演算法。情特別注意優化時間複雜度的常數。
解：把陣列兩兩一對分組，如果陣列元素個數為奇數，就最後單獨分乙個，然後分別對每一組的兩個數比較，把小的放在左邊，大的放在右邊，這樣遍歷下來，總共比較的次數是n/2次；在前面分組的基礎上，那麼可以得到結論，最小值一定在每一組的左邊部分找，最大值一定在陣列的右邊部分找，最大值和最小值的查詢分別需要比較n/2次和n/2次；這樣就可以找到最大值和最小值了，比較的次數為
n/2 * 3= (3n)/2 次
如圖會更加清晰：
**實現：
#include
#include
#define n 7
int main()
; int iter = 0;
int cnt = 0;
for(iter = 0; iter < n ; iter += 2)
}int mymin = arr[0];
for(iter = 2; iter < n ; iter += 2)
}int mymax = arr[1];
for(iter = 3; iter < n; iter += 2)
}if(n % 2 != 0 && ++cnt && mymax < arr[n - 1]) mymax = arr[n - 1];
printf("min is %d\n", mymin);
printf("max is %d\n", mymax);
printf("compare times is %d", cnt);
return 0;
}上面的演算法比較次數基本上已經是最優了，但是有朋友提出這樣的顧慮，在極端的情況下，每次都做交換，可能會導致程式開銷很大，這樣的顧慮是對的，其實在上面的演算法的基礎上，可以不做交換就能找到最大值和最小值。
第3題改進的演算法：
依舊把陣列兩兩一組分配，不做交換操作，設定乙個最大值max和最小值min，依次和每一組的兩個資料做比較，把較大的值給max,較小的值給min，遍歷一次就能找到陣列的最大值和最小值。
示例：陣列為,經過第一組比較得到max = 4，min = 1，其中比較了3次；,經過第二組比較得到max = 9，min = 1，其中比較了3次；……到最後max = 10，min = 1；比較次數是3 * n/2 = (3n)/2，比較次數沒有改變！**實現不難，就不貼了
4、已知三個公升序整數陣列a[l], b[m]和c[n]。請在三個陣列中各找乙個元素，是的組成的三元組距離最小。三元組的距離定義是：
假設a[i]、b[j]和c[k]是乙個三元組，那麼距離為:
distance = max(|a[ i ] – b[ j ]|, |a[ i ] – c[ k ]|, |b[ j ] – c[ k ]|)
請設計乙個求最小三元組距離的最優演算法，並分析時間複雜度。
解：這道題目有兩個關鍵點：
第乙個關鍵點：max =（|x1+y1-x2-y2|+|x1-y1-(x2-y2)|）/2 --公式（1）
我們假設x1=a[ i ]，x2=b[ j ]，x3=c[ k ]，則
distance = max(|x1– x2|, |x1–x3|, |x2–x3|) = max( max(|x1– x2|, |x1–x3|) , |x2–x3|) --公式（2）
根據公式（1），max(|x1– x2|, |x1–x3|) = 1/2 ( |2x1–x2–x3| + |x2–x3|)，帶入公式（2），得到
distance= max( 1/2 ( |2x1–x2–x3| + |x2–x3|) , |x2–x3| )
=1/2 * max( |2x1–x2–x3| , |x2–x3| )+ 1/2*|x2–x3|//把相同部分1/2*|x2–x3|分離出來
=1/2 * max( |2x1– (x2+ x3)| , |x2– x3| )+ 1/2*|x2– x3|//把(x2+ x3)看成乙個整體，使用公式（1）
=1/2 * 1/2 *((|2x1– 2x2| + |2x1– 2x3|)+ 1/2*|x2– x3|
=1/2 *|x1– x2| + 1/2 * |x1–x3| + 1/2*|x2– x3|
=1/2 *(|x1– x2| + |x1–x3| + |x2– x3|)//求出來了等價公式，完畢！
第二個關鍵點：如何找到(|x1– x2| + |x1–x3| + |x2– x3|) 的最小值，x1，x2，x3，分別是三個陣列中的任意乙個數，這一題，我只是做到了上面的推導，後面的演算法設計是由csdn上的兩個朋友想出來的方法，他們的csdn的id分別為 「雲夢澤」和 「shuyechengying」.
演算法思想是：
用三個指標分別指向a,b,c中最小的數，計算一次他們最大距離的distance ，然後在移動三個數中較小的陣列指標，再計算一次，每次移動乙個，直到其中乙個陣列結束為止，最慢(l+ m + n)次，複雜度為o(l+ m + n)
**如下：
#include
#include
#include
#define l 3
#define m 4
#define n 6
int mymin(int a, int b, int c)
int solvingviolence(int a, int b, int c)
; int sum = 0;
for(i = 0; i < l; i++)
}}}// printf("the min is %d\n", minabc);
// printf("the three number is %-3d%-3d%-3d\n", a[store[0]], b[store[1]], c[store[2]]);
return minsum;
}int mindistance(int a, int b, int c)
//a[i]最小,移動i
阿里巴巴面試題
1.兩個物件值相同 x.equals y true 但卻可有不同的hash code,這句話對不對？為什麼？2.gc是什麼？為什麼要有gc？3.請簡要描述一下j2ee應用中的class loader的層次結構？4.寫一段 實現銀行轉帳功能 介面定義如下 public inte ce itransfe...
阿里巴巴和華為筆試和面試題
軟體測試工程師面試題 阿里巴巴旗下各公司測試筆試和面試如下 支付寶 面試題 講述一下自己最熟悉的乙個專案是怎麼做的？具體用什麼方法和測試工具？簡述一下整個專案的測試流程和bug管理流程？bug描述中都包括那些內容？講述乙個bug的生命週期？講述自己在專案中發現最有意義的乙個bug，是什麼導致出現這個...
阿里巴巴面試經驗
阿里巴巴這個公司想必大家都知道，無論哪個專業的同學。我爸爸媽媽這一輩都還認識馬雲呢，爺爺那一輩就只認識 了，呵呵。不知道是馬雲是成就了阿里巴巴，還是阿里巴巴成就了馬雲，反正提起阿里巴巴就提到馬雲，提到馬雲就必然談到他的阿里巴巴。阿里巴巴這個公司固然是很多應屆大學生的嚮往之地。我呢，經常混跡在網際網路...