最近老是聽到小伙伴們說一些找工作的時候筆試遇到的問題，這篇文章就是找一些阿里巴巴近幾年的筆試題及解答方法，因為個人覺得阿里的題目應(yīng)該代表目前大數(shù)據(jù)領(lǐng)域的行業(yè)水平，別的公司考的只會偏易而不會更難，當然這是在同等職位的情況下，希望對大家有所幫助。
1、有三個結(jié)點結(jié)點的，可以構(gòu)成多少個種樹形結(jié)構(gòu)？
五種結(jié)構(gòu)
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、設(shè)計一個最優(yōu)算法來查找一n個元素數(shù)組中的最大值和最小值。已知一種需要比較2n次的方法，請給一個更優(yōu)的算法。情特別注意優(yōu)化時間復雜度的常數(shù)
把數(shù)組兩兩一對分組，如果數(shù)組元素個數(shù)為奇數(shù)，就最后單獨分一個，然后分別對每一組的兩個數(shù)比較，把小的放在左邊，大的放在右邊，這樣遍歷下來，總共比較的次數(shù)是N/2次；在前面分組的基礎(chǔ)上，那么可以得到結(jié)論，最小值一定在每一組的左邊部分找，最大值一定在數(shù)組的右邊部分找，最大值和最小值的查找分別需要比較N/2次和N/2次；這樣就可以找到最大值和最小值了，比較的次數(shù)為N/2 * 3= (3N)/2 次
實現(xiàn)代碼如下：#include#include#defineN 7
4、已知三個升序整數(shù)數(shù)組a[l], b[m]和c[n]。請在三個數(shù)組中各找一個元素，是的組成的三元組距離最小。三元組的距離定義是：假設(shè)a[i]、b[j]和c[k]是一個三元組，那么距離為:Distance = max(|a[ I ] – b[ j ]|, |a[ I ] – c[ k ]|, |b[ j ] – c[ k ]|)請設(shè)計一個求最小三元組距離的最優(yōu)算法，并分析時間復雜度。
感覺和排序數(shù)組中和為給定值的兩個數(shù)字有點像，再繼續(xù)順著思路往下走，要是兩個已排序（從小到大）的數(shù)組，a[n],b[m],如何求解兩數(shù)組中差值（非負）最小的兩個點，當然暴力求解肯定是可以的，有沒有其他更好的算法呢？想想這個和排序數(shù)組中給定值的兩個數(shù)字有沒有什么關(guān)系？或者能不能從那個方法獲取思路，對，方法大致是一樣的，就是先分別取兩個數(shù)組a[n],b[m]中最小的數(shù)a[i],b[j]，計算兩個數(shù)的差值，并記錄下來currentMin，然后取min(a[i],b[j]),所在的數(shù)組，
intminDifference(int*arrayOne,size_tcntOne,int*arrayTwo,size_tcntTwo)
5、有N-1個群眾和1個明星，所有的群眾都認識該明星，但明星不認識任何一個群眾，群眾之間是否認識未知。假如你是一個機器人，具有詢問一個人是否認識另外一個人的功能，請設(shè)計一個最佳算法，在這N個人中最快地找到該明星
其實解法很簡單，假設(shè)有1，2，3，4，5個人 ，從1開始，問1是否認識2 ，如果認識，留下2，淘汰1 ，如果不認識，留下1，淘汰2 ，之后留下的繼續(xù)詢問3……. 最終剩下的那個就是所謂的明星。
這種解法利用的是減小數(shù)據(jù)規(guī)模的思路，不斷將問題的解集合縮小，最終得到解。和從n個數(shù)中找到出現(xiàn)次數(shù)大于n/2的那個問題很類似。代碼如下
6、已知如下代碼，并在兩個線程中同時執(zhí)行f1和f2，待兩個函數(shù)都返回后，a的所有可能值是哪些？、
（1）b=a*2,c=a+11,a=c,a=b a=4
（2）b=a*2,c=a+11,a=b,a=c a=13
（3）b=a*2,a=b,c=a+11,a=c a=15
（4）c=a+11,a=c,b=a*2,a=b a=26
以上是阿里巴巴大數(shù)據(jù)工程師部分筆試題中的解答題，還有很多題目沒有寫出來。需要的小伙伴可以給我留言或加文中圖片里面的學習君羊。
