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

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

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

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

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

這個題更加常考的是問如何用最短的次數找出最快的3匹馬，這個題和找出5匹馬還不太一樣。如果找出3匹馬，只需要比賽7次即可，前六次假設和上面的過程一樣，A1是最快的馬，剩下的名次是B1 > C1 > D1 > E1。此時并不是讓A2、B1、C1、D1、E1進行比賽，先仔細分析一下，第二名一定出現在B1 和 A2之中，若B1 > A2，那么第三名出現在A2 、B2、C1之中，若A2 > B1，那么第三名出現在A3 、B1之中。因此，第七場比賽只需要讓A2、A3、B1、B2、C1五匹馬比賽，得到前兩名即可。因此只需要7場比賽就可以得到跑的最快的3匹馬。

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

偽代碼如下：

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

            
          

簡單解釋一下，假設兩個機器人A和B都往右走，B在前A在后，一開始二者保持相同的速度前進，當A到達曾經B經過的點后，發現此后的路是B此前經過的，那么A開始提速兩倍，B一直保持原來的一倍速度不變，那樣的話，A一定會追上B。

3、海量數據如何求中位數？數據無法放入內存，只需考慮空間復雜度，不需要考慮時間復雜度。

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

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

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

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

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

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

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

舉個例子，第2哥數據被選擇的概率為：

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

            
          

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

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

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

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

代碼如下：

            
              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、 已知有個rand7()的函數，返回1到7隨機自然數，怎樣利用這個rand7()構造rand10()，隨機1~10。

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

rand7()返回1~7的自然數，構造新的函數 (rand7()-1)*7 + rand7()，這個函數會隨機產生1 _{49的自然數。原因是1} 49中的每個數只有唯一的第一個rand7()的值和第二個rand7()的值表示，于是它們出現的概率是相等，均為1/49。

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

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

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