腾讯二面,我被 “赛马” 问题难住了
共 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 个跑道)对各个组同时计算,从而提高运算效率。此外,利用已有的数据结果也是非常重要的。
祝大家周末愉快,学到的话别忘了帮鱼皮点个 赞 + 在看 支持下吧!❤️
往期推荐