這里給大家分享幾個(gè)面試時(shí)遇到的趣味性比較濃厚的題目，答案呢也是個(gè)人的理解， 不足的地方，還望大家指出！
1、25匹馬，有一條只能5匹馬比賽的賽道，我們無法計(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è)題更加常考的是問如何用最短的次數(shù)找出最快的3匹馬，這個(gè)題和找出5匹馬還不太一樣。如果找出3匹馬，只需要比賽7次即可，前六次假設(shè)和上面的過程一樣，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、一條無限長的直線，有兩個(gè)機(jī)器人，兩個(gè)機(jī)器人執(zhí)行同一段代碼，這一段代碼中只有幾條語句：right代表向右走，left代表向左走，if arrived else代表另一個(gè)機(jī)器人是否走過這個(gè)地方。goto代表代碼的跳轉(zhuǎn)，請(qǐng)寫一段代碼確保兩個(gè)機(jī)器人能夠相遇。
偽代碼如下：
start:
if arrived:
right
right
else:
right
goto start
簡單解釋一下，假設(shè)兩個(gè)機(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一定會(huì)追上B。
3、海量數(shù)據(jù)如何求中位數(shù)？數(shù)據(jù)無法放入內(nèi)存，只需考慮空間復(fù)雜度，不需要考慮時(shí)間復(fù)雜度。
假設(shè)我們的數(shù)據(jù)都是無符號(hào)的32位整數(shù)，既然不考慮時(shí)間復(fù)雜度，可以通過二進(jìn)制來解決，從高位到低位依次判斷，首先遍歷所有數(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），則說明中位數(shù)的最高兩位是00，那么再計(jì)算N000和N001....依次計(jì)算就能找到中位數(shù)。
4、信息流采樣，有n份數(shù)據(jù)，但是n的長度并不知道，設(shè)計(jì)一個(gè)采樣算法，使得每份被選擇的概率是相同的。
這道題其實(shí)考察的是蓄水池采樣的方法，這里咱們簡單介紹下蓄水池算法的思路。
一開始選擇第一個(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沒被選擇的概率) * (x+2沒有被選擇的概率) ......(n沒有被選擇的概率)
舉個(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ū)間，也就是說每個(gè)數(shù)都不會(huì)大于等于n，那么思路主要有以下兩點(diǎn)：
1）如果我們給一個(gè)索引下的數(shù)不管加上多少個(gè)n，那么這個(gè)數(shù)對(duì)n取余的話，我們就能知道這個(gè)數(shù)原來是多少；
2）另一方面，如果一個(gè)數(shù)出現(xiàn)一次，我們就在對(duì)應(yīng)索引位置下的數(shù)加上n，那么每個(gè)數(shù)對(duì)應(yīng)索引位置上的數(shù)對(duì)n取商的話，就是這個(gè)數(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、 已知有個(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。
你們有遇到過哪些有趣的面試題？
聯(lián)系客服
