阿裡巴巴筆試題選解
--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 <stdio.h>
#include <stdlib.h>
#define N 7
int main()
{
int arr[N] = {4, 1, 5, 9, 9, 7, 10};
int iter = 0;
int cnt = 0;
for(iter = 0; iter < N ; iter += 2)
{
if(++cnt && arr[iter] > arr[iter + 1] )
{
int temp = arr[iter];
arr[iter] = arr[iter + 1];
arr[iter + 1] = temp;
}
}
int myMin = arr[0];
for(iter = 2; iter < N ; iter += 2)
{
if(++cnt && arr[iter] < myMin)
{
myMin = arr[iter];
}
}
int myMax = arr[1];
for(iter = 3; iter < N; iter += 2)
{
if(++cnt && arr[iter] > myMax)
{
myMax = arr[iter];
}
}
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;
}
上面的算法比較次數基本上已經是最優了，但是有朋友提出這樣的顧慮，在極端的情況下，每次都做交換，可能會導致程序開銷很大，這樣的顧慮是對的，其實在上面的算法的基礎上，可以不做交換就能找到最大值和最小值。
接下來請看第2頁精彩內容：http://www.linuxidc.com/Linux/2013-10/90812p2.htm