带答案分享-算法面试中的趣味题目

今天给大家分享一下去年校招面试过程中遇到一些比较有趣的题目，并附上我个人理解的答案，希望对大家校招有所帮助。

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。

有关该题更详细的讨论，参考博客：https://blog.csdn.net/muyimo/article/details/40187023

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<arr.length;i++){
            arr[arr[i] % n] += n;
        }
        for(int i = 0;i<n;i++){
            System.out.println(i + ":" + arr[i] / n);
        }
    }
}

输出为：

6、三色旗问题

大伙可以参考博客：https://blog.csdn.net/u011200844/article/details/43227301

7、 已知有个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。

推荐阅读 分享两个群友分享的面经整理： 1、概率题：https://blog.csdn.net/BertDai/article/details/78070092 2、大数据题：https://blog.csdn.net/v_july_v/article/details/6279498/