腾讯二面,我被 “赛马” 问题难住了

程序员鱼皮

共 2124字,需浏览 5分钟

 ·

2021-04-19 18:12

很难一次答对的经典面试题,处处是坑

大家好,我是鱼皮。

今天分享一道我曾经被难住了的面试题,也是一道大厂面试时经常会被问到的面试题,赛马问题。

题目其实不难,但是第一次被问到时,稍有不慎,就会答错。所以,一起来学习下吧!

问题

64 匹马 赛跑,没有任何秒表之类的计时工具,跑道每次只允许 8 匹马 同时比,问 最少 需要比赛几场才能够选出跑的最快的 前 4 名

题目描述就这么多,大家可以先思考一下,然后在投票中给出答案吧~

下面公布解题思路和答案。

解题思路

这道题目坑点很多,题目中任何一个数字的改动都会影响到最终结果,因此一定要明确题目上的关键数字。

网上也有很多题目的变种,比如 36 匹马 6 个跑道找前三名,但思路都是一致的,下面我们模拟一下比赛全程。

第一轮

首先,跑道最多允许 8 匹马同时比,那我们一定要最大程度地利用资源,每场比赛都要上满 8 匹马。

所以第一轮最简单,无脑 将 64 匹马分为 8 组,每组 8 匹马比一场 就好了,共计 8 场比赛。

组号参赛选手
组 1🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴
组 2🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴
组 3🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴
组 4🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴
组 5🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴
组 6🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴
组 7🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴
组 8🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴

本轮比赛之后,由于题目要求选出前 4 名,因此,每组比赛第 4 名之后的马可以直接淘汰,还剩 32 匹马。

组号参赛选手(🐎 = 组内冠军)
组 1🐎 🐴 🐴 🐴
组 2🐎 🐴 🐴 🐴
组 3🐎 🐴 🐴 🐴
组 4🐎 🐴 🐴 🐴
组 5🐎 🐴 🐴 🐴
组 6🐎 🐴 🐴 🐴
组 7🐎 🐴 🐴 🐴
组 8🐎 🐴 🐴 🐴

第二轮

第二轮开始,我们必须精打细算了。

最简单的方式是将剩下的 32 匹马直接分为 4 组去比赛,但其实利用上一轮的信息,我们可以有更好的方法。

让上轮比赛中,每组第 1 名一起比赛 1 场,然后按照本轮比赛结果,选出前 4 组。

赛场:🐎 🐎 🐎 🐎 🐎 🐎 🐎 🐎

比赛结果:

组号参赛选手(🐎 = 组内冠军)
组 1🐎 🐴 🐴 🐴
组 2🐎 🐴 🐴 🐴
组 3🐎 🐴 🐴 🐴
组 4🐎 🐴 🐴 🐴
组 5🐎 🐴 🐴 🐴

这么操作的原因是:如果某个组的第一名都进不了前 4,那这个组剩下的马肯定也进不了前 4,直接整组淘汰即可。

截止到目前,还剩下 16 匹马,那这一轮淘汰到这里就结束了么?

其实并没有,以这轮比赛排名第四的马所在的组为例,这个组的冠军最高也才第四名,那么这个组其他的马也是可以被淘汰的。同理,可以淘汰更多的马,剩余 10 匹。

组号参赛选手(🐎 = 组内冠军)
组 1🐎 🐴 🐴 🐴
组 2🐎 🐴 🐴 🐴
组 3🐎 🐴 🐴 🐴
组 4🐎 🐴 🐴 🐴

现在场上还有 10 匹马,看似胜利近在咫尺,但其实,接下来才是关键!

第三轮

接下来我们的目标是从 10 匹马中选出前 4 名,但一场比赛只能容纳 8 匹马,那好像至少还得比两场。

一步步来吧,先选 8 匹马比一场呗,问题是选哪 8 匹马呢?

不知道大家有没有发现,在无意中,冠军已经产生了,那就是组内组外都未尝败绩的那匹马,强中之强!

组号参赛选手(🐎 = 组内冠军)
组 1🏆 🐴 🐴 🐴
组 2🐎 🐴 🐴
组 3🐎 🐴
组 4🐎

因此,它不用再比了,目标变成,从剩余 9 匹马中选出第 2 - 4 名。

让我们任意选 8 匹马先比一场吧,选出前 3 名。

组号参赛选手(🐎 = 组内冠军)
组 1🏆 [ 🐴 🐴 🐴 ] 出战
组 2[ 🐎 🐴 🐴 ] 出战
组 3[ 🐎 🐴 ] 出战
组 4🦓(未参与比赛的马)

那么最后一轮,还需要让上轮没比的马与前 3 名比 1 场,万一人家是黑马呢?

赛场:🐎 🐴 🐴 🦓

至此,答案出来了,最少需要 8 + 1 + 1 + 1 = 11 场。

然而,这是一个错误答案!

其实,还有更优解!

在还剩 9 匹马的时候,如果不任选 8 匹马比赛,而是先移除组 2 的冠军,让剩下 8 匹马赛一场。

如果这场比赛中,组 3 的冠军拿了第一,那么由于之前已经证明了组 2 的冠军强于组 3 的冠军,则前 4 名已经确定,只需要比 10 场。如果它不是第一,那么还是要多比一场了。

因此正确答案是,最少需要 10 场,你做对了么?


最后,为什么这道题目会出现在程序员面试中呢?聪明的你一定发现了,上述的赛马问题本质上是一个 TopN(取前几名)问题,可以通过分治的方式解决,是一种经典的算法思维。如果是在分布式系统中,则体现了 并行计算 的优势,可以利用资源(比如有 8 个跑道)对各个组同时计算,从而提高运算效率。此外,利用已有的数据结果也是非常重要的。

祝大家周末愉快,学到的话别忘了帮鱼皮点个 赞 + 在看 支持下吧!❤️

往期推荐

小知识,啥是热数据探测?

聊聊有哪些参与项目的好途径吧

【干货】关于我被百大 UP 主放鸽子这档事

浏览 46
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报