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

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

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

每組進(jìn)行比賽，假設(shè)第一組快慢順序?yàn)锳1、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次。那么在最壞的情況下，每次新加入一個(gè)候補(bǔ)，得到一個(gè)新的名次的馬，此時(shí)共需要10次比賽。

這個(gè)題更加常考的是問(wèn)如何用最短的次數(shù)找出最快的3匹馬，這個(gè)題和找出5匹馬還不太一樣。如果找出3匹馬，只需要比賽7次即可，前六次假設(shè)和上面的過(guò)程一樣，A1是最快的馬，剩下的名次是B1 > C1 > D1 > E1。此時(shí)并不是讓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之中。因此，第七場(chǎng)比賽只需要讓A2、A3、B1、B2、C1五匹馬比賽，得到前兩名即可。因此只需要7場(chǎng)比賽就可以得到跑的最快的3匹馬。

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

偽代碼如下：

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

            
          

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

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

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

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

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

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

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

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

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

舉個(gè)例子，第2哥數(shù)據(jù)被選擇的概率為：

            
              1/2 * （2/3 * 3/4 * 4/5 .... n-1/n) = 1 / n

            
          

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

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

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

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

代碼如下：

            
              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
              
            
          

輸出為：

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

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

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

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

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

你們有遇到過(guò)哪些有趣的面試題？