這里給大家分享幾個面試時遇到的趣味性比較濃厚的題目，答案呢也是個人的理解， 不足的地方，還望大家指出！

1、25匹馬，有一條只能5匹馬比賽的賽道，我們無法計時，只能看到馬的排名，如何用最短的次數(shù)找出跑的最快的5匹馬？

這道題目的話最好的情況是7次，最壞的情況是10次。我們首先建立一個表格，先把25匹馬分為如下的五組：

每組進(jìn)行比賽，假設(shè)第一組快慢順序為A1、A2、A3、A4和A5，第二組依次類推。那么各組的第一分別是A1、B1、C1、D1、E1。

在最好的情況下，先讓A1、B1、C1、D1、E1比賽，得到第一名，假設(shè)A1是第一名，并且順序是A1 > B1 > C1 > D1 > E1；然后讓A2加入比賽，若比賽結(jié)果為B1 > C1 > D1 > A2。那么前五名是A1、B1、C1、D1、E1，共需比賽7次。那么在最壞的情況下，每次新加入一個候補(bǔ)，得到一個新的名次的馬，此時共需要10次比賽。

這個題更加?？嫉氖菃柸绾斡米疃痰拇螖?shù)找出最快的3匹馬，這個題和找出5匹馬還不太一樣。如果找出3匹馬，只需要比賽7次即可，前六次假設(shè)和上面的過程一樣，A1是最快的馬，剩下的名次是B1 > C1 > D1 > E1。此時并不是讓A2、B1、C1、D1、E1進(jìn)行比賽，先仔細(xì)分析一下，第二名一定出現(xiàn)在B1 和 A2之中，若B1 > A2，那么第三名出現(xiàn)在A2 、B2、C1之中，若A2 > B1，那么第三名出現(xiàn)在A3 、B1之中。因此，第七場比賽只需要讓A2、A3、B1、B2、C1五匹馬比賽，得到前兩名即可。因此只需要7場比賽就可以得到跑的最快的3匹馬。

2、一條無限長的直線，有兩個機(jī)器人，兩個機(jī)器人執(zhí)行同一段代碼，這一段代碼中只有幾條語句：right代表向右走，left代表向左走，if arrived else代表另一個機(jī)器人是否走過這個地方。goto代表代碼的跳轉(zhuǎn)，請寫一段代碼確保兩個機(jī)器人能夠相遇。

偽代碼如下：

start:
if arrived:
 right
 right
else:
 right
goto start

簡單解釋一下，假設(shè)兩個機(jī)器人A和B都往右走，B在前A在后，一開始二者保持相同的速度前進(jìn)，當(dāng)A到達(dá)曾經(jīng)B經(jīng)過的點(diǎn)后，發(fā)現(xiàn)此后的路是B此前經(jīng)過的，那么A開始提速兩倍，B一直保持原來的一倍速度不變，那樣的話，A一定會追上B。

3、海量數(shù)據(jù)如何求中位數(shù)？數(shù)據(jù)無法放入內(nèi)存，只需考慮空間復(fù)雜度，不需要考慮時間復(fù)雜度。

假設(shè)我們的數(shù)據(jù)都是無符號的32位整數(shù)，既然不考慮時間復(fù)雜度，可以通過二進(jìn)制來解決，從高位到低位依次判斷，首先遍歷所有數(shù)據(jù)，并記錄最高位為0和1的個數(shù)（最高位為0的肯定是小于最高位為1的）記為N0、N1。

那么根據(jù)N0和N1的大小就可以知道中位數(shù)的最高位是0還是1

若N0>N1，那么再計算N00和N01，如果N00>(N01+N1)（這里一定注意是N00要大于N01和N1數(shù)量的總和，而非N00大于N01），則說明中位數(shù)的最高兩位是00，那么再計算N000和N001....依次計算就能找到中位數(shù)。

4、信息流采樣，有n份數(shù)據(jù)，但是n的長度并不知道，設(shè)計一個采樣算法，使得每份被選擇的概率是相同的。

這道題其實(shí)考察的是蓄水池采樣的方法，這里咱們簡單介紹下蓄水池算法的思路。

一開始選擇第一個數(shù)據(jù)作為候選數(shù)據(jù)，以概率1/2拿第二個數(shù)據(jù)替換當(dāng)前候選，以1/3選擇拿三個數(shù)據(jù)替換當(dāng)前候選，依次類推。

這樣，第x個數(shù)據(jù)為最終選擇的數(shù)據(jù)的概率 = x被選擇的概率 * (x+1沒被選擇的概率) * (x+2沒有被選擇的概率) ......(n沒有被選擇的概率)

舉個例子，第2哥數(shù)據(jù)被選擇的概率為：1/2 * （2/3 * 3/4 * 4/5 .... n-1/n) = 1 / n

5、n個[0,n)的數(shù)，求每個數(shù)的出現(xiàn)次數(shù)（不能開辟額外空間）

這里關(guān)鍵是看清楚題意，n個數(shù)，然后是左閉右開的區(qū)間，也就是說每個數(shù)都不會大于等于n，那么思路主要有以下兩點(diǎn)：

1）如果我們給一個索引下的數(shù)不管加上多少個n，那么這個數(shù)對n取余的話，我們就能知道這個數(shù)原來是多少；

2）另一方面，如果一個數(shù)出現(xiàn)一次，我們就在對應(yīng)索引位置下的數(shù)加上n，那么每個數(shù)對應(yīng)索引位置上的數(shù)對n取商的話，就是這個數(shù)出現(xiàn)的次數(shù)。這樣就做到了沒有開辟額外的空間。

代碼如下：

public class timeDemo {
 public static void main(String[] args){
 int[] arr = {0,1,3,4,3,2,5,4,3,7,3,2,4,6};
 int n = 8;
 for(int i = 0;i<arr.length;i++){
 arr[arr[i] % n] += n;
 }
 for(int i = 0;i<n;i++){
 System.out.println(i + ":" + arr[i] / n);
 }
 }
}

輸出為：

6、 已知有個rand7()的函數(shù)，返回1到7隨機(jī)自然數(shù)，怎樣利用這個rand7()構(gòu)造rand10()，隨機(jī)1~10。

產(chǎn)生隨機(jī)數(shù)的主要原則是每個數(shù)出現(xiàn)的概率是相等的，如果可以得到一組等概率出現(xiàn)的數(shù)字，那么就可以從中找到映射為1~10的方法。

rand7()返回1~7的自然數(shù)，構(gòu)造新的函數(shù) (rand7()-1)*7 + rand7()，這個函數(shù)會隨機(jī)產(chǎn)生1~49的自然數(shù)。原因是1~49中的每個數(shù)只有唯一的第一個rand7()的值和第二個rand7()的值表示，于是它們出現(xiàn)的概率是相等，均為1/49。

但是這里的數(shù)字太多，可以丟棄41~49的數(shù)字，把1~40的數(shù)字分成10組，每組映射成1~10中的一個，于是可以得到隨機(jī)的結(jié)果。

具體方法是，利用(rand7()-1)*7 + rand7()產(chǎn)生隨機(jī)數(shù)x，如果大于40則繼續(xù)隨機(jī)直到小于等于40為止，如果小于等于40，則產(chǎn)生的隨機(jī)數(shù)為(x-1)/4+1。

你們有遇到過哪些有趣的面試題？