最近老是聽到小伙伴們說一些找工作的時(shí)候筆試遇到的問題，這篇文章就是找一些阿里巴巴近幾年的筆試題及解答方法，因?yàn)閭€(gè)人覺得阿里的題目應(yīng)該代表目前大數(shù)據(jù)領(lǐng)域的行業(yè)水平，別的公司考的只會(huì)偏易而不會(huì)更難，當(dāng)然這是在同等職位的情況下，希望對(duì)大家有所幫助。

1、有三個(gè)結(jié)點(diǎn)結(jié)點(diǎn)的，可以構(gòu)成多少個(gè)種樹形結(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è)計(jì)一個(gè)最優(yōu)算法來查找一n個(gè)元素?cái)?shù)組中的最大值和最小值。已知一種需要比較2n次的方法，請(qǐng)給一個(gè)更優(yōu)的算法。情特別注意優(yōu)化時(shí)間復(fù)雜度的常數(shù)

把數(shù)組兩兩一對(duì)分組，如果數(shù)組元素個(gè)數(shù)為奇數(shù)，就最后單獨(dú)分一個(gè)，然后分別對(duì)每一組的兩個(gè)數(shù)比較，把小的放在左邊，大的放在右邊，這樣遍歷下來，總共比較的次數(shù)是N/2次；在前面分組的基礎(chǔ)上，那么可以得到結(jié)論，最小值一定在每一組的左邊部分找，最大值一定在數(shù)組的右邊部分找，最大值和最小值的查找分別需要比較N/2次和N/2次；這樣就可以找到最大值和最小值了，比較的次數(shù)為N/2 * 3= (3N)/2 次

實(shí)現(xiàn)代碼如下：#include#include#defineN 7

4、已知三個(gè)升序整數(shù)數(shù)組a[l], b[m]和c[n]。請(qǐng)?jiān)谌齻€(gè)數(shù)組中各找一個(gè)元素，是的組成的三元組距離最小。三元組的距離定義是：假設(shè)a[i]、b[j]和c[k]是一個(gè)三元組，那么距離為:Distance = max(|a[ I ] – b[ j ]|, |a[ I ] – c[ k ]|, |b[ j ] – c[ k ]|)請(qǐng)?jiān)O(shè)計(jì)一個(gè)求最小三元組距離的最優(yōu)算法，并分析時(shí)間復(fù)雜度。

感覺和排序數(shù)組中和為給定值的兩個(gè)數(shù)字有點(diǎn)像，再繼續(xù)順著思路往下走，要是兩個(gè)已排序（從小到大）的數(shù)組，a[n],b[m],如何求解兩數(shù)組中差值（非負(fù)）最小的兩個(gè)點(diǎn)，當(dāng)然暴力求解肯定是可以的，有沒有其他更好的算法呢？想想這個(gè)和排序數(shù)組中給定值的兩個(gè)數(shù)字有沒有什么關(guān)系？或者能不能從那個(gè)方法獲取思路，對(duì)，方法大致是一樣的，就是先分別取兩個(gè)數(shù)組a[n],b[m]中最小的數(shù)a[i],b[j]，計(jì)算兩個(gè)數(shù)的差值，并記錄下來currentMin，然后取min(a[i],b[j]),所在的數(shù)組，

intminDifference(int*arrayOne,size_tcntOne,int*arrayTwo,size_tcntTwo)

5、有N-1個(gè)群眾和1個(gè)明星，所有的群眾都認(rèn)識(shí)該明星，但明星不認(rèn)識(shí)任何一個(gè)群眾，群眾之間是否認(rèn)識(shí)未知。假如你是一個(gè)機(jī)器人，具有詢問一個(gè)人是否認(rèn)識(shí)另外一個(gè)人的功能，請(qǐng)?jiān)O(shè)計(jì)一個(gè)最佳算法，在這N個(gè)人中最快地找到該明星

其實(shí)解法很簡單，假設(shè)有1，2，3，4，5個(gè)人 ，從1開始，問1是否認(rèn)識(shí)2 ，如果認(rèn)識(shí)，留下2，淘汰1 ，如果不認(rèn)識(shí)，留下1，淘汰2 ，之后留下的繼續(xù)詢問3……. 最終剩下的那個(gè)就是所謂的明星。

這種解法利用的是減小數(shù)據(jù)規(guī)模的思路，不斷將問題的解集合縮小，最終得到解。和從n個(gè)數(shù)中找到出現(xiàn)次數(shù)大于n/2的那個(gè)問題很類似。代碼如下

6、已知如下代碼，并在兩個(gè)線程中同時(shí)執(zhí)行f1和f2，待兩個(gè)函數(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ù)工程師部分筆試題中的解答題，還有很多題目沒有寫出來。需要的小伙伴可以給我留言或加文中圖片里面的學(xué)習(xí)君羊。