算法面试中的趣味题目(附答案分享)

本文转载自:小小挖掘机 作者:石晓文

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

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/

原文发布于微信公众号 - CVer(CVerNews)

原文发表时间:2019-08-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券